改进的蚁群优化的动态多车场车辆路径问题
动态车辆路径问题（DVRP）单一车场的已经受到工程师和科学家越来越多的关注。但是，动态多车场车辆路径的问题（DMDVRP）的延伸DVRP，一直没有受到重视。在我们的文章中，基于距离的聚类方法通过分配每个客户到其最近的车场的方式引入到简化的DMDVRP。因此，DMDVRP被分解成序列的DVRPs。在本文中改进的蚁群优化（IACO）的蚂蚁策略和变异操作提出了优化车辆路径问题（VRP）。此外，为了满足实时功能的DMDVRP，最近添加法是用来处理在发生的新订单VRP问题的解决方案的基础上的某个时间片段。最后，计算的17个基准问题报告给验证IACO基于距离的聚类方法更适合解决DMDVRP。
关键词：动态多车场车辆路径问题;基于距离的聚类方法;蚁群优化;最近添加法
1.引言
在过去的50年中，已经有很多的研究（1993年奥斯曼雷诺，拉波特，1996年Boctor Bullnheimer ，哈特尔和施特劳斯1999年，2004年贝尔和麦克马伦;俞，阳，和姚明2009年）车辆路径问题（VRP ）或多车场车辆路径问题（MDVRP ）。许多聚类技术应用于分成几个较小的VRP的问题分解VRP / MDVRP的（比安斯托克，布拉梅尔，辛奇- 利维1993 ;栋多和2007年CERDA ;甚和Narendran2007年，金，刘，2007年和鲍登; Sáez研究，科尔特斯，2008年和努涅斯）。在古典VRP / MDVRP的中，客户的需求/地点一般都假设为已知和确定性。然而，在实践中，VRP / MDVRP的问题是动态的，不确定的。随着国民经济的快速发展的新信息和通信技术在交通运输系统中，越来越多的关注专注于动态车辆路径问题（DVRP ）。近年来，一些研究者研究动态单车场VRP 。
Savelsbergh和Sol （1998）提出了一个动态路径自主车型的问题，其重点是一个分支和价格的算法。根德罗和波特凡（1998）在调度面积的基础上划分的本地动态车辆调度系统和宽动态车辆调度系统。flatberg等（2007）动态随机VRP和提出求解器。拉森（2000年）之间的差异静态和动态VRPS及讨论还提供了一些例子和现实生活中的例子DVRP以及目前的状态各种DVRP方法。弗莱希曼Gnutzmann ，Sandvob （2004）的出动车辆根据随机到达客户的订单规划期间上线的基础信息。更多在不同类型DVRPs上最近的调查如下：的根德罗波特凡（1998），生产间隔（1995年），富兰克林和比阿特丽斯（2007年），Montemanni等。（2005）Ichoua ，根德罗，波特凡（2000年）。然而，正如我们都知道，很少有几个研究多车场DVRP 。因此，本文着重对动态多车场车辆路径问题（DMDVRP ）。
我们假设在DMDVRP，而一些新的，一些客户的要求是事先知道客户的要求是不可用的。在DMDVRP，在有限的时间找到一个令人满意的解决方案是显著的。一般来说，DMDVRP自然已被确认为更为复杂的由于嵌入式VRP。这是一个可行的办法，改变DMDVRP成为几个DVRPs。在本文中，基于距离的聚类方法是用来根据车场数量分割成几套客户。其结果是，每个车场和对应的客户可以被认为作为DVRP。这可以大大减少的计算复杂DMDVRP。然而，经过简化，DVRPs仍难以确切的方法解决，因为一直DVRP被确认为一个非确定性多项式（NP-hard的）问题。
对于DVRP，一个两阶段的方法被发展起来。在第一阶段中，现有的客户（不带首先优化考虑立即请求）。由于许多研究人员表示启发式算法适合解决VRP问题，所以改进蚁群优化（IACO）可以被应用在优化或重新优化VRP路径。在第二阶段中，最近添加方法来处理发生在某个时间片段的动态请求。
本文的其余部分组织如下。第二节中,我们描述了DMDVRP。第三节提出了如何简化DMDVRP和后续的如何解决VRP。第四部分是处理动态问题的基于最近添加方法。一些计算基准问题的结果讨论了第五节和最后,结论是提供在第六节。
2.动态多车场车辆路径问题
一个DMDVRP能够描述为用最少的总成本从各车场到最新顾客的设计路线的问题。由于出现计划外的客户，每个客户在货物交付前进行充满单一种类的货物的车辆调度。因此，当新订单到达交付过程中，车辆可以调整其路线，挑选一些新订单如果车辆能满足新的客户。在我们的战略中，第一，优化运输路线基于当前客户DMDVRP 。虽然新的即时收到请求，现有路线需要改变，需要创建一个新的路线来处理它们。这意味着线路应重新优化，同时考虑新的要求（2000年拉森富兰克林和比阿特丽斯2007年）。图1给出了一个DMDVRP例子。如图所示，已知的客户为代表的白色节点，而眼前的新的请求被描绘成黑色节点。初步路线设计来服务于客户的订单，被称为提前（图1（a ））。由于新客户订单到达时，可以改变一些定期路线，以满足新的请求（图1（b ））。
在数学上，设G=（C*，L）是一个图，C *为顶点集（*表示标'D'或C）代表的车场（CD= {C1，C2，...}）或客户（CC={C1，C2，...}），和L是边缘的距离（L ={LCI*，CJ，CI *，CJ*∈C *}）。因此，MDVRP包括构造（2）这样一种方式，在车辆路线的一组：（1）每条路径的开始和结束在同一车场;每个顾客被访问一次，由车辆和（3）各条路线的总需求不超过车辆容量V。
3.DMDVRP简化和VRP算法
在本节中，DMDVRP将被分解为几个DVRPs通过基于距离的簇散射方法简化。然后，要解决静态VRP，IACO蚂蚁重策略变异操作将会推出。
3.1基于距离的聚类方法
一般来说，解决DMDVRP需要更多的计算时间。由于实时特征动态VRP，
它是合理的解决方案的算法，实现了加速收敛可行的解决方案，而不是最优的。因此，基于距离的聚类算法介绍简单地分配每个客户到其最近的车场（图2）。因此，DMDVRP被分解到序列DVRPs的，整个服务区域被在图2中所描述的直线划分成若干部分。
3.2 VRP问题的IACO
简化的DMDVRP的可以被认为几个DVRPs。因此，元启发式方法可能适用于DVRP被用来解决DMDVRP的。可以看出，在更多DVRP的引入其他一些研究人员的论文（Montemanni等，2005年，2007年富兰克林和比阿特丽斯）。在我们的战略中，应设计最佳路线为目前的客户在新的请求发生前，即首先要解决的VRP。因此，蚂蚁的重量战略和IACO变异操作（IACO）被提出解决VRP。
ACO是由意大利研究人员多里戈，Maniezzo最近提出的优化方法，科洛尔尼（1996年）。ACO模拟寻求食物在自然界蚁群行为。它已有成功应用于一些经典的复合优化问题，例如：旅行业务员，车辆，电信路由，路由产品设计的问题，等等。IACO本研究中提出如下。
3.2.1节点过渡规则
蚂蚁从一个节点移动到另一个节点基于概率规则兼顾的可见度和信息素的信息。对于第k个蚂蚁在第i个节点的概率选择节点j作为下一个站由下式描述：
PIJ（k）是选择节点j作为下一个站，由第k个蚂蚁离开时的概率节点i;τij是边（i，j）的信息素密度;ηij是边（i，j）条的可见性，α和β分别是相对影响信息素和能见度值; h为后续的可行的节点，节点i;tabuk是不可行的节点（包括那些已经访问过的集合）为第k个蚂蚁离开节点i，H∈tabuk
3.2.2变异操作
变异操作的遗传算法的一个重要步骤，用于生成新的解决方案基于父代解决方法。这是一个有效的方式变异操作提高ACO（于和杨，2011）。在他们的建议的变异操作的交流是完全随机的。在本文中，变异操作被视为达成进一步的解决方案搜索空间一种有效的方式。根据距离的聚类方法，交换客户部分随机的方法，即变异操作可以进行变异操作在来自同一车场开始的路线之间进行。
在图1（a）中的车场C1，作为父代的解决方案的情况下，将被视为一个例子来描述的突变操作过程（图3）如下：
步骤1：选择路线从父代中，然后从选定参观变异节点随机选择之一。图3所示，在节点C4是随机选择的。
步骤2：随机选择另一个路线从同一父代的解决方案，然后选择这次路线的节点上。然而，这个时候，选择这个节点不应该是任意的，而是确保所选的两个节点交换时，双方车辆的能力分别还是可以的满足新路线。在同一时间，在第二个节点的选择是有关于信息素的密度和边缘之间的可见性在前一个/下一个的节点两个节点之间。
步骤3：所选择的两个节点使子代解决方案产生（图4）。为了确保子代的解决方案，2-选择方法（奥斯曼1993; Bullnheimer的，哈特尔局部最优，和施特劳斯1997 Bullnheimer，哈特尔和施特劳斯1999年，2004年贝尔和麦克马伦俞，阳，和姚明2009）被应用于发生变异操作时。以这种方式，结果的变异操作将是局部最优，以提高子代解决方案。
如遗传算法中所述，变异操作可以探索蚁群算法的搜索空间。然而，由于操作降低了ACO的收敛性，本变异操作不应该被使用得很频繁。在一般情况下，病毒的突变率在算法开始时是大的，后减小在算法开始执行后。t代的突变率可确定根据概率规则如下。
pm (t) = pmin + (pmax ? pmin )1+(t?1)/T ,mmm
其中Pmax和Pmin是突变率的下限和上限，并分别是开头和结尾，单位毫米。T和t：预定的最大世代数和当前生成的迭代数。
根据初步测试，我们建议设置低突变率Pmin =1/nc的，nc是客户的数量，和上层的突变率pmax=1/nv，nv为它们量的该方案中的路线。
3.2.3 信息素信息的更新
信息素的更新的ACO和自适应学习技术是一个关键的因素和未来解决方案的改进。根据该解决方案的目标函数值更新信息素，这是可以做到与以下信息素更新方程：
τijnew链路（i，j）的更新信息素，τij是在更新前链路上的信息素（I，J），ρ是控制蒸发速度的常数，k表示第k个路线，其中包括链路（i，j）；M是在解决方案中的路线的总数，M> 0且kτij链路（i，j）的第k个蚂蚁发现的路线信息素增加。
在这项研究中，蚂蚁的重量策略（杨羽和2007年郑俞，阳，2012年，李，俞等人。2012）是用于分配信息素的增加，这需要考虑全球和本地信息。具体而言，信息素增量的计算方法：
式中，Q是一个常数，L是在解决方案中的所有路线的总长度，即L=介电常数，Dk是长度的解决方案中的第k个路线; DIJ链路（i，j）的长度; MK的客户数量在第k个路线且mk>0。
在蚂蚁的重量战略，解决方案中的每条路径上的信息素增量总额是Q/ L。此外，路线的各个环节都涉及到信息素增量的链接路线的贡献值，即链路的信息素增量等于（I，J）（DK - DIJ）/（MK×DK）。该参数进一步以一个例子解释，如图5所示。以这种方式，有效的信息从以前的搜索得到进一步寻找一个更有利的区域，可以保留这有助于加快算法的收敛性。
此外，以避免局部优化和放大获得更高质量的概率解决方案中，上限和下限[τmin，τmax]固定到更新方程。
其中d0i是从中心车场到第i个客户的距离。
4.对动态需求的最近添加法
在我们的战略中，一个工作日分成长度相等的片段。订单发生在某个时间片，通过N= {N1，N2，...}表示，并处理结束时的时间片段。显然，当引入新的客户到初始解时，总距离将增加。因此，最近添加法的引入解决了动态请求。用最少的加入为的新客户的方法是找到新路线距离对比初始路线。将程序来处理新订单用一个例子来解释如下。
图6描述车场C1D为交付任务分配了三辆车。第i个时间片段，客户C1，C3，C9和C10已经被服务，客户一直C4，C6，C7，C8和C12等待服务。在这种情况下，车辆分别在客户C2，C5和C11。新的订单在发生在第i个时间片段被黑色点（N1和N2）表示的时候。处理新订单的步骤如下：步骤1：在所有的车辆中选择可用的车辆。首先，每辆车额外的容量的计算后的车辆为所有的预先计划的客户。如果额外的货物的车辆能够满足新的秩序，车辆对于新客户是可行的。一般来说，如果新订单是循环到达的，它更容易被纳入预先计划的路线。否则，有一些车辆，要满足新的秩序需求。如果全部出动车辆不能满足新的客户，新的车辆可以从车场派遣来处理新的订单。例如，在C2的车辆和C5带有额外货物的可行车辆，在C11的车辆没有多余的货物服务新客户。
步骤2：构建可行的路线。在此步骤中，新客户N1和N2被添加到每个当前路线。图7示出了4个可行的解决方案。请注意，只有一个客户添加到每次的初始路线。
步骤3：确定最佳路线。在每个可选路线的距离计算由下式：
当添加一个新的客户路线，1表示初始添加的距离。LCI*，NK，LNK，CJ*和LCI* CJ*代表两个节点之间的距离。CI*和CJ*初始路径中的相邻节点，Nk 为新客户设定的N.例如，在图7（a）中车辆运行从C2到C4，但它改变其最初的路线服务新客户N1，并且因此，被增加的距离为LC2，N1+ LN1，c4 - LC2，c4。最小的路线中可以找到另外的距离，根据计算，然后将被更新路线。在这个例子中，计算的结果是，该车辆C2供应新的顺序N1（图8）。
第4步：重复步骤1-3把其他的新订单放到新的路线。在这个例子中，假设两个上面使用的车辆（车辆在C2和C5）仍可满足N2。该可行的解决方案和最优的方案如图9（a），图9（b）和图10中所示。
最优方案
5. 数值分析
一些基准问题上，本节专门的算法实验评价这都源于一些非常流行的静态MDVRP基准问题的标记问题（赫里斯托菲和埃隆1969年，吉列和约翰逊1976年）。这些测试的主要特点问题总结于表1，其中，H，N，V，分别表示车场的数目，客户的数量和车辆的容量。
许多参数在DMDVRP首先需要专门设置。工作一天划分进入NTS片段。如果我们定义T作为工作日，每次的长度的长度片段等于T/ NTS。富兰克林和比阿特丽斯（2007）建议设置参数NTS24八小时工作制是可以接受的。IACO 的参数与基于距离的聚类的方法（IACO-C表示）用于DMDVRP实例的Q =1000，α= 2，β= 1和ρ=0.8。在每个基准问题中，随机选择了30％的客户作为新的客户。在这个过程中随机出现的每一个新的客户。为了得到可靠结果，每个基准的问题是由计算机设置为运行20次。平均运行时间和每个问题的平均计算结果示于表1-3中。拟议的启发式编码在Visual C ++。NET 2003，在PC机上配备了512 MB的RAM和执行奔腾处理器运行在1000 MHz。
为了评估性能在本文中提出的战略，构建两个测试。首先，蚂蚁的重量策略和变异操作的性能进行测试。其次，基于距离的聚类方法的性能进行了验证。蚁群的蚂蚁重量本文提出的战略和变异操作IACO表示。IACO的比较结果和标准蚁群优化（ACO），ACO与蚂蚁的重量战略（ACO-W表示）以及ACO与变异操作（ACO-M所表示的）中给出于表2。黑体类型中的数字代表的最优之间的四则运算法则。它可以观察到的解决方案和四种算法的计算时间几乎是相同的为
解决一些简单的问题，如测试问题1-3。然而，随着越来越多车场或客户，解决方案和四种算法的计算时间数往往会变得不同。
与ACO相比，其他三个ACOS总是可以有不同的改进策略提供更好的解决方案。ACO- W和IACO计算时间也小于ACO 。这表明，蚂蚁的重量策略和变异操作可以提高性能ACO 。此外，人们可以发现，ACO -W具有良好的收敛速度，同时ACO –M是一个很好的解决方案。这是因为，进行变异操作可以分散可能的解决方案空间和防止局部优化。其结果是，变异操作的改进的解决方案，但它增加了计算时间。然而，蚂蚁的策略（重量），这是用于更新每个边缘到该解决方案中的贡献增加的信息素，可以提高过去的搜索算法的学习能力，提高了工作效率。此外，正如预期，IACO结合蚂蚁的重量和变异操作提供最佳解决方案和消耗相对较少的计算时间。
另外，在上述的试验中，11个问题的计算时间超过2分钟，尤其是，第8，9日，10日和11日的问题。因此，减少大规模的问题的计算时间是必要的。表3展示出基于距离的聚类ACO方法的ACO的计算结果，即基于距离的聚类方法的ACO（ACO-C表示），基于距离的聚类方法的ACO-W（记ACO-W-C），基于
距离聚类方法的ACO-M（ACO-M-C表示）和基于距离的聚类方法的IACO （IACO-C表示）。
很明显，基于距离的聚类方法的引入可以大大减少计算时间。然而，它也恶化了解决方案。与表2中的结果相比，ACO-C，ACO-W-C，ACO-M-C和IACO-C 的计算时间分别降低56.7％，60.2％，54.6％和60.1％。同时，ACO-C，ACO-W-C，ACO-M-C和IACO-C计算出的长度分别增加1.0％，0.8％，0.5％和0.6％。
实时功能在DMDVRP是非常重要的。因此，虽然IACO的解决方案是优于IACO - C ，IACO实际上是不适合的。这是因为客户车辆不能等待很长一段时间，特别是出现8日，9日，10日和11日的问题。为了进一步验证算法的性能与基于距离的权衡聚类方法，我们添加一个绑定IACO和IACO - C ，其中每个时间步长不能超过120秒。特别是，如果一个时间步不能完成优化在120秒内，最好的解决办法过程中发现最佳的时间步长，然后开始下一步。其结果列于表4。可以观察到，IACO较好的解的质量与客户或车场增加的数量下降。这表明，IACO不适合于实时服务，如DMDVRP 。同时，可以观察到，IACO - C总是执行优于IACO ，特别是当存在限制的时候对于大量的被测试的客户计算时间的问题。正如预期，IACO基于距离的聚类方法，可以确保更好的优化。
6结论
DVRP一直是物流领域中的重要问题。由于嵌入VRP的DVRP和新订单必
须动态地纳入一个不断发展的时间表，它属于NP难问题。因此，嵌入DVRP的DMDVRP是更难以解决的问题。在本文中，基于距离的聚类方法是先用于在几个车场的基础上将总客户分成几组。然后，DMDVRP可以被认为是一个序列的DVRPs。带有蚂蚁重量的策略和变异操作的IACO用于解决VRPS。然后最近添加法是将新订单用于初始路线。最后，17个基准问题的基础上进行计算的研究之间的比较建议IACO和其他蚁群算法。结果表明，IACO基于距离的聚类方法是适合求解DMDVRP。
学年论文之 家乐福超市物流配送路线优化 专业物流工程 班级 姓名 学号 日期
在物流配送业务中，合理确定配送路径是提商服务质量，降低配送成本，增加经济效益的重要手段。物流配送系统中最优路线的选择问题一直都是配送中心关注的焦点，针对当前家乐福物流配送体系不完善等方面的现状，本文从可持续发展的角度，用系统的观念，来研究家乐福物流配送体系，优化配送路线，使配送体系合理化。 通过对家乐福超市现有物流配送路径的分析研究，发现其中存在的一些问题，并由此提出解决办法，结合背景材料，建立了数学模型，运用遗传算法对家乐福物流配送路线进行优化选择，并得出结果。由此可见，家乐福超市原有的物流配送路线还可以进行再优化，从而达到运输成本最小化的目标。 关键词：物流配送；路径优化；节约里程算法
1.绪论 (1) 1.1选题目的和意义 (1) 1.2国内外物流配送路线优化研究现状 (2) 2. 家乐福超市配送路线现状 (3) 2.1家乐福超市概况 (3) 2.2家乐福超市配送路线作业现状 (4) 2.2.1 配送距离分析 (4) 2.2.2 车辆数分析 (5) 2.2.3 需求量分析 (6) 2.2.4 商品品种分析 (6) 2.3家乐福超市配送现有路线问题分析 (7) 3.配送路线优化建模与求解 (9) 3.1研究对象目标设定 (9) 3.2模型的构建 (11) 3.3节约算法 (12) 3.3.1节约算法的基本原理 (12) 3.3.2节约里程算法主要步骤 (13) 3.3.3基于节约算法的配送路线优化 (13) 3.3.4优化后的配送线 (24) 4.优化结果分析 (25) 4.1优化前结果 (25) 4.2优化后结果 (25) 4.3结论 (26) 5.总结与建议 (27) 参考文献: (28)
!""#$%%%&%%’( )#$$&***+,#清华大学学报-自然科学版. /012345678329-":2;0<:5.= *%%>年第(>卷第$$期 *%%>=?@A B(>=#@B$$ +C,+C $C(’&$C(D 车辆路径优化问题的均衡性 但正刚=蔡临宁=杜丽丽=郑力 -清华大学工业工程系=北京$%%%D(. 收稿日期E*%%’&%>&%F 基金项目E国家自然科学基金资助项目-F%*%$%%D. 作者简介E但正刚-$C F D&.=男-汉.=重庆=博士研究生G 通讯联系人E蔡临宁=副教授=H&I72A E:72A3J K1234567B
捕食搜索算法 动物学家在研究动物的捕食行为时发现，尽管由于动物物种的不同而造成 的身体结构的千差万别，但它们的捕食行为却惊人地相似.动物捕食时，在没有 发现猎物和猎物的迹象时在整个捕食空间沿着一定的方向以很快的速度寻找猎物.一旦发现猎物或者发现有猎物的迹象，它们就放慢步伐，在发现猎物或者有 猎物迹象的附近区域进行集中的区域搜索，以找到史多的猎物.在搜寻一段时间 没有找到猎物后，捕食动物将放弃这种集中的区域，而继续在整个捕食空间寻 找猎物。 模拟动物的这种捕食策略，Alexandre于1998提出了一种新的仿生计算方法，即捕食搜索算法(predatory search algorithm, PSA)。基本思想如下：捕食 搜索寻优时，先在整个搜索空间进行全局搜索，直到找到一个较优解;然后在较 优解附近的区域(邻域)进行集中搜索，直到搜索很多次也没有找到史优解，从 而放弃局域搜索;然后再在整个搜索空间进行全局搜索.如此循环，直到找到最优解(或近似最优解)为止，捕食搜索这种策略很好地协调了局部搜索和全局搜索 之间的转换.目前该算法己成功应用于组合优化领域的旅行商问题(traveling salesm an problem )和超大规模集成电路设计问题(very large scale integrated layout)。 捕食搜索算法设计 (1)解的表达 采用顺序编码，将无向图中的，n一1个配送中心和n个顾客一起进行编码.例如，3个配送中心，10个顾客，则编码可为:1一2一3一4一0一5一 6一7一0一8一9一10其中0表示配送中心，上述编码表示配送中心1负 贡顾客1,2,3,4的配送，配送中心2负贡顾客5,6,7的配送，配送中心3负贡顾 客8,9,10的配送.然后对于每个配送中心根据顾客编码中的顺序进行车辆的分配，这里主要考虑车辆的容量约束。依此编码方案，随机产生初始解。 (2)邻域定义 4 仿真结果与比较分析(Simulation results and comparison analysis) 设某B2C电子商务企业在某时段由3个配送中心为17个顾客配送3类商品，配送网络如图2所示。
石河子大学毕业论文 题目：节约里程法在新疆国美电器物流配 送路线优化中的应用研究 院（系）：商学院商务管理系 年级： 2008级 专业：物流管理 班级：物流2008（1）班 学号： 姓名：张露露 指导教师：李霞 完成日期： 2012年03月10日 目录 引言 ................................................................................................................................... 1.物流配送概述 ................................................................................................................. 1.1物流配送的概念 ....................................................................................... 1.2物流配送的功能 (3) 1.3物流配送路线优化的意义 (3) 2.新疆国美电器物流配送中心基本概况 (3) 2.1新疆国美电器简介 (3) 2.2新疆国美电器配送中心运作现状及现有路线分析 (4) 2.2.1现有配送路线概况 (5)
2.2.2现有配送路线中存在的问题分析 (6) 3.节约里程法在新疆国美电器物流配送路线优化中的应用研究 (7) 3.1建立VRP模型 (7) 3.1.1物流配送模型 (7) 3.1.2节约里程法的基本理论 (7) 3.1.3新疆国美电器物流配送中心VRP模型的建立 (9) 3.2模型求解 (9) 3.3配送路线优化 (10) 3.4配送路线优化前后比较分析及思考 (16) 3.4.1优化前后比较分析 (16) 3.4.2节约里程法的思考 (16) 4.新疆国美电器物流配送中心配送路线优化对策分析 (18) 4.1完善物流配送体系，加强物流运作标准化 (18) 4.2构建物流信息系统平台，降低配送成本 (18) 4.3合理安排配送排程，减少不必要的配送路线 (18) 4.4优化配送资源，提高物流配送效率 (19) 结束语 (20) 致谢 (21) 参考文献 (22) 摘要 配送作为物流活动中直接与消费者相连的环节，在企业的物流成本中，配送成本占了相当高的比例。配送线路安排的合理与否对配送速度、成本、效益影响很大，特别是多用户配送线路的确定更为复杂。 正确合理地安排车辆的配送线路，实现合理的线路运输，可以有效地节约运输时间，
系 统 管理学报 第１９卷 不同，文献［６］中１００，本文３０；③文献［６］中没有给出２０次求解中有多少次求得最优解，本文算法在软硬２种时间窗下，求得最优解的概率分别为９０％和７５％。由此可以看出本文算法具有较快的收敛速度和较高的稳定性。 表２实例ｌ。软时间窗下算法运行结果 第２个实例［６］，该问题有８个客户，顾客的装货或卸货的时间为Ｔｉ，一般将ｔ作为车辆的行驶时间的一部分计算费用，ｇｆ和［ｎ，，６ｉ］的含义同前，具体数据见表４。这些任务由仓库发出的容量为８ｔ的车辆来完成，车辆行驶速度为５０，仓库以及各个顾客之间的距离见表５。 ６），达到最优解的概率为８０％，其最终结果与文献［６］中相同最优解其费用值为９１０，对应的子路径
为（Ｏ一３一ｌ一２—０）、（Ｏ一６—４一Ｏ）、（Ｏ一８—５—７一Ｏ）。然而，文献 ［６］是在ｍａｘｇｅｎ＝５０、ｐｏｐｓｉｚｅ一２０的情况下，达到最优解的概率为６７％。这又说明了本文算法的有 效性。 表６实例２的算法运行结果 ４ 结语 尽管用带有子路径分隔符的自然数编码作为遗传算法解决ＶＲＰＴＷ问题的编码方式有其优点，但缺陷也是显而易见的，为了弥补该缺陷，本文去掉了 子路径中的分隔符，并采用Ｓｐｌｉｔ作为解码方式，就此设计了求解ＶＲＰＴＷ的遗传算法，并进行了数值试验的对比分析，试验结果表明，该算法是十分有
效的。参考文献 ＤａｎｔｚｉｑＧ，Ｒａｍｓｅｒ Ｊ．Ｔｈｅｔｒｕｃｋｄｉｓｐａｔｃｈｉｎｇｐｒｏｂｌｅｍ ［Ｊ］．Ｍａｎａｇｅｍｅｎｔ ｓｃｉｅｎｃｅ，１９５９，１３（６）８０一９１． 谢秉磊，李军，郭耀煌．有时间窗的非满载车辆调 度问题的遗传算法［Ｊ］．系统工程学报，２０００，１５ （３）２９０一２９４． 宋伟刚，张宏霞，佟玲．有时间窗约束非满载车辆调度问题的遗传算法［Ｊ］．系统仿真学报，２００５，１７ （１１）２５９３—２５９７． 刘诚，陈治亚，封全喜．带软时间窗物流配送车辆路径问题的并行遗传算法
》本文对在GIS（地理信息系统）环境下求解动态路径优化算法及相关技术 进行了研究。最短路径问题是网络分析中的基本的问题，它作为许多领域中选择 最优值的一个基本却又是一个十分重要的问题。特别是在交通诱导系统中占有重 要地位。本文分析了GIS环境下动态路径优化算法的特点，对GIS环境下城市 路网的最优路径选择问题的关键技术进行了研究和验证。 》考虑现实世界中随着城市路网规模的日益增大和复杂程度不断增加的情况，充分利用GIS 的特点，探讨了通过限制搜索区域求解最短路径的策略，大大减少了搜索的时间。 》另一方面，计算机技术的进步，地理信息系统(GIS)得到了飞速的发展。地理信息系统是采集、存储、管理、检索、分析和描述整个或部分地球表面与空间地理分布数据的空间信息系统。它是一种能把图形管理系统和数据管理系统有机地结合起来的信息技术，既管理对象的位置又管理对象的其它属性，而且位置和其它属性是自动关联的。它最基本的功能是将分散收集到的各种空间、非空间信息输入到计算机中，建立起有相互联系的数据库。当外界情况发生变化时，只要更改局部的数据，就可维持数据库的有效性和现实性[3][4]，GIS为动态路径优化问题的研究提供了良好的环境。目前GIS带动的产业急剧膨胀，已经应用到各个方面。网络分析作为地理信息系统最主要的功能之一，在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用[5]。文献[6][7]说明了GIS 在城市道路网中的应用情况。而路网分析中基本问题之一是动态路径优化问题。所谓动态路径，不仅仅指一般地理意义上的距离最短，还可以应用到其他的参数，如时间、费用、流量等。相应的，动态路径问题就成为最快路径问题、最低费用问题等。 》GIS因为其强大的数据分析功能、空间分析功能,已被广泛应用于各种系统中与空间信息有密切关系的各个方面.各种在实际中的系统如电力系统，光缆系统涉及到最佳、最短抢修等问题都可以折合到交通网络中来进行分析，故而交通网络中最短路径算法就可以广泛的应用于其它很多的最佳、最短抢修或者报警系统中去[5]。最短路径问题是GIS网络分析功能的应用。最短路径问题可分为单源最短路径问题及所有节点间最短路径问题，其中单源最短路径更具有普遍意义[9]。 》2.1地理信息系统的概念 地理信息系统（Geographical Information System,简称GIS）是一种将空间位置信息和属性数据结合在一起的系统，是一种为了获取、存储、检索、分析和显示空间定位数据而建立的计算机化的数据库管理系统（1998年，美国国家地理信息与分析中心定义）[4]。这里的空间定位数据是指采用不同方式的遥感和非遥感手段所获得的数据，它有多种数据类型，包括地图、遥感、统计数据等，它们的共同特点都有确定的空间位置。地理信息系统的处理对象是空间实体，其处理过程正是依据空间实体的空间位置和空间关系进行的[25]。地理信息系统的外在表现为计算机软硬件系统，其内涵却是由计算机程序和地理数据组织而成的地理空间信息模型。当具有一定地理学知识的用户使用地理空间分析非空间分析等处理工具输入输出GIS数据库信息系统时，他所面对的数据不再是毫无意义的，而是把客观世界抽象为模型化的空间数据。用户可以按照应用的目的观测这个现实世界模型的各个方面的内容，取得自然过程的分析和预测的信息，用于管理和决策，这就是地理信息系统的意义。一个逻辑缩小的、高度信息化的地理系统，从视觉、计量和逻辑上对地理系统在功能上进行模拟，信息流动以及信息流动的结果，完全由计算机程序的运行和数据的变换来仿真。地理学家可以在地理信息系统支持下提取地理系统各个不同侧面、不同层次的空间和时间特征，也可以快速地模拟自然过程演变成思维过程的结果，取得地理预测或“实验”的结果，选择优化方案，用于管理与决策[26]。 一个完整的GIS主要有四个部分构成，即计算机硬件系统、计算机软件系统、地理数据（或空间数据）和系统管理操作人员。其核心部分是计算机系统（硬件和软件），地理数据反映
一、车辆路径问题描述和建模 1. 车辆路径问题 车辆路径问题（Vehicle Routing Problem, VRP ）,主要研究满足约束条件的最优车辆使用方案以及最优化车辆路径方案。 定义：设G={V,E}是一个完备的无向图，其中V={0,1,2…n}为节点集，其中0表示车场。V ,={1,2,…n}表示顾客点集。A={(i,j),I,j ∈V,i ≠j}为边集。一对具有相同装载能力Q 的车辆从车场点对顾客点进行配送服务。每个顾客点有一个固定的需求q i 和固定的服务时间δi 。每条边（i,j ）赋有一个权重，表示旅行距离或者旅行费用c ij 。 标准车辆路径问题的优化目标为：确定一个具有最小车辆数和对应的最小旅行距离或者费用的路线集，其满足下列约束条件： ⑴每一条车辆路线开始于车场点，并且于车场点约束； ⑵每个顾客点仅能被一辆车服务一次 ⑶每一条车辆路线总的顾客点的需求不超过车辆的装载能力Q ⑷每一条车辆路线满足一定的边约束，比如持续时间约束和时间窗约束等。 2.标准车辆路径的数学模型: 对于车辆路径问题定义如下的符号： c ij ：表示顾客点或者顾客点和车场之间的旅行费用等 d ij ：车辆路径问题中，两个节点间的空间距离。 Q ：车辆的最大装载能力 d i ：顾客点i 的需求。 δi ：顾客点i 的车辆服务时间 m:服务车辆数，标准车辆路径问题中假设所有的车辆都是同型的。 R ：车辆集，R={1,2….，m} R i :车辆路线，R i ={0，i 1,…i m ,0},i 1,…i m ?V ,,i ?R 。 一般车辆路径问题具有层次目标函数，最小化车辆数和最小化车辆旅行费用，在文献中一般以车辆数作为首要优化目标函数，在此基础上使得对应的车辆旅行费用最小，下面给出标准车辆路径问题的数学模型。 下面给出标准车辆路径问题的数学模型。 对于每一条弧（I,j ）,定义如下变量: x ijv = 1 若车辆v 从顾客i 行驶到顾客点j 0 否则 y iv = 1 顾客点i 的需求由车辆v 来完成0 否则 车辆路径问题的数学模型可以表述为： minF x =M x 0iv m i=1n i=1+ x ijv m v=1n j=0n i=0.c ij (2.1) x ijv n i=0m v=1≥1 ?j ∈V , (2.2)
配送是指对局域范围内的客户进行多客户、多品种、按时联合送货活动。 配送活动是指根据一定区域范围内各个客户所需要的各个品种要求，对配送中心 的库存物品进行拣选、加工、包装、分割、组配、分装上车，并按一定路线循环 依次送达各个用户的物流活动。物流配送是供应链网络中一个重要的直接与消费 者相连的环节，是货物从物流节点送达收货人的过程。配送是在集货、配货基础上，按货物种类、品种搭配、数量、时间等要求所进行的运送，是“配”和“送”的有机结合。配送的实质是现代送货，是以低成本、优质服务为宗旨，是一种先进 的物流形式。 供应链网络的物流配送过程主要包括：从生产工厂进货并集结的集货作业； 根据各个用户的不同需求，在配送中心将所需要的货物挑选出来的配货作业；考虑配送货物的质量和体积，充分利用车辆的载重和容积的车载货物的配装及路线 的确定。随着供应链管理系统的集约化、一体化的发展，常将配送的各环节综合 起来，核心部分为配送车辆的集货、货物装配及送货过程。进行配送系统优化， 主要是配送车辆优化调度，包括集货线路优化、货物配装及送货线路优化，以及集货、货物配装和送货一体化优化。物流配送车辆优化调度，是供应链系统优化 中关键的一环，也是电子商务活动不可缺少的内容。对配送车辆进行优化调度， 可以提高供应链管理的经济效益、实现供应链管理科学化。
配送车辆优化调度实际上也就是车辆路径问题（V ehicle Routing Problem，简称VRP），是Dantzig和Ramse]80[于1959年提出来的，该问题被提出来之后， 很快就引起了运筹学、应用数学、组合数学、图论、网络分析、物流学、管理学、 以及计算机科学等学科专家和运输计划制订者的极大重视，成为了运筹学和组合 优化领域的前沿和研究热点问题。各学科专家对该问题进行了大量的理论研究及 实验分析，取得了很大的进展。 车辆路径问题是径旅行商问题（Travel Salesman Problem，简称TSP）衍生 而出的多路TSP问题，即为K-TSP。VRP的一般定义为]81[：对一系列送货点和 （或取货点），组织适当的行车路线，使车辆有序地通过它们，在满足一定的约 束条件下（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、 时间限制等），达到一定的目标（如路程最短、费用最少、使用车辆数最少等）。见图1。
摘要 供货小车的路径优化是企业降低成本,提高经济效益的有效手段,供货小车路径优化问题可以看成是一类车辆路径优化问题。 本文对供货小车路径优化问题进行研究，提出了一种解决带单行道约束的车辆路径优化问题的方法。首先，建立了供货小车路径优化问题的数学模型，介绍了图论中最短路径的算法—Floyd算法，并考虑单行道的约束，利用该算法求得任意两点间最短距离以及到达路径，从而将问题转化为TSP问题，利用遗传算法得到带单行道约束下的优化送货路线，并且以柳州市某区域道路为实验，然后仿真，结果表明该方法能得到较好的优化效果。最后对基本遗传算法采用优先策略进行改进，再对同一个供货小车路径网进行实验仿真，分析仿真结果，表明改进遗传算法比基本遗传算法能比较快地得到令人满意的优化效果。 关键字:路径优化遗传算法 Floyd算法
Abstract The Path Optimization of Goods Supply Car is the effective way to reduce business costs and enhance economic efficiency.The problem of the Path Optimization of Goods Supply Car can be seen as Vehicle routing proble. This paper presents a solution to Vehicle routing proble with Single direction road by Researching the Way of Path Optimization of Goods Supply Car. First, This paper Establish the mathematics model of Vehicle routing proble and introduced the shortest path algorithm-Floyd algorithm, then taking the Single direction road into account at the same time. Seeking the shortest distance between any two points and landing path by this algorithm,then turn this problem in to TSP. Solving this problem can get the Optimize delivery routes which with Single direction road by GA,then take some district in the state City of LiuZhou road as an example start experiment.The Imitate the true result showed that this method can be better optimize results. Finally improving the basic GA with a priority strategy,then proceed to imitate the true experiment to the same Path diagram. The result expresses the improvement the heredity calculate way ratio the basic heredity calculate way can get quickly give satisfaction of excellent turn the result. Keyword: Path Optimization genetic algorithm Floyd algorithm
粒子群优化算法 计算车辆路径问题 摘要 粒子群优化算法中,粒子群由多个粒子组成,每个粒子的位置代表优化问题在D 维搜索空间中潜在的解。根据各自的位置,每个粒子用一个速度来决定其飞行的方向和距离,然后通过优化函数计算出一个适应度函数值(fitness)。粒子是根据如下三条原则来更新自身的状态:(1)在飞行过程中始终保持自身的惯性;(2)按自身的最优位置来改变状态;(3)按群体的最优位置来改变状态。本文主要运用运筹学中粒子群优化算法解决车辆路径问题。车辆路径问题 由Dan tzig 和Ram ser 于1959年首次提出的, 它是指对一系列发货点(或收货点) , 组成适当的行车路径, 使车辆有序地通过它们, 在满足一定约束条件的情况下, 达到一定的目标(诸如路程最短、费用最小, 耗费时间尽量少等) , 属于完全N P 问题, 在运筹、计算机、物流、管理等学科均有重要意义。粒子群算法是最近出现的一种模拟鸟群飞行的仿生算法, 有着个体数目少、计算简单、鲁棒性好等优点, 在各类多维连续空间优化问题上均取得非常好的效果。本文将PSO 应用于车辆路径问题求解中, 取得了很好的效果。 针对本题，一个中心仓库、7个需求点、中心有3辆车，容量均为1，由这三辆车向7个需求点配送货物，出发点和收车点都是中心仓库。 1233,1,7. k q q q l =====货物需求 量12345670.89,0.14,0.28,0.33,0.21,0.41,0.57g g g g g g g =======， 且 m a x i k g q ≤。利用matlab 编程，求出需求点和中心仓库、需求点之间的各 个距离，用ij c 表示。求满足需求的最小的车辆行驶路径，就是求 m i n i j i j k i j k Z c x = ∑∑∑ 。经过初始化粒子群，将初始的适应值作为每个粒子的个
物流配送的车辆路径优化 专业：[物流管理] 班级：[物流管理2班] 学生姓名：[江东杰] 指导教师：[黄颖] 完成时间：2016年6月30日
背景描述 物流作为“第三利润源泉”对经济活动的影响日益明显，越累越受到人们的重视，成为当前最重要的竞争领域。近年来，现代物流业呈稳步增长态势，欧洲、美国、日本成为当前全球范围内的重要物流基地。中国物流行业起步较晚，随着国民经济的飞速发展，物流业的市场需求持续扩大。特别是进入21世纪以来，在国家宏观调控政策的影响下，中国物流行业保持较快的增长速度，物流体系不断完善，正在实现传统物流业向现代物流业的转变。现代物流业的发展对促进产业结构调整、转变经济增长方式和增强国民经济竞争力等方面都具有重要意义。 配送作为物流系统的核心功能，直接与消费这相关联，配送功能完成质量的好坏及其达到的服务水平直接影响企业物流成本及客户对整个物流服务的满意程度。配送的核心部分是配送车辆的集货、货物分拣及送货过程，其中，车辆配送线路的合理优化对整个物流运输速度、成本、效益影响至关重要。 物流配送的车辆调度发展现状 VRP（车辆调度问题）是指对一系列装货点和卸货点，组织适当的行车线路，使车辆有序的通过，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量等限制）下，达到一定的目标（如路程最短、费用最少、时间最少、使用车辆数最少等）。一般认为，不涉及时间的是路径问题，涉及时间的是调度问题。VRP示意图如下 当然，VRP并不止是这样的一个小范围，而是又更多的客户点与一个仓库链接，从而达
到一整个物流集群。 根据路径规划前调度员对相关信息是否已知，VRP可分为静态VRP和动态VRP，动态VRP 是相对于静态VRP而言的。静态VRP指的是：假设在优化调度指令执行之前，调度中心已经知道所有与优化调度相关的信息，这些信息与时间变化无关。一旦调度开始，便认为这些信息不再改变。 而VRP发展到现在的问题也是非常突出的，例如，只有一单货物，配送成本远高于一单的客户所给的运费，在这种情况下，该如何调度车辆？甚至还有回程运输的空载问题，在这些问题之中，或多或少都涉及到了VRP的身影，那么在这样的配送中怎么有效的解决车辆的路径优化问题就是降低运输和物流成本的关键所在。 解决怎么样的问题？ 现如今对于VRP研究现状主要有三种静态VRP的研究、动态VRP的研究以及随机VRP的研究。 而我对于VRP的看法主要有以下几点。 有效解决VRP或者优化车辆调度路径优化问题，那么将非常有效的降低物流环节对于成本的比重，有效的增大利润。 而我想到的方法，就是归类总结法。 建立完善的信息系统机制，将订单归类总结出来，可以按地区划分出来，一个地区一个地方的进行统一配送，这样也有效的降低了物流配送的车辆再使用问题，降低了成本。如下图所示。 仓库 客户 变换前 由上图可以看出来这样的路径，车辆需要来回两次，严重增加了配送成本，也增加了运输成本，使得利润并不能最大化。
物流车辆路径算法的优化与设计 【摘要】：随着物流业向全球化、信息化及一体化发展，配送在整个物流系统中的作用变得越来越重要。运输系统是配送系统中最重要的一个子系统，运输费用占整体物流费用的50％左右，所以降低物流成本首先要从降低物流配送的运输成本开始。 一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所装载货物不能超过它的容量。起初车辆都在中心点，顾客在空间任意分布，车把货物从车库运送到每一个顾客（或从每个顾客处把货物运到车库），要求满足顾客的需求，车辆最后返回车库，每个顾客只能被服务一次，怎样才能使运输费用最小。而顾客的需求或已知、或随机、或以时间规律变化，这正是本文要研究的课题。 【关键词】：物流配送；路径；车辆路径问题(VRP)；MATLAB 1 前言 1.1 课题研究背景 运输线路是否合理直接影响到配送速度、成本和效益，特别是多用户配送线路的确定是一项复杂的系统工程。选取恰当的车辆路径，可以加快对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商运作成本。因此，自从1959年Danting和Rams er提出车辆路径问题(Vehicle Routing Problem，VRP)以来，VRP便成为近年来物流领域中的研究热点。 VRP一般定义为：对一系列发货点和／或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定的目标(如路程最短、费用最小、时间尽量少、使用车辆尽量少等)。本文围绕VRP展开了研究，共包括五章内容。首先，本文收集国内外关于
用ACO 算法求解机器人路径优化问题 4.1 问题描述 移动机器人路径规划是机器人学的一个重要研究领域。它要求机器人依据某个或某些优化原则(如最小能量消耗，最短行走路线，最短行走时间等)，在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。机器人路径规划问题可以建模为一个有约束的优化问题，都要完成路径规划、定位和避障等任务。 4.2 算法理论 蚁群算法（Ant Colony Algorithm，ACA），最初是由意大利学者Dorigo M. 博士于1991 年首次提出，其本质是一个复杂的智能系统，且具有较强的鲁棒性，优良的分布式计算机制等优点。该算法经过十多年的发展，已被广大的科学研究人员应用于各种问题的研究，如旅行商问题，二次规划问题，生产调度问题等。但是算法本身性能的评价等算法理论研究方面进展较慢。 Dorigo 提出了精英蚁群模型（EAS），在这一模型中信息素更新按照得到当前最优解的蚂蚁所构造的解来进行，但这样的策略往往使进化变得缓慢，并不能取得较好的效果。次年Dorigo 博士在文献[30]中给出改进模型（ACS），文中 改进了转移概率模型，并且应用了全局搜索与局部搜索策略，来得进行深度搜索。 Stützle 与Hoos给出了最大-最小蚂蚁系统（MAX-MINAS），所谓最大-最小即是为信息素设定上限与下限，设定上限避免搜索陷入局部最优，设定下限鼓励深度搜索。 蚂蚁作为一个生物个体其自身的能力是十分有限的，比如蚂蚁个体是没有视觉的，蚂蚁自身体积又是那么渺小，但是由这些能力有限的蚂蚁组成的蚁群却可以做出超越个体蚂蚁能力的超常行为。蚂蚁没有视觉却可以寻觅食物，蚂蚁体积渺小而蚁群却可以搬运比它们个体大十倍甚至百倍的昆虫。这些都说明蚂蚁群体内部的某种机制使得它们具有了群体智能，可以做到蚂蚁个体无法实现的事情。经过生物学家的长时间观察发现，蚂蚁是通过分泌于空间中的信息素进行信息交流，进而实现群体行为的。 下面简要介绍蚁群通过信息素的交流找到最短路径的简化实例。如图 2-1 所示，AE 之间有
第２９卷第４期２００８年４月 东北大学学报（自然科学版） ＪｏｕｒｎａｌｏｆＮｏｒｔｈｅａｓｔｅｒｎＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅ） Ｖ０１．２９．Ｎｏ．４ Ａｐｒ．２００８动态车辆路径问题的优化方法 刘士新，冯海兰 （东北大学流程工业综合自动化教育部重点实验室，辽宁沈阳１１０００４） 摘要：设计了在动态环境下进行车辆路径优化的导向局域搜索算法．算法在产生初始解以后的动态求解过程中，不再做车辆之间的顾客调整，而只应用２－ｏｐｔ局域搜索算子更新车辆服务顾客的顺序，即针对每辆车辆的旅行路线求解一个旅行商问题．建立了在动态环境下车辆执行运输任务过程的仿真模型．仿真过程中，应用算法根据交通路网实际情况实时优化车辆路径。并采用４种接受准则判别是否接受新的车辆路径．仿真结果表明：算法具有实时、高效的特点，满足动态车辆路径问题的求解要求． 关键词：智能交通系统；动态车辆路径问题；交通模拟；导向局部搜索 中图分类号：Ｃ９３４文献标识码：Ａ文章编号：１００５—３０２６（２００８）０４—０４８４—０４ ＯｐｔｉｍｉｚａｔｉｏｎＡｐｐｒｏａｃｈｔｏＳｏｌｖｉｎｇＤｙｎａｍｉｃＶｅｈｉｃｌｅＲｏｕｔｉｎｇＰｒｏｂｌｅｍｓ Ｌ儿，Ｓｈｉ．ｘｉｎ，ＦＥＮＧＨ．口ｉ—ｌａｎ （ＫｅｙＬａｂｏｒａｔｏｒｙｏｆＩｎｔｅｇｒａｔｅｄＡｕｔｏｍａｔｉｏｎＤｆＰｒｏｃｅｓｓＩｎｄｕｓｔｒｙ，ＭｉｎｉｓｔｒｙｏｆＥｄｕｃａｔｉｏｎ，ＮｏｒｔｈｅａｓｔｅｒｎＵｎｉｖｅｒｓｉｔｙ，Ｓｈｅｎｙａｎｇ１１０（）０４，Ｃｈｉｎａ．Ｃｏｒｒｅｓｐｏｎｄｅｎｔ：ＬＩＵＳｈｉ—ｘｉｎ，Ｅ－ｍａｉｌ：ｓｘｌｉｕ＠ｍａｉｌ．ｎｅｕ．ｅｄｕ．ｃｎ） Ａｂｓｔｒａｃｔ：Ａｇｕｉｄｅｄｌｏｃａｌｓｅａｒｃｈ（ＧＬＳ）ａｌｇｏｒｉｔｈｍｉｓｐｒｅｓｅｎｔｅｄｔｏｓｏｌｖｅｄｙｎａｍｉｃｖｅｈｉｃｌｅｒｏｕｔｉｎｇｐｒｏｂｌｅｍｓ（ＤＶＲＰ）．Ｉｎｔｈｅｄｙｎａｍｉｃｓｏｌｖｉｎｇｐｒｏｃｅｓｓａｆｔｅｒａｌｌｉｎｉｔｉａｌｓｏｌｕｔｉｏｎ，ｔｈｅＧＬＳｄｏｅｓｎｏｔｅｘｃｈａｎｇｅｃｕｓｔｏｍｅｒｓｂｅｔｗｅｅｎｖｅｈｉｃｌｅｓｂｕｔａｐｐｌｉｅｓｔｈｅ２一ｏｐｔｌｏｃａｌｓｅａｒｃｈｏｐｅｒａｔｏｒｔｏｕｐｄａｔｉｎｇｔｈｅｓｅｒｖｉｃｉｎｇｓｅｑｕｅｎｃｅｆｏｒｃｕｓｔｏｍｅｒｓ，ｉ．ｅ．，ｔｏｓｏｌｖｅａｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍｏｆｔｒａｖｅｌｉｎｇｒｏｕｔｉｎｇｏｆｅａｃｈｖｅｈｉｃｌｅ。Ａｓｉｍｕｌａｔｉｏｎｍｏｄｅｌｉｓｔｈｕｓｄｅｖｅｌｏｐｅｄｆｏｒｔｈｅｄｙｎａｍｉｃｐｒｏｃｅｓｓｄｕｒｉｎｇｗｈｉｃｈｖｅｈｉｃｌｅｓａｒｅｉｎｔｒａｆｆｉｃ．ＩｎｔｈｅｓｉｍｕｌａｔｉｏｎｍｏｄｅｌｔｈｅＧＬＳａｌｇｏｒｉｔｈｍｉｓａｐｐｌｉｅｄｔｏｏｐｔｉｍｉｚｉｎｇｔｈｅｖｅｈｉｃｌｅｒｏｕｔｅｓｉｎａｃｃｏｒｄａｎｃｅｔｏｔｈｅｒｅａｌ—ｔｉｍｅｔｒａｆｆｉｃｓｉｔｕａｔｉｏｎ，ａｎｄｆｏｕｒｒｕｌｅｓａｙｅａｐｐｌｉｅｄｔｏｊｕｄｇｉｎｇｉｆｔｈｅｎｅｗｌｙｏｐｔｉｍｉｚｅｄｖｅｈｉｃｌｅｒｏｕｔｅｓａｒｅａｃｃｅｐｔｅｄ．ＴｈｅｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｒｅｖｅａｌｔｈａｔｔｈｅＧＬＳ ａｌｇｏｒｉｔｈｍｃａｎｐｒｏｖｉｄｅｒｅａｌ－ｔｉｍｅｒｅｓｐｏｎｓｅｔｏｄｙｎａｍｉｃｉｎｆｏｒｍａｔｉｏｎｔｏｓａｔｉｓｆｙｔｈｅｒｅｑｕｉｒｅｍｅｎｔｓｏｆｓｏｌｖｉｎｇＤＶＩ王Ｐ． Ｋｅｙｗｏｒｄｓ：ｉｎｔｅｌｌｉｇｅｎｔｔｒａｎｓｐｏｒｔａｔｉｏｎｓｙｓｔｅｍ；ＤＶＲＰ；ｔｒａｆｆｉｃｓｉｍｕｌａｔｉｏｎ；ＧＬＳ 物流优化已经成为当代企业的一个重要利润源泉．车辆路径问题（ｖｅｈｉｃｌｅｒｏｕｔｉｎｇｐｒｏｂｌｅｍｓ，Ⅵ冲）是物流领域的核心和热点研究问题，吸引了众多学者和业者的研究和关注．现代物流市场的激烈竞争和顾客的个性化需求不断提高，使得现代物流配送运作更加复杂，要求物流配送系统更加灵活、高效地针对变化的环境调整作业计划．计算机及通讯技术的迅速发展，使得交通状况及运输工具的实时信息更易获取，为解决物流配送面对的新问题提供了基础．动态ＶＲＰ（ｄｙｎａｍｉｃＶＲＰ，ＤｖＲＰ）正是在这样的背景下开始受到了关注和研究．现有研究主要是针对环境变化，对车辆路径计划进行重计划或局部调整，涉及的方法有元启发式算法和局域搜索算法等【１－２Ｊ．本文针对城市复杂交通系统的环境变化，提出了一种ＤＶＲＰ中更新车辆路径的导向局域搜索（ｇｕｉｄｅｄｌｏｃａｌｓｅａｒｃｈ，ＧＬＳ）算法，设计了动态交通环境的仿真模型，通过对７１个节点交通路网的仿真实验，得出了咖车辆路径的更新原则，研究成果对于现代城市智能交通系统中的车辆路径优化 收稿日期：２００７一０４—０５ 基金项目：国家自然科学基金资助项目（７０３０１００７，７０７７１０２０，７０４３１００３）；新世纪优秀人才支持计划项目（ＮＣＥＴ－０６－０２８６）．作者简介：刘士新（１９６８一），男，辽宁调兵山人，东北大学教授． 万方数据
蚁群算法在车辆路径问题中的应用 摘要 蚁群算法（Ant Colony Optimization, ACO）是意大利学者M.Dorigo等人通过模拟蚁群觅食行为提出的一种基于种群的模拟进化算法。通过介绍蚁群觅食过程中基于信息素（pheromone）的最短路径的搜索策略，给出了基于MATLAB 的蚁群算法在车辆路径问题（Vehicle Routing Problem, VRP）中的应用。蚁群算法采用分布式并行计算机制，易于其他方法结合，而且具有较强的鲁棒性，但搜索时间长，容易陷入局部最优解。针对蚁群算法存在的过早收敛问题，加入2—opt方法对问题求解进行了局部优化，计算机仿真结果表明，这种混合型蚁群算法对求解车辆路径问题有较好的改进效果。 关键词：蚁群算法、组合优化、车辆路径问题、2-opt方法 1.车辆路径问题 车辆路径问题（VRP）来源于交通运输，1959年由Dantzig 提出，它是组合优化问题中一个典型的NP-hard问题。最初用于研究亚特兰大炼油厂向各个加油站投送汽油的运输路径优化问题，并迅速成为运筹学和组合优化领域的前沿和研究热点。
车路优化问题如下： 已知有一批客户，各客户点的位置坐标和货物需求已知，供应商具有若干可供派送的车辆，运载能力给定，每辆车都是从起点出发，完成若干客户点的运送任务后再回到起点。现要求以最少的车辆数和最少的车辆总行程来完成货物的派送任务。 2、蚁群系统基本原理 在蚂蚁群找到食物时，它们总能找到一条从食物到蚁穴之间的最短路径。因为蚂蚁在寻找食物时会在路途上释放一种特殊的信息素。当它们碰到一个还没有走过的路口时，会随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激素浓度越低。当后面的蚂蚁再次碰到这个路口时，会选择激素浓度较高的路径走。这样形成了一个正反馈，最优路径上的激素浓度越来越高，而其他的路径上激素浓度却会随时间的流逝而消减。最终整个蚁群会找出最优路径。在整个寻找过程中，整个蚁群通过相互留下的信息素作用交换着路径信息，最终找到最优路径。 3、基本蚁群算法求解车辆路径问题 求解VRP问题的蚂蚁算法中，每只蚂蚁是一个独立的用 于构造路线的过程，若干蚂蚁过程之间通过信息素值来交换信