单车单点配送的线路优化课件

1、项目6 线路优化1233任务1 单车单点配送的线路优化任务2 单车多点线路优化任务3 多车多点配送的线路优化返回第1页，共38页。任务1 单车单点配送的线路优化1.1任务导入配送中心S向t配送货物，图6-1中的6个点是途径的客户点，各点之间的路径距离公里数如线上的数据所示，货物吨/公里运价50元，请制定从S出发将货品配送到t的最优配送方案。1 .3相关知识1 .3. 1最短路问题的定义在实际送货过程中常常会遇到要从配送中心给单个客户送货的问题，这时企业所期望的通常是能够找到一条从配送中心到客户点最短的运行路线，因为这样能够节省油耗，节省成本。下一页返回第2页，共38页。任务1 单车单点配送的线

2、路优化这种需要求从始点到终点的一条路径使得路径总长最短的问题被称为最短路问题。最短路问题一般是描述在一个网络图中，给定一个始点和一个终点，求始点到终点的一条路径且使得路径总长最短。除配送路径选取问题外，有许多实际问题都可以归结为最短路问题，例如，两地之间的管道铺设、线路安装、道路修筑等都属于最短路问题。1.3. 2解决方法1.最大相邻法上一页下一页返回第3页，共38页。任务1 单车单点配送的线路优化本方法较简单，思路为:从始点或终点开始，找与该点相连的所有点中最近的点，从而得到第二个点，再找与第二个点相连的所有点中最近的点得到第三个点，以此类推。但是注意不能够走回头路，也就是前面找到的点不能够

3、再被找出来一次。 2. Dijkstra标号法该法是Dijkstra1959年提出的，能求出网络的任一点S到其他各点的最短路。在计算过程中，对每一个点J都要赋予一个标号，这分为固定标号P (j)和临时标号T (j)，其含义如下:上一页下一页返回第4页，共38页。任务1 单车单点配送的线路优化P (j)从始点S到J的最短路长;T (j)从始点S到J的最短路长的上限。一个点j的标号只能是上述两种标号之一。若为T标号，则需要视情况修改，而一旦成为P标号，就固定不变了。开始先给始点S标上P标号0，然后检查一切与点S相连的边的另一端点j，修改其T标号为位势Vj，在网络图中的所有T标号中选取最小的并把它修

4、改为P标号。以后每次都检查刚得到P标号的那点，按一定规则修改其一切相连边另一端点的T标号，再在网络中的T标号中选取最小者，把它改为P标号。上一页下一页返回第5页，共38页。任务1 单车单点配送的线路优化这样，每次都把至少一个T标号点改为P标号点，因为网络中共有n个节点，所以最多只需要n一1次就能把终点t改为P标号。这样就求得了S到t的最短路。采用Dijkstra标号法解决过程如图6-4所示。 从图中可以看出，该问题有两种可行方案:S3 2 4 t;S 3- 5 t两种方案距离都是9。同时这种方法也求出了S到图中其他各点的最短路和最短距离。到其他各点的最短路如图6 -4中箭头所示，最短距离就是在

5、各点旁边的方框中标出的数字。上一页返回第6页，共38页。任务2 单车多点线路优化2. 1任务导入仍然采用任务1中的网络图，如果要求一辆车从配送中心s出发，装满所有客户需要的货品，给所有客户送完货后再回到配送中心，如何运行可使得总的行驶距离最短？2. 3相关知识在实际配送作业中，为了能够充分利用车辆的载重量和吨位，节省运费，经常会将某些客户点的部分货物装载在同一辆车上进行配送作业，送完所有客户点的货物后再回到起点，同时也希望所行走的路径最短，这就是单车多点作业。这种问题被称为旅行商问题(TSP问题，Traveling Salesman Problem) 。下一页返回第7页，共38页。任务2 单车

6、多点线路优化2. 3. 1 TSP问题定义假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求走的路径路程为所有路径之中的最小值。2. 3. 2解决方法TSP问题的解决方法有多种，大多原理较复杂。此处介绍一种利用软件解决的方法，方法较简单。这种软件就是WinQSB软件。(1)新建问题。上一页下一页返回第8页，共38页。任务2 单车多点线路优化运行:程序WinQSB Network Modeling，单击File New Problem，出现对话框，问题类型 Problem Type中选择Traveling

7、 Salesman Problem，输入问题名称TSP1，节点数8，其他默认，单击OK按钮。(2)从菜单Edit-Node Name，更改节点名称(如图6-7所示)。(3)在出现的对话框中输入所有有连线的两点间的距离。由于该图没有方向所以是双向的，如S: 1距离是10, 1: S距离也同样是10;如果某些道路有方向，则代表该道路是单行道，只能一个方向有距离，如S 1,则只有S: 1是10, 1: S没有距离(如图6-8所示)。(4)解决问题。上一页下一页返回第9页，共38页。任务2 单车多点线路优化单击求解Solve and Analyze，从中选择求解问题Solve the Problem这

8、时会出现如图6 -9所示的选择框，这是要求选择解决TSP问题的计算机算法，不同的算法有可能得到不同的结果。选择每一种算法，记录每一种算法的结果，选择最小的结果。例如，本任务的最小结果就是27，在结果Results中选择图解Graphic Solution，得到图解结果，如图6-10所示，这就是最优行驶路径。上一页返回第10页，共38页。任务3 多车多点配送的线路优化3. 1任务导入配送中心A要向B, C, D, E, F, G6个门店配送货物，如图6-14所示，它们之间的距离和每一处的配送货物量见图中标注，配送车辆载重量有2. 5 t和4t两种，请规划总距离最短的配送方案。3. 3相关知识3.

