·论文·
车辆路径调度问题的启发式算法综述1
杨燕旋1，宋士吉1
(1.清华大学自动化系，北京 100084)
摘要：车辆路径调度问题是一类具有重大研究意义及广泛应用价值的NP难优化问题。本文给出了该问题的定义和基本描述，并将目前为止被应用于求解VRP问题的启发式算法分为构造型启发式算法、改进型启发式算法和人工智能算法这三大类，接着介绍了各类中比较典型的算法，并对算法的应用和研究情况进行了分析和总结，最后对进一步的研究做出了展望。
关键词：物流；车辆路径问题；调度；启发式算法
中图分类号：F252
A Survey on the Heuristic Algorithms for the Vehicle Routing
Problem
YANG Yan-Xuan,1 SONG Shi-Ji,1
(1.Department of Automation, Tsinghua University, Beijing 100084, China)
Abstract：Vehicle Routing Problem is an NP-hard problem with great research and application significance. In this research, we first present the definition of the problem and give a classification to the existed heuristic algorithms for the problem. Then typical algorithms are introduced and research on the algorithms are investigated and summarized. Finally, further research directions are given.
Key words：Logistics; Vehicle Routing Problem; Scheduling; Heuristic Algorithm 1959年，Dantzig等人首先从旅行商问题（Traveling Salesman Problem，简称TSP问题，）得到启发，提出了车辆分配问题TDP（Truck Dispatching Problem）。这是一类具有重要研究价值的问题。一方面，它代表了一类典型的组合优化问题，具有深远的理论意义；另一方面，它是一类重要的物流运输问题，直接影响着相关企业的运转效率，具有广泛的实践意义。半个世纪以来，许多的专家学者对该问题进行了广泛而深入的研究，并将这类问题统称为车辆路径调度问题（Vehicle Routing Problem，简称为VRP问题）。他们从基本问题出发，根据
1基金项目：自然科学基金（编号：60574077）、国家“八六三”高技术项目（编号：2007AA04Z102）
作者简介：杨燕旋（1983-），女，汉族，广东，清华大学硕士研究生，从事车辆路径调度方向的研究，E-mail: yyx02@https://www.doczj.com/doc/193996318.html,. 宋士吉（1965-），男，汉族，黑龙江，清华大学教授，博导，从事供应链管理等方向的研究，E-mail: shijis@https://www.doczj.com/doc/193996318.html,
不同的约束和目标，构建了不同的模型，并有针对性地开发出了有效的算法。
从大的框架上讲，用于求解VRP 问题的算法可以分为两类，一类是精确算法；一类是启发式算法。精确算法主要是基于对具体的问题建立具体的数学模型，并利用数学方法进行求解；启发式算法主要是基于直观或者凭借经验，开发出能够朝着最优解的方向搜索或靠近的一类算法。精确算法以时间和空间的复杂度为代价，换取了解的质量，但往往只能应用于小规模的问题中，这是由VRP 是NP 难问题的属性所决定的；启发式算法通常能够在时间和空间复杂度以及解的质量中获得一个平衡，因此，该类算法被越来越多的学者所采用和研究，在实际应用中，它们也显示出了它们的优势。
本文对目前被应用得比较多且相对较为成熟的启发式算法进行一个综述。启发式算法可以分为三大类：（一）构造型启发式算法；（二）改进型启发式算法；（三）人工智能算法。本文在总结时，将对各类算法中比较经典和基本的算法（见表1）进行描述，并对相关的研究进行总结。
表1 启发式算法分支图 三大类
经典算法 插入算法节约算法
先聚类后路线算法
构造型启发式算法 先路线后分割算法
Petal 算法
Sweep 算法
改进型启发式算法 Or-opt 算法
禁忌搜索算法
遗传算法
蚁群算法
启发式算法 人工智能算法
模拟退火算法1 车辆路径问题的定义和描述
车辆路径调度问题的一般定义[1]为：对一系列发货点和收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等) 下，达到一定的目标(如路程最短、费用最小、时间尽量少、使用车辆尽量少等)。
在基本定义中，可以总结出VRP 问题中涉及到的能够影响问题模型的变量有：
1） 仓库（v o ）
：就数目来讲，有两种组合，即单仓库和多仓库，一般只考虑单仓库问题，因为多仓库问题可以通过区域划分简化为单仓库问题；另外，现实中，通常仓库会有固定的服务对象，因此算法只考虑单仓库问题；
2）车辆（k i）：就数目来讲，有两种组合，即单车辆和多车辆；就容量来讲，可以有容量限制和无容量限制两类，也可以有同容量车辆和不同容量车辆两类；可以有运输路线长度限制和无运输路线长度限制两类；就车辆是否需要返回仓库来讲，有封闭式（车辆需要回到车场）和开放式（车辆不需要回到车场）两类；就车辆在固定路段的运行时间来讲，可以分为固定旅行时间、模糊旅行时间和随机旅行时间三类；
3）客户（v i）：就数目来讲，可以分为有固定客户数目和随机客户数目两类；就客户需求来讲，可以有多维度的考虑，可以分为有时间窗要求和无时间要求两类；可以有固定客户需求、模糊客户需求和随机客户需求三类。
根据这些主体变量取值的不同可以将VRP问题分为很多种类型，由于本文旨在对算法进行综述，不涉及针对某种类型的算法的讨论，因此这里就不再对各种类型的VRP问题进行一一列举了。
求解VRP问题时，我们旨在得到一系列路线，车辆按照该路线来服务顾客，在满足顾客需求的同时，使得总的运输费用最小。在设计这些路线时，还要根据不同问题考虑不同约束，设计的路线不能够违背相应的约束。下面介绍一些经典的求解该问题的启发式算法。而值得说明的是，下边介绍的算法无论对于求解哪一种VRP问题都是会有启发的，因为这些算法都能够帮助读者从不同的角度或程度去思考求解某一种具体VRP问题，只是由于问题特点的不同，有些算法对于辅助解决某一类型的问题显得更好，对其他类型则可能略显不足。2构造型启发式算法
构造型启发式算法是一类基于直观或者经验来构造相对有效解的算法。这类算法的共同特点是：根据某些降低耗费的规则或者标准，每一次将不在线路上的点增加进已经构造的路线中去，直到所有的点都被安排进线路为止。
2.1插入算法
插入算法是指通过k步迭代时，将第k个节点插入到路线中。算法的关键在于确定在第k+1步可以被插入到路线中的点以及该点的最佳插入位置。因此，该算法由两个关键的部分组成。第一部分是节点选择阶段，即确定下一步被插入到路线中的顾客节点；第二部分是路径插入阶段，即确定所选择的顾客节点在路线中的最佳插入位置。
根据不同的节点选择规则，可以得到不同的插入算法。比如，最短距离插入算法（Nearest Insertion）选择离路线中的任意一点距离最短的点插入到路线中；最低耗费插入算法（Cheapest Insertion）选择插入后子路线费用最低的点插入到路线中。更多的插入算法可以
参考Bodin等[2]的研究，他们总结了八种插入算法，并逐个分析了它们在最坏情况下的解的情况，这些统称为基本插入算法，除了上述的几种算法外，还包括凸包插入、最大角插入、最远距离插入、任意插入、快速插入、差值比率插入，关于这一类算法，读者可以参阅参考文献[2]。
不少学者借鉴基本插入算法的思想，针对不同问题开发了新的插入算法。Renaud和Boctor等[3]借鉴凸包插入算法的思想，开发了CLOCK插入算法，作为初始解的构造方法。该算法从一个节点出发，顺时针或者逆时针地将其他相关节点插入到路线中，这样形成的初始路线不一定会包括所有的节点，算法允许在下一步将剩余的节点插入到路线中，形成完整的路线。
2.2节约算法
节约算法是一类最为经典的构造型启发式算法之一，该算法最早由Clark和Wright于1964年提出[4]，通常被简称为C-W算法。该算法的思想是：根据顾客点之间连接可以节省的距离（节约值）最大的原则，将不在线路上的顾客点依次插入到路线中，直到所有的点都被安排进路线为止。
根据不同的模型可以对节约值进行不同的定义，以辅助求得相应模型的较优解。C-W 算法中对节约值的定义为：s(i,j)=c i0+c0j-c ij，即依次服务i和j比分开单独服务i和j可以节省的值，其中c ij表示从顾客i到顾客j的运输总费用。算法开始时，计算所有的节约值s ij= c i0 +c0j-c ij，并将它们由从大到小进行排列，同时生成n-1条独立的路线(1,i,1)；之后分别考虑包含弧(i,1)和(1,j)的两条路线，如果将他们合成后对应的节约值大于0，则在满足容量或时间等其他约束的条件下将这两条路线合二为一。重复这个步骤直到没有路线可进一步合并为止。
节约算法根据特定规则一次性地生成了可行解，并把它当成问题的解。该算法是很经典的构造型启发式算法，在提出之后被许多学者所借鉴和研究引用[2, 5]。
但是实际应用中，更多的算法则是将整个构造的过程分为两大步，现在用得最多的有即先聚类后安排路线的算法和先安排路线后分割的算法。
2.3先聚类后路线算法
在对实际的大规模VRP问题设计算法时，往往会因为节点数目的增大而使得求解的难度变大，因此，可以考虑先根据一些原则（如距离或服务时间的相近、需求的合适组合等），采用合适的操作，对节点进行分区或者聚类，由同一辆车服务同一分区或者同一类中的顾客节点；然后再对分区里的节点进行排序，确定车辆在分区内的行车路线。
由于车辆通常有容量限制，因此安排到每个车辆的顾客节点的数目是有限的，因此在步骤2可以采取精确算法来求得一条最优的路线。因此，本算法的关键在于步骤1，即如何进行聚类才能够使得解较优的问题。
截至目前，不少学者应用该算法的思想求解了VRP问题。Karp等[6]利用该算法解决了大规模TSP问题，他们还分析这种方法在最坏情况下的表现；Fisher和Jaikumar[7]开发了用于求解VRP问题的广义分配启发式算法，他们将聚类问题看成一个广义分配或匹配问题并加以求解；不少学者通过设定规则逐步进行寻优聚类，比如按照服务时刻、顾客需求量、地理位置相近度等规则进行聚类，Gillett和Miller[8]在地理平面上建立极坐标系，按照顾客极坐标角大小依次对顾客编号，然后基于车辆容量约束依次将顾客安排到车辆中，完成了顾客到车辆的分配，即顾客聚类（Lin的文章称为生成Petal集，具体参见下文叙述的Petal算法）；Yang等[9]在进行顾客节点分区时提出另一种更为有效的聚类方法，即先选择种子顾客节点，再根据种子顾客节点对其他节点进行吸收，最后完成聚类。其他的算法可参见参考文献[6, 10-12]。
2.4先路线后分割算法
该算法首先生成或构造一条很长的实际不可行的较优路线，该路线包括所有待服务的顾客节点；然后根据一定的约束（如车辆容量等）对它进行分划，使路线变成多条短而可行的路线，每条路线可以由相应的车辆来进行服务。
许多学者利用该算法解决了许多VRP实际应用问题。Bodin等[13]采用先路线后分割的算法，开发了一个计算机辅助系统，求解了街道清洁机的调度问题。Yang[9]等人用该算法求解了多车辆随机VRP问题，在他们的研究中，他们利用插入算法和Or-opt算法得到了初始单一优化解，然后利用动态规划算法来对得到的路线进行分割，以得到比较好的可行分支路线；其他的相关研究可以参见参考文献[14-16]，这些成果的特点是利用先路线后分割的算法来求解VRP问题，在对路线进行分割时，他们采用了集分割模型求解等方法。
以上描述了五种比较基本和常见的构造型启发式算法，事实上，还有很多的算法也是属于这一种类型，比如Kim提出的最小生成树方法[17]（Minimal spanning tree approach）、Christofides提出的Christofides启发式算法[18]（Christofides’ heuristic）、Rosenkrantz等[19]提出的最近邻算法（Nearest Neighbor Algorithm）和最短归并方法（Nearest merger）等。由于篇幅关系，这里不再一一列举。详细的可以阅读相关参考文献。
由于构造型启发式算法能够通过一次的构造得到较优解，因此它们在求解速度上显示出了很大的优势。但在一些应用中，由一次构造出来的解的质量往往不能够达到要求，因此学
者们探索通过一些新的方法来进一步改进解的质量，于是有了各种类型的改进型启发式算法。
3改进型启发式算法
改进型启发式算法从一个初始解出发，在始终保持解可行的情况下，对当前的解进行反复地局部扰乱或者调整，力图使目标函数得以改进，一直继续到不能再改进目标函数为止。现在用得最多的改进型启发式算法大多都是基于交换操作的算法，即在路线内或者路线间交换顾客节点或者在定义的解的邻域中搜索，以得到新的解。比较经典的几类改进型启发式算法有Lin等提出的Petal算法、Gillett和Miller[8]提出的Sweep算法和Lin等提出的Or-Opt 交换算法。
3.1Petal算法
Petal算法是Lin等人于1965年提出的。该算法首先定义并确定了可行Petal集，然后利用集分割模型求解等方法从得到的可行Petal集中得到优化的路线，找到较优解。
在地理平面上建立极坐标，以仓库作为坐标中心，确定所有需求点的极坐标。将所有节点按照极坐标角的大小进行重新排序。此时，任何一组由连续的节点构成的集合均可称为Petal。
Foster等在他们的文章[14]中提出了枚举所有可能Petal的有效方法。在求解VRP问题时，有效的Petal在求解问题中显得更重要。有效Petal指的是集合中的所有顾客节点的可以由同一个车辆进行服务，即满足相关的约束，诸如容量、总路线长度等。
在Petal算法中，每个Petal的费用取决于车辆在Petal内的行车路线，这个路线可以获得精确最优解。Petal算法的关键在于从所有可行Petal中找到一个能够覆盖所有顾客节点的Petal集。为了能够找到比较好的Petal集，Foster等[14]提出了一个集分割模型，并利用线性单纯形法求解得到优化结果。Ryan[16]等拓宽了Petal的定义，提出了广义的Petal，并利用最短路算法来生成广义优化Petal集，获得更好的优化解。Renaud[20]等进一步提出了r-Petal的概念，即一个Petal中的顾客节点需要有r辆车才能完成服务，进而在该Petal中会形成相应的r条路线。他们首先得到1-Petal和2-Petal集，在利用集分割模型求解到较优解。 Petal算法提出后，许多学者得到启发，利用该算法提出很多新的算法，可参考文献[16, 20, 21]。
3.2Sweep算法
Sweep算法最早由Gillett和Miller于1974年提出。他们利用Petal算法得到所有顾客
节点的排序后，按照一定的方法将各节点的运输任务派给车辆，形成了第一个相对合理的可行解。之后他们利用Sweep算法来对初始解进行改进，他们将第K个路线的一个节点j抽出来，其中K=1,2,……,m-1，其中m是所有路线的总数；同时将K+1路线中的一个或多个点换到K路线中。节点j再进一步被分配到其他路线中。为了确定被抽出的节点，可以定义不同的指标函数来选择节点I。为了确定被放入第K个路线的节点，首先选择一个节点，满足它与最后被加到第K个路线的节点的距离最近，依次类推。
受到Sweep算法的启发，Thompson和Psaraftis在他们的文章[22]中提出了一种新的互换操作，称为循环k转移操作（cyclic transfers）。首先根据一些特定的规则将所有的节点分配给不同的车辆，形成b+1条可行路线；接着对形成的路线进行b循环k转移（b-cyclic k-transfer）：即将从第i条路线选出的b个节点转移到第i+1条路线中，i=1,2,……b。每完成一次b循环k转移，便检查一次形成路线的可行性以及该次循环转移所增加的费用，如果增加的费用为正值，则不进行循环转移。如此不断进行互换操作，直到最终的解的质量较好为止。
交换算法作为一个基本算法，其思想被应用于很多的其他算法中，学者根据该思想开发了许多其他的算法。Renaud和Boctor[21]借鉴互换操作的思想，开发了一个基于邻域交换的启发式算法，通过算法的不断交换和更新操作，求得了相应的最优解。
3.3Or-opt算法
Or-Opt交换算法是一类常用和著名的路径改进算法。Lin等人于1965年首先提出了2-opt 和3-opt启发式算法，随后又将该算法扩充为k-opt算法，详见参考文献[23]。该类算法的简单框架如下（参考Yang的文献[9]）：首先，假设已经由其他算法得到一条初始路线，设该路线为T；计算路线T对应的目标函数费用值。从T中得到所有由连续k、k-1、……1个节点组成的子路线集S，对集合中的每个子路线，计算T中去掉S后，目标函数费用值的节约值，记为s；将S插入到T中的其他位置，并计算目标函数费用值的增加值，记为d；计算
c≤，则现在的路线T 目标函数费用值的差值，即c=s-d；如果对于任意的子路线，均有0
即为得到的优化路线；否则选择其中最大的c值，并将对应的子路线插入到对应的位置上，将其作为新的路线T，重新开始新一轮的迭代；
该算法被提出后，不少学者对算法进行了扩展，不断地改进算法的性能，可参考文献[24, 25]。
在改进型启发式算法中，解的质量或者求解速度往往对初始解有一定的依赖，因此一般会先通过构造型启发式算法来求得初始解，因此上述的各种算法或者算法的变型常常被同时
应用着，学者们将组合成的算法称为N阶段启发式算法或者组合算法，通过组合算法能够在解的质量和求解速度中取得一个平衡，Renaud等[3]开发的快速组合启发式算法就是综合应用多种构造型和改进型启发式算法来得到优质解的范例。
4人工智能算法
人工智能算法，是基于降低解空间搜索规模的思想被提出来的。包括禁忌搜索算法，模拟退火算法，进化算法，蚁群算法，神经网络等算法。这一类算法在最有可能获得最优解的子空间进行搜索，不断迭代，不断改进解的性质。
4.1禁忌搜索算法
禁忌搜索算法（Tabu Search，简称TS）是这类算法中被应用得最多的算法，在许多的实验仿真中，该算法都显出了优于其它算法的性能，该算法的通用结构可参见文献[26]。它通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。
用该算法求解VRP问题时，需要定义解的邻域结构N(x)，以便对生成的解x进行邻域搜索。在算法的初期，构建往返于仓库和顾客节点的路线x，并生成一组邻域，算法有在邻域中搜索并计算得到的解的质量的功能。为了避免重复搜索，算法利用一些特定的规则将一些解加到预先设定的禁忌表中，每次搜索只检查不在禁忌表中的解的情况，如此反复迭代并更新，直到得到的最好解的质量足够好或者迭代的次数达到预定的次数为止。
由本身的算法特点决定了禁忌搜索的优化结果对初始解有较强的依赖性，算法搜索的过程只能对一个解进行操作，所以往往需要使用别的启发式算法先获得一个比较好的初始解，比如上述的构造型启发式算法。截至目前，国内外已经有许多专家用禁忌搜索算法求解了各种类型的VRP问题。Taillard和Badeau等[27]利用该算法求解了带软时间窗的VRP问题，他们通过互换两条路线中的一组连续顾客节点来生成原路线的邻域，同时定义了一个自适应记忆池，将算法找到的质量好的解放进池中，并每次从中挑选出一组较优解，进行重新组合，作为新一次搜索的起始点，以此使算法的性能得到了很大的改进；Gendreau等[28]提出了基于禁忌搜索算法的TABUROUTE算法，解决了带容量和路线长度约束的VRP问题。该算法利用一个节点在两条路线中的转移来生成解的邻域，同时该算法在搜索过程中对不可行解进行了赦免，使解能够朝着全局优化的方向靠近。Cordeau等[29]提出了一个统一禁忌搜索算法（Unified TS），求解了带有时间窗的多仓库VRP问题，该算法在求解该类问题中显示出了其快速性、简单性和灵活性。其他相关的研究可参见参考文献[30, 31]。
遗传算法（Genetic Algorithm，简称GA）是美国J.Holland和他的学生于1975年受生物进化论的启发而提出并建立发展起来的。其基本思想是借鉴大自然生物进化中“适者生存”的规律，通过对产生的解（“父代”）不断操作（包括复制、交叉、变异和竞争）以产生新的解（“子代”），如此反复迭代，最终收敛到“最适应环境”的个体，从而得到相对比较好的解。
用遗传算法求解VRP问题时，首先根据不同问题定义不同的编码方式，用码来表示问题的解，比如用于表示节点服务顺序的一个字符串可以是一种码，每一条局部路线可以是基因。将这种码看成染色体，不同的染色体中会包含不同的基因，每组基因表达一个信息单元。开始时，构建往返于仓库和顾客节点的一系列路线集X并编码，作为初始种群；然后，挑选出部分染色体（码），从中取出不同的基因，按照某种组合产生新的染色体；再挑选出一些染色体，改变其中的一些基因，实现变异，产生新的染色体；设定某种竞争机制，在生成的新的染色体中挑选出比较好的个体，同时将上一代中质量比较好或者适应度比较高的个体进行复制，一并成为新的一代；如此反复。如果当前的最佳染色体所对应的解的质量达到要求或者算法迭代次数达到要求，则结束算法，并以当前的最好解作为问题的解。
由于每一代都复制了上一代中的最好个体，因此遗传算法隐含着对全局解空间搜索的特点，不会在过程中丢失好的解。但他也存在着过早收敛和搜索效率低等缺陷。截至目前，国内外有许多利用遗传算法求解VRP问题的研究，包括研究如何通过对编码、染色体构建、基因定义、变异及适应度定义等不同操作的设置来改进算法效能的问题。
Tan等[32]人利用遗传算法的思路开发了MOEA算法，求解了随机需求多目标VRP问题，他们在算法中借鉴了两种局部搜索启发式算法，利用Pareto优化思想，在搜索过程中得到更优的解并开拓了更大的搜索空间，同时他们建立了评估解的适应度的仿真方法，辅助算法获得比较好的解。Malmborg[33]分析了实际VRP问题求解中的对解的性质评估的难度问题，指出了遗传算法在算法实现和全局搜索等方面的优势，并开发了一个二阶段遗传算法，该算法在每次迭代时均保留了父代解中的优质的子路径，并复制到下一代，利用该算法，作者很好地解决了带装载问题的VSP问题。Hwang[34]利用遗传算法的思想，针对带有时间约束的VRP问题提出了一个GA-TSP模型，并通过改变遗传算法中的各种基本操作和初始种群的产生方法，有效地求解了该类VRP问题。关于遗传算法的更多研究和应用，读者可以参见参考文献[35, 36]。
蚁群算法是一种生物仿生算法，该算法是上世纪90年代由M.Dorigo等学者从自然界蚁群觅食行为中受到启发而提出的一种优化算法。研究发现，尽管单只蚂蚁的觅食能力有限，但整个蚁群却能够在觅食的过程中，互通信息，最后发现从蚁巢到食物源的最短路径：每当蚂蚁发现一条通往食物源的路径时，它们便会在路径上释放一种“信息素”，同时它们也根据信息素的浓度来决定它们的移动方向（岔路选择原则）。开始时，不同路径上的信息素浓度一样；当蚂蚁沿着一条路到达终点时，它们便会原路返回；这样，短的路径上的蚂蚁来回的频率就高，信息素的浓度也自然增高，于是吸引更多的蚂蚁，散发更多的信息素，如此形成正反馈，最后越来越多的蚂蚁被吸引到较短的路径上，于是找到最佳路径。
蚁群算法被提出后，不少学者利用该算法来求解各种VRP问题。Mazzeo[37]等利用蚁群算法的思想，开发了ACO（An Colony Algorithm）算法，求解了带容量约束的VRP问题，并就几类典型的VRP问题进行了实验仿真，证实了该算法的有效性；Dorigo等[38]开发了一个基于蚁群算法的系统ACS（Ant Colony System），并利用一些局部搜索算法来改进优化解，较好的求解了TSP问题；Bullnheimer[39]等开发了一个改进型蚁群系统求解了单仓库、同生产能力车辆的VRP问题，并通过对14个benchmark进行实验仿真，与其他5个人工智能算法的实验对比，显示出该算法的有效性。其他的相关研究可参见参考文献[40, 41]。4.4模拟退火算法
模拟退火（Simulated Annealing，简称SA）算法的思想是Metropolis受到物理退火过程的启发，于1953年提出来的。物理退火过程主要是通过加热使固体脱离平衡态，融解为液体，增加物体的能量，然后经过等温过程和冷却过程，降低物体的热运动和能量，进而得到低能的晶体结构。组合优化问题中，问题的解好比粒子状态，问题的目标函数好比粒子的能量，因此求取最优解的过程即是得到粒子能量最低态的过程。1983年，Kirkpatrick等意识到组合优化与模拟退火的这种相似性，将该算法应用于求解组合优化问题中，之后有不少学者将该算法应用于求解VRP问题。
Tavakkoli-Moghaddam等[42]利用一种混合的模拟退火算法求解了带容量约束的VRP问题，以得到能够使车辆费用最小和车辆容量利用率最大的解。在应用该算法时，他们提出了基于最近邻算法的NNBH算法，用于生成模拟退火算法的初始解；而在更新解时，他们利用了1-opt和2-opt交换算法。事实上，模拟退火算法自身能够克服初值依赖性，但是好的初始解能够改善解的收敛速度。Attahiru[43]也利用模拟退火算法来求解VRP问题，在求解过程中，他们利用了3-opt交换算法。其他的相关研究可参见参考文献[44-46]。
5总结与展望
VRP问题自从被提出来以后就受到了广泛的关注，不少学者对求解该问题的算法进行了研究，并取得了不少成果。本文结合国内外的相关研究，对现有的比较典型的用于求解该问题的启发式算法进行了分析和总结。
相对于精确算法，启发式算法具有更好的工程实际应用价值。因为它既能够在合理的时间内得到问题的较优解，又能够使得到的较优解的精度满足工程要求。从总结可以看到，启发式算法是一类基于直观或者经验设计而成的算法，因而算法设计具有较高的灵活性和较大的自由度。事实上，本文仅仅列举了一些比较典型的算法，而这些算法在应用时，又往往会被结合着使用，以进一步提高解的质量。
另外，随着人们对VRP问题研究的深入以及对VRP问题解质量要求的提高，人们开始研究如何在算法中加进人的主观判断以提高解的质量，比如如何在行驶过程中判断到仓库补货的时机，这归结为补货策略问题；另外，人们也开始研究如何结合顾客库存的情况来制定运输策略的问题，这归结为库存运输问题；诸如此类的研究尚处于起步阶段，因此具有很大的研究潜力和意义。
参考文献
[1] 郭耀煌, 李军. 车辆优化调度成都科技大学出版社, 1994.
[2] Bordin L, Golden B, Assad A, Ball M. Routing and scheduling of vehicles and crews The state of
the art. Computers and Operations Research 1983;10(2):63-211.
[3] Renaud J, F.Boctor F, Laporte G. A Fast Composite Heuristic for the Symmetric Traveling
Salesman Problem INFORMS Journal on Computing 1996;8(2):134-43.
[4] Clarke G, Wright JW. Scheduling of vehicles from a central depot to a number of delivery points.
Operations Research 1964;12(4):568-81.
[5] Golden B. A statistical approach to the TSP. Networks 1977;7:209-25.
[6] Karp R. Probabilistic analysis of partitioning algorithm for the traveling salesman problem in the
plane. Mathematics of Operations Research 1977;2(3):209-24.
[7] Fisher M, Jaikumar R. A Generalized Assighment Heuristic for the vehicle routing problem.
Networks 1981;11:109-24.
[8] Gillet BE, Miller LR. A Heuristic Algorithm for the Vehicle Dispatch Problem. Operations
Research 1974;22:340-49.
[9] Yang W-H, Mathur K, Ballou RH. Stochastic vehicle routing problem with restocking.
Transportation Science 2000;34(1):99-112.
[10] Toth P, Vigo D. A heuristic algorithm for the symmetric and asymmetric routing problem with
backhauls. European Journal of Operational Research 1999;113(3):528-43.
[11] Dror M, Ball M, Golden B. A computational comparison of Algorithm for the inventory routing
problem. Annals of Operations Research 1985;4(1):3-23.
[12] Christofides N, Beasley J. The Period Routing Problem. Networks 1984;14:237-56.
[13] Bodin LD, Kursh SJ. A computer-Assisted System for the Routing and Scheduling of Street
Sweepers. Operations Research 1978;26(4):525-37.
[14] B.A.Foster, D.M.RYAN. An Integer Programming Approach to the Vehicle Scheduling Problem.
Operations Research Quarterly 1976;27(2):367-84.
[15] Golden BL, Assad AA, Levy L, Giieysens F. The fleet size and mix vehicle routing problem.
Computers and Operations Research 1984;11:49-66.
[16] M.Ryan D, Hjorring C, Glover F. Extensions of the Petal Method for Vehicle Routing. The Journal
of the Operational Research Society 1993;44(3):289-96.
[17] Kim C. A minimal spanning tree and approximate tours for a traveling salesman 1975.
[18] Christofides N. Worst-case analysis of a new heuristic for the traveling salesman problem 1976.
[19] Rosenkrantz D, Sterns R, Lewis P. An analysis of several heuristics for the traveling salesman
problem. SIAM Journal on Computing 1977;6:563-81.
[20] RENAUD J, BOCTOR FF, LAPORTE G. An Improved Petal Heuristic for the Vehicle Routing
Problem. Journal of the Operational Research Society 1996;47:329-36.
[21] Renaud J, F.Boctor F. A Sweep-Based Algorithm for the Fleet Size and Mix Vehicle Routing
Problem. European Journal of Operational Research 2002;140:618-28.
[22] Thompson PM, Psaraftis HN. Cyclic Transfer Algorithms for the Multivehicle Routing and
Scheduling Problems. Operations Research 1993;41:935-46.
[23] Lin S, Kernighan B. An Effective Heuristic Algorithm for the Travelling Salesman Problem.
Operations research 1973;21(2):498-516.
[24] Russell R. An effective heuristic for the M-tour traveling salesman problem with some side
conditions. Operations research 1977;25(3):517-24.
[25] Christofides N, Eilon S. Algorithms for large-scale traveling salesman problems. Operational
research quarterly 1972;23:511-18.
[26] 王凌. 智能优化算法及其应用, 1 ed. 清华大学出版社, 2004 (230 pp.).
[27] Taillard E, Badeau P. A tabu search heuristic for the vehicle routing problem with soft time
windows. Transportation science 1997;31:170-86.
[28] Gendreau M, Hertz A, Laporte G. A tabu search heuristic for the vehicle routing problem.
Management science 1994;40(10):1276-90.
[29] Cordeau J-F, Laporte G, Mercier A. A unified tabu search heuristic for vehicle routing problems
with time windows. Journal of the Operational Research Society 2001;52(8):928-36.
[30] Jiefeng X, P.Kelly J. A network flow based tabu search heuristic for the vehicle routing problem.
Transportation Science 1996;30(4):379-93.
[31] Gendreau M, lori M, Laporte G, Martello S. A Tabu search heuristic for the vehicle routing
problem with two-dimensional loading constraints. Networks 2007;51(1):4-18.
[32] Tan KC, Cheong CY, Goh CK. Solving multiobjective vehicle routing problem with stochastic
demand via evolutionary computation. European Journal of Operational Research 2007;177:813-39.
[33] J.Malmborg C. A genetic algorithm for service level based vehicle scheduling. European Journal of
Operational Research 1996;93(1):121-34.
[34] Hwang H-S. An improved model for vehicle routing problem with time constraint based on genetic
algorithm. Computers & Industrial Engineering 2002;42:361-69.
[35] Potvin J-Y, Bengio S. The vehicle routing problem with time window - Part 2: Genetic search.
INFORMS Journal on Computing 1996;8(2):165-72.
[36] Prins C. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers
and Operations Research 2004;31(12):1985-2002.
[37] Mazzeo S, Loiseau I. An Ant Colony Algorithm for the Capacitated Vehicle Routing. Electronic
Notes in Discrete Mathematics 2004;18:181-86.
[38] Dorigo M, Gambardella LM. Ant colonies for the travelling salesman problem. BioSystems
1997;43:73-81.
[39] Bullnheimer B, Hartl RF, Strauss C. An improved Ant System algorithm for the Vehicle Routing
Problem. Annals of Operations Research 1999;89:319-28.
[40] E.Bell J, R.McMullen P. Ant colony optimization techniques for the vehicle routing problem.
Advanced Engineering Informaties 2004;18:41-48.
[41] Donati A V, Montemanni R, Casagrande N, Rizzoli AE, Gambardella LM. Time dependent vehicle
routing problem with a multi ant colony system. European Journal of Operational Research 2008;185:1174-91.
[42] Tavakkoli-Moghaddam R, Safaei N, Gholipour Y. A hybrid simulated annealing for capacitated
vehicle routing problems with the independent route length. Applied Mathematics and Computation 2006;176:445-54.
[43] Attahiru SA. A 3-opt based simulated annealing algorithm for vehicle routing problems.
Computers & Industrial Engineering 1991;21(1-4):635-39.
[44] Lin SW, Ying KC, Lee ZJ, Hsi FH. Applying Simulated Annealing Approach for Capacitated
Vehicle Routing Problems. 2006 IEEE International Conference on Systems, Man, and Cybernetics, Taipei, Taiwan, 2006.
[45] 谢秉磊, 李良, 郭耀煌. 求解配送/收集旅行商问题的模拟退火算法. 系统工程理论方法应用
2000;11(3):240 - 43.
[46] 蔡延光, 钱积新, 孙优贤. 多重运输调度问题的模拟退火算法. 系统工程理论与实践
1998;18(10):11－15.
!""#$%%%&%%’( )#$$&***+,#清华大学学报-自然科学版. /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
系 统 管理学报 第１９卷 不同，文献［６］中１００，本文３０；③文献［６］中没有给出２０次求解中有多少次求得最优解，本文算法在软硬２种时间窗下，求得最优解的概率分别为９０％和７５％。由此可以看出本文算法具有较快的收敛速度和较高的稳定性。 表２实例ｌ。软时间窗下算法运行结果 第２个实例［６］，该问题有８个客户，顾客的装货或卸货的时间为Ｔｉ，一般将ｔ作为车辆的行驶时间的一部分计算费用，ｇｆ和［ｎ，，６ｉ］的含义同前，具体数据见表４。这些任务由仓库发出的容量为８ｔ的车辆来完成，车辆行驶速度为５０，仓库以及各个顾客之间的距离见表５。 ６），达到最优解的概率为８０％，其最终结果与文献［６］中相同最优解其费用值为９１０，对应的子路径
为（Ｏ一３一ｌ一２—０）、（Ｏ一６—４一Ｏ）、（Ｏ一８—５—７一Ｏ）。然而，文献 ［６］是在ｍａｘｇｅｎ＝５０、ｐｏｐｓｉｚｅ一２０的情况下，达到最优解的概率为６７％。这又说明了本文算法的有 效性。 表６实例２的算法运行结果 ４ 结语 尽管用带有子路径分隔符的自然数编码作为遗传算法解决ＶＲＰＴＷ问题的编码方式有其优点，但缺陷也是显而易见的，为了弥补该缺陷，本文去掉了 子路径中的分隔符，并采用Ｓｐｌｉｔ作为解码方式，就此设计了求解ＶＲＰＴＷ的遗传算法，并进行了数值试验的对比分析，试验结果表明，该算法是十分有
效的。参考文献 ＤａｎｔｚｉｑＧ，Ｒａｍｓｅｒ Ｊ．Ｔｈｅｔｒｕｃｋｄｉｓｐａｔｃｈｉｎｇｐｒｏｂｌｅｍ ［Ｊ］．Ｍａｎａｇｅｍｅｎｔ ｓｃｉｅｎｃｅ，１９５９，１３（６）８０一９１． 谢秉磊，李军，郭耀煌．有时间窗的非满载车辆调 度问题的遗传算法［Ｊ］．系统工程学报，２０００，１５ （３）２９０一２９４． 宋伟刚，张宏霞，佟玲．有时间窗约束非满载车辆调度问题的遗传算法［Ｊ］．系统仿真学报，２００５，１７ （１１）２５９３—２５９７． 刘诚，陈治亚，封全喜．带软时间窗物流配送车辆路径问题的并行遗传算法
车辆路径问题(vehideRoutingProblem，vRP)是组合优化和运筹学领域研究 的热点问题之一，其主要研究满足约束条件的最优车辆使用方案以及最优的车辆路径方案。基于基本车辆路径问题的框架，研究满足生产经营和运作需要的各种车辆路径问题，并构建具有高质量和高鲁棒性(roubustuess)的问题求解算法对于提高生产经营管理水平和降低运作成木具有重要的理论意义和现实价值。 本文以车辆路径问题为研究对象，综合运用组合优化和现代启发式算法等工 具，对几类重要的车辆路径问题模型及其优化算法进行了系统的研究，主要研究工作及成果总结如下: 1.综述了车辆路径问题在定义车辆路径问题分类和扩展标准的基础上，给出了 车辆路径问题的研究综述。基于不同的分类标准，首先讨论了主要的标准车辆 路径问题扩展问题。在此基础上详细地综述了求解标准车辆路径问题的现代启 发式算法，系统地描述了各种算法的实现机理以及各种算法的性能比较结果。 2.综述了求解组合优化问题的现代启发式算法在给出组合优化问题和计算复杂 性定义的基础上，综述了求解复杂组合优化问题的各种现代启发式算法。 3.研究了开放式车辆路径问题通过松弛标准车辆路径问题中车辆路线为哈 密尔顿巡回(Hamiltoniantour)的假设，研究了车辆路线为哈密尔顿路径(Hamiltonianpath)的开放式车辆路径问题。该问题中车辆在服务完最后一个 顾客点后不需要回到车场，若要求回到车场，则必须沿原路返回。在首先给出 问题数学模型的基础上，提出了求解开放式车辆路径问题的蚁群优化算法。该 算法主体是一个在超立方框架下执行的侧只刃一侧工加尸蚂蚁系统，算法混合了禁忌搜索算法作为局部优化算法，同时集成了一个后优化过程来进一步优化最优解。基于基准测试问题，系统地研究了算法性能。同其它算法的性能比较结果 表明本文提出的蚁群优化算法是有效的求解开放式车辆路径问题的方法。 4.研究了带时间窗和带时间期限开放式车辆路径问题通过引入时间约束，研究 了两类新的满足时效性要求的开放式车辆路径问题—带时间窗和带时间期 限开放式车辆路径问题。首先构建了两类问题的数学模型，同时提出了求解两 上海交通大学博十学位论文 类问题的基于禁忌搜索的迭代局部搜索算法，该算法集成了不同的解接受标准 以及一个基于阂值接受的后优化过程。基于随机产生的测试问题的实验结果表明:基于禁忌搜索的迭代局部搜索算法可以有效地求解带时间窗和带时间期限 开放式车辆路径问题。 5.研究了带时间窗和随机旅行时间车辆路径问题通过对标准车辆路径问题的拓 展，引入新的边约束条件:时间窗、随机旅行时间和服务时间，研究了一类新 的随机车辆路径问题—带时IbJ窗和随机旅行时间车辆路径问题。根据不同 的优化标准，分别构建了问题的机会约束规划模型以及带修正随机规划模型。 机会约束规划模型是在随机约束以一定的置信水平成立的条件下最小化运输费用。带修正的随机规划模型是一个两阶段优化问题，其确定第一阶段的路线集 以最小化第二阶段(随机变量实现后)的期望运输费用。鉴于问题的随机特 性，为了有效求解该问题提出了基于随机模拟的禁忌搜索算法。同时基于随机 产生的测试问题通过实验检验了算法有效性。 6.研究了固定车辆数异型车辆路径问题在车辆路径问题经典文献中，一般均假 设车辆同质目‘车辆数无限。然而在实际运作中，车辆集一般是由具有不同属性(装载能力、固定成本以及单位公里可变费用)的车辆组成，且受运作成本的
车辆路径问题优化算法 美国物流管理学会(Council of Logistics Management，CLM)对物流所作的定义为：“为符合顾客的需要，对原料、制造过程中的存货与制成品以及相关信息，从其起运点至最终消费点之间，做出的追求效率与成本效果的计划、执行与控制过程。” 而有关资料显示，物流配送过程(包含仓储、分拣、运输等)的成本构成中，运输成本占到52%之多。因此，如何在满足客户适当满意度的前提下，将配送的运输成本合理地降低，成为一个紧迫而重要的研究课题，车辆路径问题正是基于这一需求而产生的。 2.1车辆路径问题的定义 车辆路径问题可以描述为：给定一组有容量限制的车辆的集合、一个物流中心（或供货地）、若干有供货需求的客户，组织适当的行车路线，使车辆有序地通过所有的客户，在满足一定的约束条件（如需求量、服务时间限制、车辆容量限制、行驶里程限制等）下，达到一定的目标（如路程最短、费用极小、时间尽量少、使用车辆数尽量少等）。[4] 因此研究车辆的路径问题，就是要研究如何安排运输车辆的行驶路线，使运输车辆依照最短的行驶路径或最短的时间费用，依次服务于每个客户后返回起点，总的运输成本实现最小。车辆路径问题已被证明是NP-Hard问题，因此求解比较困难。然而，由于其在现实生活中应用非常广泛，使得它无论在理论上还是在实践上都有极大的研究价值。 Penousal Machado等人[5]指出车辆路径问题(vehicle routing problem，简称VRP)是一个复杂的组合优化问题，是古老的旅行商问题和背包问题的综合。实际上，车辆路径问题通常可被分解或转化成一个或几个已经研究过的基本问题，再采用相应比较成熟的基本理论和方法，以得到最优解或满意解。 这些与车辆路径问题相关的常用基本问题有；旅行商问题、运输问题、背包问题、最短路问题、最小费用最大流问题、中国邮路问题、指派问题等。 旅行商问题可被描述为：一个推销员欲到n个城市推销商品，每2个城市之间的距离是已知的。如何选择一条路径使推销员依次又不重复地走遍每个城市后，回到起点且所走的路径最短。 运输问题关心的是（确实的或是比喻的）以最低的总配送成本把供应中心（称为出发地，sources）的任何产品运送到每一个接受中心（称为目的地，destinations）。运输问题需要的数据仅仅是供应量、需求量和单位成本。 背包问题是指有一只固定容量的背包和若干体积、重量不等的物品，背包的容量不允许装下这所有的物品，那么如何选择适当的物品装入背包，使得背包的装载量（所装物品的重量之和）最大。 最短路径问题解决的是在一个网络中，如何寻找两点之间的最短路径。这两点之间通常没有直接的通路可达，但可经由若干中间结点相通。 最小费用流问题主要解决如何以最小成本在一个配送网络中运输货物。最小费用流问题又称为网络配送问题。 最大流问题和最小费用流问题一样，也与网络中的流有关。但是它们的目标不同，最大流问题不是使得流的成本最小化，而是寻找一个流的方案，使得通过网络的流量最大。 中国邮路问题是由我国管梅谷同志在1962年首先提出的，它可描述为：一个邮递员负责某一个地区的信件投递。每天要从邮局出发，走遍该地区所有的街道再返回邮局，问应该怎样安排送信路线可以使所走的路程最短。 指派问题解决将n件工作安排给m个人完成的问题。已知不同人完成不同工作的效率（或成本）不同，指派问题要求以最高的效率（或最小的人工成本）完成工作的安排。 2.2车辆路径问题的分类
一、车辆路径问题描述和建模 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)
????????? ?仈?ウ?? ??????????? ?仈а? ?? 亶 ??ウ???а? ???? ?仈? ?? ? ? ?? 学?仈 ??????ウ? ? ? ??? ?? ??????????? ?仈??? ?????? The Current Situation and Development Trends on Vehicle Routing Problems of distribution management Abstract: Vehicle routing problem is one of the attractive research area in the circles of operations research. In this paper, on the basis of introducing briefly the application background, the research classified the vehicle routing problem, analyzed and summarized the progress of different type of problems and solution algorithms. Furthermore, the research progress of the problems is also discussed. It is expected to provide inference for relevant research work. Key words: distribution management; vehicle routing problem; heuristics; overview.
粒子群优化算法 计算车辆路径问题 摘要 粒子群优化算法中,粒子群由多个粒子组成,每个粒子的位置代表优化问题在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 = ∑∑∑ 。经过初始化粒子群，将初始的适应值作为每个粒子的个
车辆路径优化及算法综述 袁建清 （黑龙江东方学院计算机科学与电气工程学部，黑龙江哈尔滨１５００８６ ）摘 要：阐述了ＶＲＰ的主要求解算法， 在参阅大量文献基础之上以禁忌搜索算法、遗传算法、蚂蚁算法三种主要的算法为划分总结了ＶＲＰ的研究现状以及三种算法的改良与应用情况，最后对车辆调度问题进行了展望，提出了进一步发展动向。 关键词：车辆路径问题；ＶＲＰ； 算法中图分类号：ＴＰ３１２ 文献标识码：Ａ 文章编号：１６７２－７８００（２０１１）０７－００６０－ ０２作者简介：袁建清（１９７９－） ，女，黑龙江穆棱人，硕士，黑龙江东方学院讲师，研究方向为信息管理。０ 引言 车辆路径问题（Ｖｅｈｉｃｌｅ Ｒｏｕｔｉｎｇ Ｐｒｏｂｌｅｍ，ＶＲＰ）是指在客户需求和位置已知的情况下， 确定车辆在各个客户间的行驶路线，使得运输路线最短或运输成本最低。对运输车辆进行优化调度，通过选择车辆的最佳运输路径，合理安排车辆调度顺序， 可以有效减少车辆的空驶率和行驶距离。它是物流系统优化环节中关键的一环。已经典型应用到牛奶配送、 报纸和快件投递、垃圾车的线路优化及连锁商店的送货线路优化等众多社会领域，而且在工业管理、物流管理、交通运输、通讯、电力、计算机设计等领域都有广泛的应用。 １ ＶＲＰ求解算法 ＶＲＰ是一个ＮＰ难问题， 因此根据各具体类型问题的特点应用启发式算法算法求解已经成为研究的主流。其中传统启发式算法主要有节约算法、插入算法、二阶段算法法等；现代启发式算法主要有禁忌搜索算法（ＴａｂｕＳｅａｒｃｈ，ＴＳ）、遗传算法（Ｇｅｎｅｔｉｃ Ａｌｇ ｏｒｉｔｈｍ，ＧＡ）、模拟退火算法（Ｓｉｍｕｌａｔｅｄ Ａｎｎｅａｌｉｎｇ，ＳＡ）、蚂蚁算法（ａｎｔ ｃｏｌｏｎｙｏｐ ｔｉｍｉｚａｔｉｏｎ，ＡＣＯ）等。近年来应用最多的是禁忌搜索算法、 遗传算法、蚂蚁算法以及它们之间或它们与传统启发式算法之间的结合形成的混合算法。 （１）禁忌搜索算法（ＴＳ） ：是一种全局优化搜索算法，通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。但是存在对初始解有较高的依赖性的缺点。 （２）遗传算法（ＧＡ） ：是一种基于自然进化原理的全局搜索随机算法，它使用群体搜索技术，通过对当前群体施 加选择（ｒｅｐｒｏｄｕｃｔｉｏｎ）、交叉（ｃｒｏｓｓｏｖｅｒ）及变异（ｍｕｔａｔｉｏｎ）等一系列遗传操作，从而产生出新一代的群体，并逐步使群体进化到包含或接近最优解的状态。该算法有局部搜索能力不强、易陷入早熟、总体上可行解的质量不是很高的缺点。 （３）蚁群算法（ＡＣＯ） ：是一种概率搜索算法，它模拟蚂蚁群体在觅食过程中所体现出的智能行为， 利用信息激素为媒介进行间接的信息传递，根据信息素的强度做出对较优解的选择。此算法有易陷入早熟、停滞、局部最优的缺点。 ２ ＶＲＰ研究现状 ＶＲＰ一直是物流届研究的热点问题， 纵观国内外学者研究都是通过对以上几种算法进行改良或将其结合形成有效地混合算法， 而对不同约束条件下车辆路径优化问题进行求解。本文针对三种主要算法总结研究现状如下：（１ ）应用遗传算法研究。文献分别用改进的遗传算法、免疫遗传算法、小生境遗传算法、以及与爬山算法、禁忌搜索算法、 蚁群算法相结合的混合算法对时间窗的车辆路径优化问题（ＶＲＰＴＷ）进行了求解。另外：张海刚等提出用基于自然数编码的遗传算法同时处理有软硬时间窗的ＶＲＰ，魏航等设计了基于自然数编码的遗传算法，针对有行驶里程限制的多车场满载车辆调度问题。 （２ ）应用禁忌搜索法研究。学者们对禁忌搜索法的应用主要针对两方面进行改良。一是构造好的初始解，在这方面主要形成三种方法：①随机排列，然后将顾客按序列聚类分配到每辆车，从而产生每辆车的路径；②先分组，然后在每个组内采用旅行商算法产生初始解；③用Ｃ－Ｗ启发式构造线路。二是通过改进邻域移动方法构造候选
文献综述 车辆调度算法研究及其应用 一、前言部分 车辆调度问题是现代物流系统优化中关键的一环，也是开展电子商务不可缺少的内容。对车辆调度优化理论与算法进行系统研究是构建综合物流系统、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础[1]。 车辆调度问题是运筹学与组合优化领域的研究热点。有效的调度车辆，不仅可以提高物流工作效率，而且能够为及时生产模式的企业提供运输上的保障，从而实现物流管理科学化。由于该问题的理论涉及很多学科，很多实际问题的理论抽象都可归结为这一类问题，研究该问题具有很重要的理论意义和实际意义。 1 . VRP（Vehicle Routing Problem）问题描述及其分类 VRP问题一般可定义为：对一系列的装货点或卸货点，组织适当的行车路线，使车辆 有序地通过它们，在满足一定的约束条件(货物需求量、发送量、车辆容量限制、行驶里程限制、时间限制)下，达到一定的目标(路程最短、时间最小、费用最省、车辆数目最少等)。由于该问题研究范围非常广，根据其网络性能大致可以分为两类：一类为静态 VRP (StaticVRP, SVRP)，一类为动态VRP (dynamic VRP, DVRP)。 (1)静态VRP问题描述 SVRP 问题是VRP 中较简单的一类问题，是大部分研究者研究的热点。该问题具有一 个很重要的特征：在安排初始路线时，和路线相关的所有信息已知，并且在安排路线以后其相关信息始终保持改变[2]。以下列举了一些常见的SVRP 问题:仅考虑车辆容量限制的 VRP(CVRP)、带时间窗的VRP(VRPTW)、带有回收的VRP(VRP with backhauls)、带有集派的VRP(VRPPD)。除此以外，还有许多其它 CVRP 的延伸问题，如顾客有优先权，考虑卸货时间、装卸时间、等待时间等，甚至综合了以上不同的特征。这些问题的相关信息均已知且保持不变[3]。 (2)动态VRP问题描述 所谓DVRP，是指在安排初始路线时，并不是和路线相关的所有信息都为已知，并且初始路线安排以后，其相关信息可能发生改变。DVRP 研究范围较广，需求不确定、动态网络、服务车辆不确定、提供数据有偏差等都属于DVRP 的研究范畴。从网络性能角度，DVRP 可以分为以下三种类型：1)时间依赖型VRP (TDVRP)。2)概率VRP (PVRP)。车辆运行时间以离散
物流配送的车辆路径优化 专业：[物流管理] 班级：[物流管理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展开了研究，共包括五章内容。首先，本文收集国内外关于
摘要：作为现代物流领域的研究前沿，车辆路径问题的求解算法及应用领域一直是学者研究的重点。本文在研读大量文献的基础上介绍了遗传算法的研究现状及其应用情况，并对车辆路径优化在生鲜农产品配送上的应用进行了简单的综述。 关键词：车辆路径问题；遗传算法；生鲜农场品；研究综述 一、引言 车辆路径问题最早在60年代被提出，dantzig和ramser首次在交通领域提出该问题就立即引起了社会的广泛关注。发展到现如今，车辆路径问题的应用已经跳出了交通领域，在别的很多领域被使用，如：通讯、工业管理、航空等。 二、遗传算法 1.遗传算法简介 达尔文的生物进化论自被提出以来就一直被科学家们广泛应用到各个领域。60年代时美国科学家结合进化论，提出了遗传算法。跟大自然中生物优胜劣汰的进化过程类似，遗传算法在计算过程中模拟了自然界各种群由简单到复杂，由低级到高级的进化过程，不断进化种群，直至使种群达到包含最优解或接近最优解的状态。 2.遗传算法研究现状 遗传算法作为一种群体随机搜索方法，在车辆路径问题研究中运用很多。很多国内外的研究学者对基础的遗传算法进行了改良，以期达到求解不同约束条件下车辆路径优化问题的目的。通过研究撰写遗传算法的文献发现，研究学者们分别用各种改进遗传算法对车辆路径问题进行了求解，如：免疫遗传算法、小生境遗传算法，以及遗传算法与爬山算法、禁忌搜索算法、蚁群算法相结合的混合算法。 将基础的遗传算法与改进的遗传算法进行对比仿真实验，可以发现经过改良的遗传算法，其各方面能力都更优。罗勇等为了求解更优的物流配送路线，就采用了针对性改进的遗传算法。通过研究发现，改良后的算法不仅收敛速度变快，而且全方位寻优的能力也有很大提高。由此可见改进的遗传算法是能更好的处理物流配送路径问题。基础的遗传算法有容易陷入局部最优和早熟的缺点，为了解决这个问题，周艳聪等设计了基于小生境技术的改进遗传算法，还在改进的遗传算法的基础上求解了物流配送路径的优化问题。不仅如此，还通过对物流配送过程的研究，建立了不带时间窗约束的物流配送优化模型。大规模车场的车辆路径问题是车辆路径优化问题中的一个难点，一直是学者们研究的重点。李波等引入了双层模糊聚类方法，针对基础的遗传算法进行了改进，得到了求解该问题的基本框架。通过随机的实验算例证明，所提出的方法是有效可行的。 三、车辆路径问题在生鲜农产品配送中的应用 对近年来，针对生鲜农产品配送路径问题的研究已经越来越多，人们对绿色食品的质量要求不断提高，是导致该问题备受关注的根本原因。容易腐烂变质，存放不易是大多数生鲜农产品的特点。而在整个销售过程中，生鲜农产品需要经历从农户手中到经销商手中这样一个配送过程，尽可能在配送过程中选择合适的路径，节约时间，保证生鲜农产品的质量，从而保证农户、经销商、消费者的利益就变得越来越重要。 为了保证生鲜农产品的质量、安全，生鲜农产品配送过程中的时效性一直是各个学者研究的关注点，大多数相关文献的模型建立都是以配送时间最短和配送成本最低为目标。王红玲等学者的研究考虑了生鲜农产品的特点构建了以生鲜农产品在途时间最短、配送成本最低为优化目标的农产品配送模型，并采用经过改进后的粒子群算法进行求解。由于生鲜农产品的时效性强的特点，对带时间窗的车辆路径问题的研究也相当多。邱荣祖等在分析了农产品的物流配送模式的基础上，建立了有时限的物流配送路径优化模型，并应用gis于禁忌搜索算法集成技术进行求解。文献中还选用了具体的数据进行了实验的验证，进行了初步的应用
第6卷第5期 2006年10月交通运输系统工程与信息JournalofTransportationSystemsEngineeringandInformationTechnologyVol16No15Oct ober2006文章编号:100926744(2006)0520065205多配送中心车辆调度问题的模型与算法研究 (北京交通大学交通运输学院,北京100044) 摘要:在对多配送中心车辆调度问题进行直观描述的基础上,建立了该问题的数学模 型。提出了采用距离最近分配法将多配送中心车辆调度问题分解为多个单配送中心车 辆调度问题进行求解的策略.,设计了求解多配送中心车辆调度问题的算法,.,用本文设计的算法求解多配送中心车辆调度问题,,计算效率较高,收敛速度较快,关键词:中图分类号:U491 ModelandAlgorithmforMulti2Depot VehicleSchedulingProblem LANGMao2xiang(SchoolofTrafficandTransportation,BeijingJiaotongUniversity,Beijin g100044,China) Abstract: Onthebasisofintuitionisticdescriptionofthemulti2depotvehicleschedulingproblem,many math2 ematicmodelsoftheproblemisbuiltinthispaper.Thesolvingtacticsofdividingamulti2depotv ehiclescheduling problemintoseveralsingle2depotvehicleschedulingproblemsbyusingtheminimumdistance distributionmethodis presented.Thealgorithmforthemulti2depotvehicleschedulingproblemisdesignedbasedont hetaboosearchal2 gorithmforsingle2depotvehicleschedulingproblem.Thecomputationalresultsdemonstrate sthatthehighquality solutionstothemulti2depotvehicleschedulingproblemcanbeobtainedbyusingthenewalgori thmandthealgo2 rithmisalsoefficientandrobust. Keywords:multi2depotvehicleschedulingproblem;model;algorithm
蚁群算法在车辆路径问题中的应用 摘要 蚁群算法（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问题的蚂蚁算法中，每只蚂蚁是一个独立的用 于构造路线的过程，若干蚂蚁过程之间通过信息素值来交换信
第２９卷第４期２００８年４月 东北大学学报（自然科学版） ＪｏｕｒｎａｌｏｆＮｏｒｔｈｅａｓｔｅｒｎＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅ） Ｖ０１．２９．Ｎｏ．４ Ａｐｒ．２００８动态车辆路径问题的优化方法 刘士新，冯海兰 （东北大学流程工业综合自动化教育部重点实验室，辽宁沈阳１１０００４） 摘要：设计了在动态环境下进行车辆路径优化的导向局域搜索算法．算法在产生初始解以后的动态求解过程中，不再做车辆之间的顾客调整，而只应用２－ｏｐｔ局域搜索算子更新车辆服务顾客的顺序，即针对每辆车辆的旅行路线求解一个旅行商问题．建立了在动态环境下车辆执行运输任务过程的仿真模型．仿真过程中，应用算法根据交通路网实际情况实时优化车辆路径。并采用４种接受准则判别是否接受新的车辆路径．仿真结果表明：算法具有实时、高效的特点，满足动态车辆路径问题的求解要求． 关键词：智能交通系统；动态车辆路径问题；交通模拟；导向局部搜索 中图分类号：Ｃ９３４文献标识码：Ａ文章编号：１００５—３０２６（２００８）０４—０４８４—０４ ＯｐｔｉｍｉｚａｔｉｏｎＡｐｐｒｏａｃｈｔｏＳｏｌｖｉｎｇＤｙｎａｍｉｃＶｅｈｉｃｌｅＲｏｕｔｉｎｇＰｒｏｂｌｅｍｓ Ｌ儿，Ｓｈｉ．ｘｉｎ，ＦＥＮＧＨ．口ｉ—ｌａｎ （ＫｅｙＬａｂｏｒａｔｏｒｙｏｆＩｎｔｅｇｒａｔｅｄＡｕｔｏｍａｔｉｏｎＤｆＰｒｏｃｅｓｓＩｎｄｕｓｔｒｙ，ＭｉｎｉｓｔｒｙｏｆＥｄｕｃａｔｉｏｎ，ＮｏｒｔｈｅａｓｔｅｒｎＵｎｉｖｅｒｓｉｔｙ，Ｓｈｅｎｙａｎｇ１１０（）０４，Ｃｈｉｎａ．Ｃｏｒｒｅｓｐｏｎｄｅｎｔ：ＬＩＵＳｈｉ—ｘｉｎ，Ｅ－ｍａｉｌ：ｓｘｌｉｕ＠ｍａｉｌ．ｎｅｕ．ｅｄｕ．ｃｎ） Ａｂｓｔｒａｃｔ：Ａｇｕｉｄｅｄｌｏｃａｌｓｅａｒｃｈ（ＧＬＳ）ａｌｇｏｒｉｔｈｍｉｓｐｒｅｓｅｎｔｅｄｔｏｓｏｌｖｅｄｙｎａｍｉｃｖｅｈｉｃｌｅｒｏｕｔｉｎｇｐｒｏｂｌｅｍｓ（ＤＶＲＰ）．Ｉｎｔｈｅｄｙｎａｍｉｃｓｏｌｖｉｎｇｐｒｏｃｅｓｓａｆｔｅｒａｌｌｉｎｉｔｉａｌｓｏｌｕｔｉｏｎ，ｔｈｅＧＬＳｄｏｅｓｎｏｔｅｘｃｈａｎｇｅｃｕｓｔｏｍｅｒｓｂｅｔｗｅｅｎｖｅｈｉｃｌｅｓｂｕｔａｐｐｌｉｅｓｔｈｅ２一ｏｐｔｌｏｃａｌｓｅａｒｃｈｏｐｅｒａｔｏｒｔｏｕｐｄａｔｉｎｇｔｈｅｓｅｒｖｉｃｉｎｇｓｅｑｕｅｎｃｅｆｏｒｃｕｓｔｏｍｅｒｓ，ｉ．ｅ．，ｔｏｓｏｌｖｅａｔｒａｖｅｌｉｎｇｓａｌｅｓｍａｎｐｒｏｂｌｅｍｏｆｔｒａｖｅｌｉｎｇｒｏｕｔｉｎｇｏｆｅａｃｈｖｅｈｉｃｌｅ。Ａｓｉｍｕｌａｔｉｏｎｍｏｄｅｌｉｓｔｈｕｓｄｅｖｅｌｏｐｅｄｆｏｒｔｈｅｄｙｎａｍｉｃｐｒｏｃｅｓｓｄｕｒｉｎｇｗｈｉｃｈｖｅｈｉｃｌｅｓａｒｅｉｎｔｒａｆｆｉｃ．ＩｎｔｈｅｓｉｍｕｌａｔｉｏｎｍｏｄｅｌｔｈｅＧＬＳａｌｇｏｒｉｔｈｍｉｓａｐｐｌｉｅｄｔｏｏｐｔｉｍｉｚｉｎｇｔｈｅｖｅｈｉｃｌｅｒｏｕｔｅｓｉｎａｃｃｏｒｄａｎｃｅｔｏｔｈｅｒｅａｌ—ｔｉｍｅｔｒａｆｆｉｃｓｉｔｕａｔｉｏｎ，ａｎｄｆｏｕｒｒｕｌｅｓａｙｅａｐｐｌｉｅｄｔｏｊｕｄｇｉｎｇｉｆｔｈｅｎｅｗｌｙｏｐｔｉｍｉｚｅｄｖｅｈｉｃｌｅｒｏｕｔｅｓａｒｅａｃｃｅｐｔｅｄ．ＴｈｅｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｒｅｖｅａｌｔｈａｔｔｈｅＧＬＳ ａｌｇｏｒｉｔｈｍｃａｎｐｒｏｖｉｄｅｒｅａｌ－ｔｉｍｅｒｅｓｐｏｎｓｅｔｏｄｙｎａｍｉｃｉｎｆｏｒｍａｔｉｏｎｔｏｓａｔｉｓｆｙｔｈｅｒｅｑｕｉｒｅｍｅｎｔｓｏｆｓｏｌｖｉｎｇＤＶＩ王Ｐ． Ｋｅｙｗｏｒｄｓ：ｉｎｔｅｌｌｉｇｅｎｔｔｒａｎｓｐｏｒｔａｔｉｏｎｓｙｓｔｅｍ；ＤＶＲＰ；ｔｒａｆｆｉｃｓｉｍｕｌａｔｉｏｎ；ＧＬＳ 物流优化已经成为当代企业的一个重要利润源泉．车辆路径问题（ｖｅｈｉｃｌｅｒｏｕｔｉｎｇｐｒｏｂｌｅｍｓ，Ⅵ冲）是物流领域的核心和热点研究问题，吸引了众多学者和业者的研究和关注．现代物流市场的激烈竞争和顾客的个性化需求不断提高，使得现代物流配送运作更加复杂，要求物流配送系统更加灵活、高效地针对变化的环境调整作业计划．计算机及通讯技术的迅速发展，使得交通状况及运输工具的实时信息更易获取，为解决物流配送面对的新问题提供了基础．动态ＶＲＰ（ｄｙｎａｍｉｃＶＲＰ，ＤｖＲＰ）正是在这样的背景下开始受到了关注和研究．现有研究主要是针对环境变化，对车辆路径计划进行重计划或局部调整，涉及的方法有元启发式算法和局域搜索算法等【１－２Ｊ．本文针对城市复杂交通系统的环境变化，提出了一种ＤＶＲＰ中更新车辆路径的导向局域搜索（ｇｕｉｄｅｄｌｏｃａｌｓｅａｒｃｈ，ＧＬＳ）算法，设计了动态交通环境的仿真模型，通过对７１个节点交通路网的仿真实验，得出了咖车辆路径的更新原则，研究成果对于现代城市智能交通系统中的车辆路径优化 收稿日期：２００７一０４—０５ 基金项目：国家自然科学基金资助项目（７０３０１００７，７０７７１０２０，７０４３１００３）；新世纪优秀人才支持计划项目（ＮＣＥＴ－０６－０２８６）．作者简介：刘士新（１９６８一），男，辽宁调兵山人，东北大学教授． 万方数据