【国家级精品课程】中南大学数学建模lingomatlab优化建模数模培训全国赛论文B题带有客户时间窗的货车配送路径优化问题

1、2009高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从a/b/c/d中选择一项填写）： b 我们的参赛报名号为（如果赛区设置

2、报名号的话）： 29 所属学校（请填写完整的全名）： 中南大学 参赛队员 (打印并签名) ：1. 袁浩 2. 何开先 3. 李华斌 指导教师或指导教师组负责人 (打印并签名)： 日期： 2009 年 08月 17日b题 带有客户时间窗的货车配送路径优化问题摘要本文主要是求解一个典型的和一个带有随机需求的带有时间窗车辆路径问题（vrptw问题）。为简化问题，我们将时间窗假设为硬时间窗。对于问题一，利用确定性规划的方法，建立了总路程最短为目标的优化模型，但是如果直接用lingo软件硬求问题的最优精确解，就会需要很长时间才有结果，有时甚至可能得不到结果，所以我们另辟蹊径，运用c-w节约算法求解该模型

3、。c-w节约算法的主要思想是：首先将各个客户点与中心仓库相连，构成一条仅含一个客户点的送货路线，并计算总路程；然后计算将两个客户点连接在一条线路上的路程节约值，节约值越大，说明将两个客户点连在一起的总路程减少得越多，直到节约值为0为止。该算法可以很快求出较优解，但不一定会是最优解。针对算例，首先我们对此问题所需车辆数进行了估计，在估算得到至少3辆车即可完成任务的前提下，由lingo软件来求时，我们没有得出结果；但由该算法得到的c+程序求得较优车辆路径为0-8-5-7-0，0-6-4-0，0-3-1-2-0，总路程为910公里，我们认为这个解是一个比较优的解。最后，我们还对这个线路进行了小小的改

4、进，经分析又发现，完成任务后可能从某些任务点绕行比直接返回车场路程更短，故放弃直接回车场的假设，利用组合策略的floyd算法得到最短路问题的解，进而得到改进的车辆路径为0-8-5-7-2-0，0-6-4-0，0-3-1-2-0（第一条线路只是从2客户经过而已），总路程为885公里。对于问题二，利用随机规划的方法，在假设各客户的实际需求满足同样的离散概率分布的基础上，建立了总期望路程最短为目标的优化模型，并给出了随机参数的确定方法。至于处理方法，由于随机性问题中用户的需求事先未知，因此对这一类问题的求解不能采用确定性问题的做法，所以求解十分困难，我们最后也只给出了大致的努力方向。关键字 时间窗

5、随机规划 c-w节约算法 最短路一 问题重述 1问题背景车辆路径问题(vehicle routing problem, vrp)最早是于1959年首次提出的,它是指有一定数量的客户,各自有不同数量的货物需求,一个中心仓库提供这些货物,并有一个车队负责分送货物,要求组织适当的行车路线,使客户的需求得到满足,并能在满足一定的约束条件下,达到诸如路程最短、成本最小、耗费时间最少等目的。有时间窗车辆路径问题(vehicle routing problem with time window,vrptw ) 是在基本vrp中对每个客户的开始服务时间范围加以约束,与实际情况更加吻合, 因此有很强的实用背景。

6、在配送运输上，时间窗口显得越来越重要。因此，降低运输成本，提高配送的及时性和配送的服务质量，优化车辆路径问题，是降低企业成本的迫切需要。例如可以有以下的具体实例。一个中心仓库，拥有一定数量容量为q的车辆，负责对n个客户进行货物派送工作，客户i的货物需求量为，且，车辆必须在一定的时间范围内到达，早于到达将产生等待损失，迟于到达将处以一定的惩罚，这就是一个带时间窗和容量约束的车辆线路问题。2要解决的问题（1）得到一个使派送费用最小的车辆行驶路径问题的数学模型及其求解算法。（2）求解一个具体算例。有8项货物运输任务（编号为1，2，8），各项任务的货运量 （单位：吨）、装货（或卸货）时间 （单位：小时

