多车辆配送路线的优化---扫描法_1.pptx

多车辆配送路线的优化---扫描法

1.多车辆配送路线的优化

什么是多车辆配送路线的优化模型假设是什么

如何求解多车辆配送路线的优化问题

2.扫描法

何为扫描法

求解步骤是什么

实例分析

1.多车辆配送路线的优化

多车辆配送路线的优化

Part1.1什么是多车辆配送路线的优化

多车辆路径问题(VehicleRoutingProblem,VRP)

经典VRP可描述如下：有多个货物需求点(或称顾客),己知每个需求点的需求量及位置，至多用m辆汽车从配送中心(或中心仓库)送货，每辆汽车载重量一定，安排汽车路线，要求每条路线不超过车辆载重量和每个需求点的需求必须且只

能由一辆车来满足，目标是使运距最短或者运输费用最少。

例如，一家大型物流中心要为成百上千的客户提供送货或取货的服务，就需要对运输车辆的数量及其行驶路线进行

规划以节约成本。

多车辆配送路线的优化

Part1.2模型假设是什么

(1)单一物流中心，多部车辆配送。

(2)每个需求点由一辆车服务，每个客户点货物需求量不超过车辆的载重容量。

(3)车辆为单一车种，即视为相同的载重量，且有容量限制。

(4)无时窗限制的配送问题。

(5)客户的位置和需求量均为已知。

(6)配送的货物视为同一种商品，便于装载。

多车辆配送路线的优化

Part1.3如何求解多车辆配送路线的优化问题

精确优化算法

智能优化算法模拟方法

启发式方法

扫描法

节约法

O

仓库仓库

图1-1合理的车辆分派方案图1-2不合理的车辆分派方案

Part1.3如何求解多车辆配送路线的优化问题

1、同一车辆服务的客户按距离聚类

多车辆配送路线的优化

原则

3.尽可能使用大载重量车辆，减少出车数量

4.取货/送货混合安排

5.从距仓库最远的站点开始设计线路

多车辆配送路线的优化

原则

如何求解多车辆配送路线的优化问题

2、避免行车路线交叉

(a)不交叉线路(b)交叉线路

2.扫描法

扫描法在VRP求解方法中是一种先分群再寻找最佳路线的算

法。求解过程分为两步：第一步是分派车辆服务的站点或客户点；第二步是决定每辆车的行车路线。

原理：先以物流中心为原点，将所有需求点的极坐标算出，然后依角度大小以逆时钟或顺时钟方向扫描，若满足车辆装载容量即划分为一群，将所有点扫描完毕后在每个群内部用最短路径算法求出车辆行驶路径。

何为扫描法

评价扫描法是一种逐次逼近法，用该方法不一定能求得物

流配送车辆路径优化问题的最优解，但是能够有效地求得问题的满意解。对于某个具体的物流配送车辆路径优化问题，由于存在多种客户编号方法，当仅选择一种客户编号方案用扫描法求解时，其计算量相对较小，但相应地解的质量可能不会很高；当选用多种客户编号方案用扫描法求解时，一般能得到质量很高的满意解，但相应地，计算量会成倍增加。研究表明，对于物流配送车辆路径优化问题，当每条路线上的客户数目大体相同且配送路线不太多时，用扫描法求解是非常有效的。

何为扫描法

Part2.2求解步骤是什么

1.以物流中心为原点，将所有客户需求点的极坐标计算出来。

2.以零角度为极坐标轴，按顺时针或逆时针方向，依角度大小开始扫描。

3.将扫描经过的客户点需求量进行累加，当客户需求总量达到一辆车的载重量限制且不超过载重量极限时，就将这些客户划分为一群，即由同一辆车完成送货服务。接着，按照同

样的方法对其余客户划分新的客户群，指派新的车辆。

4.重复步骤3,直到所有的客户都被划分到一个群中。

5.在每个群内部用TSP算法求出车辆行驶最短路径。

【例2-1】某运输公司为其客户企业提供取货服务，货物运回仓库集中

后，将以更大的批量进行长途运输。所有取货任务均由载重量为10吨的货车完成。现在有13家客户有取货要求，各客户的去货量、客户的地理位置坐标见表2-1。已知运输公司仓库的坐标为(19.50,5.56)。要求合理安排车辆，并确定各车辆行驶路线，使总运输里程最短。

表2-1客户数据信息

客户

1

2

3

4

5

6

7

8

9

10

11

12

13

Di(吨)

1.9

2.8

3.15

2.4

2

3

2.25

2.5

1.8

2.15

1.6

2.6

1.5

Xi

20.0

18.8

18.3

19.1

18.8

18.6

19.5

19.93

20.0

19.5

18.7

19.5

20.3

Yi

4.80

5.17

5.00

4.78

6.42

5.88