数学建模2015年5月vrp

1、车辆路径问题Vehicle Routing Problem 目录1. 车辆路径问题定义2. 车辆路径问题分类3. 车辆路径问题求解算法概述4. 以模拟退火算法求解CVRP为例2Graphical RepresentationSupplierGraphical RepresentationSupplier1. 车辆路径问题定义A fleet of vehicles supplies customers. Each vehicle has a certain capacity and each customer has a certain demand. Further on there exis

2、ts a depot(s) and a distance (length, cost, time) matrix between the customers. We look for optimal vehicle routes (minimum distance or number of vehicles). The Vehicle Routing Problem (VRP) is a generic name given to a whole class of problems in which a set of routes for a fleet of vehicles based a

3、t one or several depots must be determined for a number of geographically dispersed cities or customers. The objective of the VRP is to deliver a set of customers with known demands on minimum-cost vehicle routes originating and terminating at a depot. The VRP is a well known integer programming pro

4、blem which falls into the category of NP Hard problems, meaning that the computational effort required to solve this problem increases exponentially with the problem size. For such problems it is often desirable to obtain approximate solutions, so they can be found fast enough and are sufficiently a

5、ccurate for the purpose. Usually this task is plished by using various heuristic methods, which rely on some insight into the problem nature. This difficult combinatorial problem conceptually lies at the intersection of these two well-studied problems:The Traveling Salesman Problem (TSP): If the cap

6、acity of the vehicles C is infinite, we can get an instance of the Multiple Traveling Salesman Problem (MTSP). An MTSP instance can be transformed into an equivalent TSP instance by adjoining to the graph k-1 (being k the number of routes) additional copies of node 0 and its incident edges (there ar

7、e no edges among the k depot nodes).The Bin Packing Problem (BPP): The question of whether there exists a feasible solution for a given instance of the VRP is an instance of the BPP. The decision version of this problem is conceptually equivalent to a VRP model in which all edge costs are taken to b

8、e zero (so that all feasible solutions have the same cost). 车辆路线问题（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。 由此定义不难看出，旅行商问题（Traveling Saleman Problem,TSP）是VRP的特例，由于TSP问题已被证明是NP难题，因此，VRP也属于NP难题。 102. 车辆

9、路径问题分类Capacitated Vehicle Routing Problem (CVRP) This is the homogeneous VRP. Multiple Depot VRP (MDVRP) The customers get their deliveries from several depots. VRP with Time Windows (VRPTW) In case a time window (starttime, endtime, servicetime) is associated to each customer. Stochastic VRP (SVRP)

10、If any component has a random behaviour. Periodic VRP (PVRP)If the delivery is in some days. Split Delivery VRP (SDVRP)Several vehicles serve a customer. VRP with Backhauls (VRPB)When the vehicle must pick something up from the customer AFTER ALL deliveries are done. VRP with Pick-Ups and Deliveries

11、 (VRPPD) If the vehicle picks something up and delivers it to the customer. 3. 车辆路径问题求解算法概述精确算法（exact algorithm） 分支界限法、分支切割法、集合涵盖法等启发式算法（heuristics） 简单启发式算法（节省法或插入法、路线内间节点交换法、贪婪法和局部搜索法等方法） 两阶段启发式算法（cluster first-route second，route first-cluster second，前者是先将所有需求点大略分为几个组，然后再对各个组分别进行路线排序；后者则是先将所有的需求点建构

12、成一条路线，再根据车辆的容量将这一路线分割成许多适合的单独路线。） 基于人工智能的启发式算法 或称亚启发式算法Metaheuristic常见的亚启发式算法禁忌搜索法Tabu Search,TS模拟退火法Simulated Annealing,SA遗传算法Genetic Algorithm,GA蚁群算法Ant Colony Optimization, ACO粒子群算法Particle Swarm Optimization, PSO可变邻域搜索算法Variable Neighborhood Search, VNS混合策略:分别采用两种人工智能方法进行路线分组和路线优化几种常见亚启发式算法的比较 T