7、）以及要求每项任务开始执行的时间范围由表1给出，这些任务由车场0发出的容量为8吨的车辆来完成，车场0与各任务点以及各任务点间的距离（单位：公里）由表2给出。这里假设车辆的行驶时间与距离成正比，每辆车的平均行驶速度为50公里/小时，问如何安排车辆的行驶路线使总运行距离最短。（3）拓展问题：当客户i的货物需求量为随机参数时的数学模型及处理方法。3相关信息表1 任务的特征及其要求表2 点对之间的距离（表1与表2都见附录）二 问题分析 由题意得知，可以分析出问题的要求是将货物准时送到，并且要求使用的车辆数最少、车辆行走的路程最短、每个客户仅被一辆车访问一次。该要求涉及到的对象有：货物、时间、送货的车辆

8、、道路以及客户。进一步可以分析出问题要求涉及到的这些对象的关键属性有：货物的需求数量，车辆的载重量，车辆的行驶速度，道路的长度，以及客户是否被访问过。这些属性中的大部分是由问题已知条件给出的，进而要分析出各个对象之间的关系，比如货物的需求量与车辆的载重量之间的关系，车辆的行驶速度与时间的要求之间的关系，道路的长度与时间之间的要求的关系等等。在上述分析结果的基础上，就可以假设变量建立等式了。就算法而言，精确算法如列生成法，割平面法等，可以求最优解，但速度慢，且数据量一大时间复杂度呈指数增长，不利于解决大规模的实际问题。所以我们主要考虑启发式算法如遗传算法，蚂蚁算法等。对于货物需求量为随机参数的情

9、况，建模求解更加困难，我们准备要做一些假设对随机性进行限定，在此基础上给出模型和处理方法。三 基本假设（1）文中所有数据来源真实可靠；（2）不考虑塞车和运输车出现故障或事故对其运输量和时间的影响；（3）每辆车可以完成多项任务，但每项任务只由一辆车来完成；（4）每条路线必须起始于出发点，为最后一个客户服务完后返回出发点；（5）每条路线的总负荷不能超过该辆汽车的最大载重量；（6）每个客户必须在它的时间窗口内被服务，如果汽车提前到了客户所在地，也必须等待，直到允许为该客户服务为止；（7）车辆的行驶时间与距离成正比，派送成本随着运送货物的路程的增加而增大；（8）车辆为同种车型；（9）假设时间窗为硬时间

10、窗。四 定义与符号说明-客户的编号（时代表中心仓库）-客户的个数-每辆车的最大容量-客户的货物需求量-允许车辆到达客户的最早时间-允许车辆到达客户的最迟时间-各项任务装货（或卸货）时间-车辆到达客户的时间-车辆从客户行使到客户所需的时间（数据见附表3）-客户到客户的距离-每辆车运送货物的过程中的速度，已知=50公里/小时-中心货仓拥有的车辆的数量（局部符号定义另行说明）五 模型的建立及求解5.1模型一（确定性规划模型）5.1.1 模型建立根据本问题的一系列的要求和约束，可知该问题是一个vrp问题，再加上每个任务都有时间上的限制，问题变成了vrptw问题，即带有时间窗的车辆路径问题。vrptw问

11、题就是为中心仓库提供一个合理的安排车辆执行运送货物的方案，包括执行运送任务车辆的数量和车辆的行驶路线，使得中心仓库付出的派送费最小。据此，我们首先建立了vrptw问题的模型。定义变量：我们的目标为所有车辆行驶的总距离最短，故有如下目标函数：根据题意，我们得出以下各个约束：派出车辆的数目不能超过中心仓库所拥有的车辆数：车辆容量约束：确保车辆都是从中心仓库出发, 并回到仓库：保证每个客户只能被一辆车服务一次：时间窗的约束：故得到下面的数学模型：s.t.5.1.2 模型求解5.1.2.1 求解准备为了安排线路，需要预先对需要的车辆数进行估计，我们可以通过下面的式子来估计：代入数据，为了简化本题，下面