9、 3. 1里程节约法的基本原理使用里程节约法的基本条件是同一条线路上所有客户的需求量总和不大于一辆车的额定载重量。下一页返回第11页，共38页。任务3 多车多点配送的线路优化送货时由这辆车装着所有客户的货物沿着一条精心挑选的最佳线路依次将货物送到各个客户的手中，这样既保证按时按量将用户需要的货物及时送到，又节约了费用，缓解了交通紧张的压力，并减少了运输对环境造成的污染。1.里程节约法的基本规定利用里程节约法确定配送线路的主要出发点是根据配送方的运输能力及其到客户之间的距离和各客户之间的相对距离来制定使配送车辆总的周转量达到或接近最小的配送方案。下面假设:(1)配送的是同一种或相类似的货物;上一

10、页下一页返回第12页，共38页。任务3 多车多点配送的线路优化(2)各用户的位置及需求量已知;(3)配送方案有足够的运输能力。里程节约法制定出的配送方案除了使总的周转量最小外，还应满足:(1)方案能满足所有用户的到货时间要求;(2)不使车辆超载;(3)每辆车每天的总运行时间及里程满足规定的要求。2.里程节约法的基本思想如图6-15所示，设P0为配送中心，分别向客户Pi和Pj送货。上一页下一页返回第13页，共38页。任务3 多车多点配送的线路优化P0到Pi和Pj的距离分别为d0i和d0j，两个客户Pi和Pj之间的距离为dij，送货方案只有两种即配送中心P0向客户Pi 、 Pj分别送货和配送中心P

11、0向客户Pi 、 Pj同时送货，如图6-15(a)和(b)所示。根据节约法的基本思想，如果一个配送中心P0分别向n个客户Pj (j=1,2,，n)配送货物，在汽车载重能力允许的前提下，每辆汽车的配送线路中经过的客户个数越多，里程节约量越大，配送线路越合理。3.3.2解决方法(1)计算最短距离。根据配送网络中的已知条件，计算配送中心与客户之间及各客户之间的最短距离，结果如表6-1所示。上一页下一页返回第14页，共38页。任务3 多车多点配送的线路优化(2)计算节约里程Sij，结果如表6-2所示:(3)将节约里程Sij进行分类，按从大到小的顺序排序，得到表6-3;(4)确定配送线路。从分类表中，按

12、节约里程大小顺序组成线路图(如图6-16所示)。(1)初始方案:对每一客户分别单独派车送货，原路返回:配送线路:6条配送距离S0 ; 196 km配送车辆:2. 5t x6上一页下一页返回第15页，共38页。任务3 多车多点配送的线路优化(2)修正方案1:按节约里程S由大到小的顺序，同时考虑车辆额定载重和各点需求量的关系，将E , G连成一条线路，得修正方案1，配送线路1; A-E-G -A,剩余客户点单独配送，配送线路5条(如图6-17所示)。节约里程:40 km配送距离S1:196-40=156 (km)由于EG 两点需求量之和为2. 9t，因此需要1辆4t车，所以，配送车辆:4tx1+2

13、.5tx4上一页下一页返回第16页，共38页。任务3 多车多点配送的线路优化(3)修正方案2:在剩余的S中，按由大到小的顺序连接F 、 G，同时考虑车辆额定载重4t和F点的需求量1. 1t，可以把F点并入线路1，这时需要4t车1辆，得到配送线路2; A-E-G-F-A,剩余客户点单独配送，配送线路4条，如图6-18所示。节约里程:40 +39 =79 (km)配送距离S2：156-39 =117 ( km)配送车辆:4tx1+2.5Stx3这条线路就是一条有效的配送线路，并且本条线路车辆已经装满，不能够再加入其他客户点了。所以所有与本线路有关联的其他客户点的节约里程都无效了，此处线路EF, D

14、F, CF, DE都无效了，不予考虑。上一页下一页返回第17页，共38页。第18页，共38页。任务3 多车多点配送的线路优化(4)修正方案3:在剩余可行的S中，选择里程节约最大的线路这时找到了CD，考虑C, D两点的需求量之和为1. 7t，这时可以采用一辆2. 5 t车完成两点的配送作业，得到配送线路3; A-C-D-A。剩余客户点B单独配送，配送线路3条(如图6-19所示)。节约里程:79+14=93 (km)配送距离S3 ; 117-14 = 103 (km)配送车辆:4t x1 +2. 5t x2上一页下一页返回第19页，共38页。任务3 多车多点配送的线路优化(5)修正方案4:在剩余可

15、行的s中，下一个最大的是BC，也就是BC两点同车配送，这时考虑B的需求量0. 8，可以考虑将B并入线路3; A-C-D-A,得到线路4; A-B-C-D-A。这时正好需一辆2. 5t的车可以装载B, C, D三家客户的货品，配送线路2条(如图6 - 20所示)。节约里程:93 + 12 =105(km)配送距离S4; 103-12=91 (km)配送车辆:4t x1 +2.5tx1所以，最终配送方案为线路2; A-E-G-F-A，需要1辆4t车和3辆2. 5 t车;线路4; A-B-C-D-A，需要1辆2. 5 t车1辆4t车。上一页返回第20页，共38页。图6 -1 S t的6种不同配送路径图返回第21页，共38页。图6-4采用Diikstra标号法返回第22页，共38页。图6 -7菜单中更改节点名称返回第23页，共38页。第24页，共38页。图6 -8两点间的距离返回第25页，共38页。图6-9解决问题返回第26页，共38页。图6-10最优行驶路径返回第27页，共38页。图6 -14配送中心A至6个不同门店的配送路线返回第28