13、S算法所得到的解最接近最优解，但其运算时间也最长，是GA算法的23倍，SA算法的近20倍； 由于GA算法也能较好的逼近最优解，同时使运算时间大大缩短，所以GA算法能兼顾运算时间和效率两方面，是具有较好的发展前途的方法； SA算法求解速度非常快，也能提供一定程度上的优化方案在求解较小规模问题上具有较好效果。 注：上面数据来源于某文献，事实情况究竟如何，有待检验。144. 以SA求解CVRP为例4.1 Assumption4.2 Model4.3 Algorithm4.4 Experiments154.1 Assumption假设配送中心拥有一队同质车辆，车辆的数目不受限制，车容量相同。假设有多个

14、零售商，地理位置分散，各零售商每天的需求量为常数。假设每个零售商只允许由一辆车服务，且要求需求得到满足。假设每辆车从配送中心出发，为某些零售商送货后，再回到配送中心。每辆车每天只出行一趟。运输成本包括车辆的固定启动成本和可变运输成本。 目标：配送中心为各零售商送货，制定合理的运输线路，在满足车辆容量限制的条件下，使得运输成本最小。 164.2 Model 符号说明-车容量-零售商i的需求率 -各零售商之间以及和配送中心之间的距离 -每辆车的固定启动成本 -单位距离可变运输成本 -配送中心需要派出的车辆总数 -配送中心各车的总行驶距离 174.2 Model184.3 Alogorithm思想：

15、首先采用改进的最近邻算法产生初始解，然后用模拟退火算法对解进行优化，得到最终解。 Step 1设初值，为N个零售商分别设置访问标识值，flagi0；m=0； =0；改进的最近邻算法Step 2取源点0（配送中心）作为线路的起点；Step 3寻找与上一次加进线路中的点距离最近且flag0的零售商，判断此零售商若加进线路中是否满足车容量约束，若满足则把此零售商加到线路中去，flag1；否则不加入，flag-1；Step 4重复第3步，直到所有的零售商都已考虑，即flag0，从而得到一条线路，m+，并计算该线路的路径长度，加到 中；Step 5若存在flag-1的点，则将所有flag-1的零售商改为

16、flag0，转到第2步；否则转第6步；Step 6所得即为可行解 ，将此可行解保存在present中， m为所用车辆数目，求出总运输成本保存在变量cost中。 194.3 Alogorithm模拟退火算法Step 1: 设置初值best=present;bestcost=cost;Step 2:设置初始温度T，最小温度minT，冷却速度alpha；Step 3:判断温度，若TminT，或在同一温度下无新解接受，则结束程序，且当前解为满意解；否则转Step 4;Step 4:设置同一温度下的迭代次数L(=n*n/2),循环变量l=0，当lL，转Step 5；否则T=alpha*T，转Step 3

17、；Step 5:产生随机数r1(0,1)Step 6:若r10.5，则转Step 7，否则转Step 8；Step 7:（交叉）产生两个随机数（表示节点号）rc11.N,rc21.N，且要求rc1rc2；rc1,rc2若在同条线路上，则rc1,rc2交换，产生新解，保存在newresult中；若不在同一线路上，需考虑容量约束，若满足，则rc1,rc2交换，产生新解，保存在newresult中；若不满足，则转Step 11;204.3 Alogorithm模拟退火算法Step 8:（插入）产生1个随机数（表示节点号）rc31.N，将rc3所在线路号存在rr3中，再产生1个随机数（表示路径号）rr

18、1.countroute，且rrrr3，判断rc3加入rr是否满足容量约束，若满足，插入该线路rr头部，产生新解，保存在newresult中；否则，转Step 11;Step 9:计算新解newresult的运输成本，保存在newcost中，deta=newcost-cost，若deta=0)产生随机数r2(0,1)，若EXP(-deta/T)r2，则接受新解，调用accept();Step 11:l+;若lL，转Step 5，否则T=alpha*T，转Step 3。 214.4 Experiments224.4 Experiments234.4 Experiments241 Paolo Toth, Daniele Vigo. Models, relaxations and exact approaches for the capacitated vehicle routing problem. Discrete Applied Mathematics 123(2002)487-512.2 Michel Gendreau, Alain Hertz, Gilbert Laporte