12、我们就默认，即只有三辆车来完成任务。从我们建立的模型来看，这是一个复杂的规划模型，如果用matlab或者lingo来求解的话，可能需要求解很长时间或者甚至求不出结果，虽然如此，我们也给出了lingo的求解程序，因为对于小规模问题而言，还是可以用精确算法求最优解的。但实际问题中，客户数可能多达几百，下面我们转向另外一种启发式算法经典的c-w节约算法。5.1.2.2 节约算法的基本原理12节约算法的基本思想是：首先将各个客户点与中心仓库相连，构成一条仅含一个客户点的送货路线，并计算总路程；然后计算将两个客户点连接在一条线路上的路程节约值，节约值越大，说明将两个客户点连在一起的总路程减少得越多，直到

13、节约值为0为止。如果在中心仓库的送货范围内还存在着其他的客户，在车辆载重和客户时间要求都允许的情况下，可按照节约路程的大小将他们依次地连入巡回路线，直到满载为止，这样，就组成了一条配送路线。然后以同样的方法进行第二条配送路线。很显然，这样每一次连接过程都能使总距离得到最大的节约，也就使行程增加值最小，最终使得运输线路得到优化。算法示意图见图5.1。图5.1 c-w节约算法示意图以表示连接后的路程节约值：以表示连接客户i和客户j所在线路后，车辆到达客户j的时间比原路线上车辆到达客户j的时间的推迟量（或提前量），可由下式得出：表示车辆到达客户的时间；表示各项任务的货运量（单位：吨）、装货（或卸货）

14、时间；表示车辆从客户行使到客户所需的时间。由上式可以看出，时，表示连接后到达客户j的时间不变；时，表示连接后到达客户j的时间提前了；时，表示连接后到达客户j的时间推迟了。为了讨论时间窗约束问题的方便，还需定义两个比较重要的参数：-车辆在线路上j点后面的各任务处均不需要等待的j点的到达时间的最大可以提前量；-车辆在线路上j点后面的各任务处不违反时间窗约束的到达j点的最大允许推迟量。定义如下：；.在考虑连接点i和点j所在的线路时，需要检查其是否符合时间窗的约束时，由上述定义可以看出，当时，若有，则车辆在j后面的任务处不需要等待，否则，就要等待；而当时，若有，则j后面的任务的执行是不会拖延的，否则，

15、就要延迟进行。5.1.2.3 节约算法的算法设计 根据上面的原理，设计详细的求解步骤如下： step1：计算点i和点j连接后的路程节约值s(i,j)，并将其定义为数组； step2：若s(i,j)的值均为0，则终止，否则，在数组s(i,j)内求出值为最大的那一项； step3：考察对应的(i,j)，若满足下述条件之一，则转step5，否则转下步； (1)点i和点j均不在线路上； (2)点i不在线路上，点j为线路的起点；(3)点i不在线路上，点j为线路的终点；(4)点i为一线路的终点，点j为另一线路的起点； step4：判断点i和点j的值是否已交换，若没有交换则转step3，否则转step8；

16、step5：计算连接点i和点j后线路的总运货量q，若，则转下步，否则转step8； step6：计算； (1)若，则转step7； (2)若，则计算，若，则转下步，否则转step8； (3)若，则计算，若，则转下步，否则转step8； step7：连接点i和点j，计算车辆到达各项任务的新时间，转下步； step8：将该s(i,j)的值赋0，转step2.下面我们用cw节约算法来求解题目中的算例：(1) 计算各点对间连接后的路程节约值s(i,j)例如，在计算点1和点2时，有：类似，其他点对的节约值计算结果如下表：表5.1 各点对间连接后的路程节约值s(i,j)(i,j)(5,7)(5,6)(3,

17、5)(5,8)(4,5)(1,5)(6,7)s(i,j)270230225205190190190(i,j)(4,7)(2,5)(2,7)(3,7)(7,8)(4,6)(1,7)s(i,j)17516014514514011590(i,j)(2,6)(3,6)(6,8)(1,3)(4,8)(1,6)(2,8)s(i,j)85858075706565(i,j)(3,4)(2,3)(2,4)(1,2)(1,4)(1,8)(3,8)s(i,j)6560503530205由于s(i,j)和s(j,i)是一样的，所以一共有个值。(2)构造线路：根据上表所示的s(i,j)的顺序，逐一考察对应的i-j，点对

18、之间连接过程如下表：表5.2 点对之间连接过程i-j两点位置连接否5-7非线路上5-76-5非线路上外点3-5非线路上外点8-5非线路上外点8-5-74-51-5其中一点为内点7-67-4外点非线路上点2-5一点为内点7-27-3外点非线路上点4-6不在线路上6-47-12-63-6外点非线路非线路6-8两起点1-3非线路3-14-82-81-64-3外点外点外点外点2-3非线路外点4-2非线路外点1-2非线路外点3-1-2由上表我们得到具体路线：表5.3 行车路线车辆编号行驶路径总路程10-8-5-7-091020-6-4-030-3-1-2-0进一步，我们来检验我们的解，由上表我们能够得到

19、到达每个客户的时间（表5.2的最后一列），我们把这些数据以及各个客户所允许的时间放在一张表上：表5.4 到达每个客户的时间及其时间窗客户号1234到达时间3.35.61.56时间窗1,44,61,24,7客户号5678到达时间3.527.71.6时间窗3.5,52,55,81.5,4每个客户都会被满足要求，其解比较令人满意。5.1.3 结果分析及模型修正通过以上的车辆的行驶路径方案观察发现，所有的车辆都是在送完获后直接回到中心仓库，但是若不规定车辆送完货后就直接回到中心仓库，则车辆在回去的过程中可能绕过某个客户回去更近。采用组合策略的floyd算法可以求出各点间的最短行驶距离（程序见附录），具

20、体可见下表：表5.5 各点间最短行驶距离点号01234567800406075909010013580140065401005075110100260650751001007575753754075010050909012549010010010001007575100590501005010007090756100757590757007010071351107590759070010088010075125100751001000表2中两点间的最短距离可能不是直接到达的，有可能要经过其他的点，下表则给出了各个点间最短路径经过的中间点：表5.6 各个点间最短路径所经过的中间点点号012345

21、678000000102010000000002000000000300000000540000000005100000000600000000072000000008000500000上表中0表示这两点间直接行驶最近，数字则表示要经过的点号，如：上表中的5表示从3号点到8号点的最短行驶路径要经过5号点。根据以上表格中的数据我们可以求出一个更优的车辆行驶路径的安排方案：表5.7 改进的车辆的行驶路径安排方案车辆编号行驶路径总路程1号0-3-1-2-08852号0-6-4-03号0-8-5-7-2-05.2模型二（随机规划模型）5.2.1局部假设（1）所有客户是否需要服务事先已知，所有客户的实际

22、需求量必须到达用户后才能得知；（2）各客户的实际需求满足一定的离散概率分布，且分布函数已知，一旦发生路径失败，车辆返回站点释放容积后再按照原先顺序服务后续客户。5.2.2 局部符号说明有向图配送网络节点集,其中0为中心仓库； 客户 弧集第条计划路径,第条计划路径对应的节点集路径失败所导致的临时返回路径临时返回路径对应节点集临时返回路径的期望总长度节点需求量的随机变量 配送车辆，其中表示所需车辆数(其余符号沿用先前的)5.2.3 模型建立各客户需求满足同一概率分布，且已知概率分布为，并引入决策变量如下：则随机需求的带时间窗车辆路径问题的数学模型可以表示如下： (1)s.t. (2) (3) (4

23、) (5) (6) (7) (8) (9)其中式(1)为目标函数，目标函数包含两项，第一项为计划路径总长度，第二项为临时返回路径的期望总长度；式(2) (3)为访问唯一性约束；式(4)为中心仓库约束；式(5)为容积约束；式(6)为次回路消除条件；式(7)(8)(9)为时间窗约束。1)目标函数中的确定假设计划路径为下述形式的节点序列，在节点处发生“路径失败”，若节点处恰好达到车辆容积，则需要返回站点清空容积后开往继续计划路径，对应的临时返回路径长度为；若节点处超过了车辆容积，且不允许车辆非满载配送，则车辆清空容积后需要返回节点继续计划路径，对应的临时返回路径长度为。设表示节点处恰好达到容积的概率

24、，表示节点处超过容积的概率，则与路径对应的临时返回路径期望长度为，由此可进一步将前方模型中的所有节点的返回路径期望总长度改写为。2)和的确定假设用来表示车辆直至节点处刚好达到容积的概率，则可以下面用递归公式（1）（2）求得： （1） （2）其中表示节点的需求量。假设用来表示车辆直至节点处刚好达到容积的概率，类似的可以下面用递归公式（3）（4）求得： （3） （4）5.2.4 处理方法4由于随机性问题中用户的需求事先未知，因此对这一类问题的求解不能采用确定性问题的做法，比较常见的思路是首先将容积约束进行松弛，将vrptw问题退化为mtsptw问题进行求解，求得mtsptw问题的满意解作为计划路径

25、;然后按照计划路径的顺序求得各节点处的期望返回路径长度;最后通过邻域变换对mtsptw问题的满意解进行改进。六 模型的评价与推广1.模型一是解决vrptw的主流模型，能够较好地描述硬时间窗的情况。在解决算例后，我们还提出了最短路的修正。在物流配送中，有一定的参考价值。但硬时间窗始终比较理想化，我们应将其软化，早到和迟到都加上惩罚因子（相当于以一定的速度在路上跑），算入总路程，以新目标函数和软时间窗约束再进行优化。2.模型二解决带随机需求的vrptw。我们只给出了模型和求解方向。问题较复杂，没能完全解决。3.模型设定在单一物流配送中心、单一车种、单一商品条件下等条件下进行配送服务。而物流配送社会

26、化、共同化是其发展趋势，商品种类空前增加，实际中用户的时间窗也是不确定的，所以有必要研究多配送中心、多车种、多种商品和随机时间窗等条件下车辆路径优化问题的动态规划模型。4.就c-w算法而言，在计算机上容易实现、编程简单,易于调整,理念朴素、方法易行、效果理想等优点,并获得了最优解。在小规模的站点不太多的客户配送优化中,节约算法得到的解与精确最优解很接近,并且能够很快给出结果。但规模变大后，精度变差。这时可以选择人工免疫算法等更现代的方法。七 参考文献1 李军.有时间窗的车辆路线安排问题的启发式算法j.系统工程，1996.2 宋伟刚,张宏霞,佟玲.有时间窗约束非满载车辆调度问题的节约算法j. 东

27、北大学学报( 自然科学版)，2006.3 姜启源,等.数学模型（第三版）.北京:高等教育出版社,2003.4 马华伟.带时间窗车辆路径问题及其启发式算法研究,博士论文,合肥工业大学,2008.八 附录1.问题相关信息表1 任务的特征及其要求任务12345678（吨）21.54.531.542.53（小时）121322.530.81,44,61,24,73,5.52,55,81.5,4表2 点对之间的距离ij01234567800406075902001001608014006540100507511010026065075100100757575375407501005090901504901

28、00100100010075751005200501005010007090756100757590757007010071601107590759070010088010075150100751001000表3 点对之间车辆行驶时间ij012345678000.81.21.51.8423.21.610.801.30.8211.52.2221.21.301.5221.51.51.531.50.81.50211.81.8341.8222021.51.5254121201.41.81.5621.51.51.81.51.401.4273.22.21.51.81.51.81.40281.621.532

29、1.52202.精确算法的lingo程序model:sets:kehu/k0.k8/:time1,time2,xiehuo,q,t;car/car1.car3/;drive(kehu,kehu):time,distance;plan(kehu,kehu,car):x;endsetsdata:time1=0 1 4 1 4 3.5 2 5 1.5;time2=15 4 6 2 7 5 5 8 4;xiehuo=0 1 2 1 3 2 2.5 3 0.8;q=0 2 1.5 4.5 3 1.5 4 2.5 3;distance=040607590200100160 8040065401005075

30、110100606507510010075757575407501005090901259010010010001007575100200501005010007090751007575907570070100160110759075907001008010075150100751001000;time=0 0.8000 1.2000 1.5000 1.8000 4.0000 2.0000 3.2000 1.60000.8000 0 1.3000 0.8000 2.0000 1.0000 1.5000 2.2000 2.00001.2000 1.3000 0 1.5000 2.0000 2.0000 1.5000 1.5000 1.50001.5000 0.8000 1.5000 0 2.0000 1.0000 1.8000 1.8000 2.50001.8000 2.0000 2.00