物流配送车辆调度问题算法综述

陈君兰， 叶春明 （上海理工大学 管理学院，上海 200062）

CHEN Jun-lan, YE Chun-ming (Manage School,University of Shanghai for Science and Technology,Shanghai 200062,China)

配送是物流中的一个环节，一般的配送包括装卸、包装、保管、运输，其目的就是将货物成功送达。而特殊的配送以加工活动为支撑，包括更广泛的方面。配送过程中有两个重要环节，一个是运输，另一个是分拣配货，分拣配货就是根据特殊的要求，将货物根据送货时间、送货地点等具体要求，将货物送达。所以分拣是配送的独特要求，而运输则是最后实现配送的主要手段。随着物流体系的发展，人们常将配送的各个环节综合起来考虑，而核心部分就是配送的车辆、货物装卸及送货。因而配送车辆优化调度就成为人们关注的焦点，其中包括集货线路优化、货物配装及送货线路优化，以及集货、货物配装和送货一体化优化等等。

无论是对于物流中心，还是第三方物流公司，物流配送运输车辆的调度都是工作重点，通过减少运输成本、节约运输时间，从而提高经济效益。

1 配送车辆调度优化问题的分类

车辆路径调度问题的一般定义为：对一系列发货点和收货点，组织适当的行车路线，使车辆有序通过它们，在满足一定的约束条件下 （如货物需求量、车载量、交发货时间、行车里程、时间限制，路线约束等），达到一定目标最优化 （如路程最小、运费最少、时间准时、车辆较少等）。

1.1 按时间因素分类

配送车辆调度优化问题可以简单地分为三类，第一类问题称为车辆路径规划问题 （Vehicle Routing Problems，VRP），VRP问题关注为车辆安排合理、高效益的线路，仅是在空间上对问题进行优化，而不考虑时间因素。第二类问题称为车辆调度问题 （Vehicle Scheduling Problems，VSP），VSP问题也关注合理、高效安排车辆行车路线，所不同的是，VSP问题考虑的是在满足时间要求的前提下实现最优调度。第三类问题称为路径和调度的混合问题 （Vehicle Routing And Scheduling Problems，VRP&VSP），就是将前两类问题综合考虑的问题。而目前也有学者不区分VRP和VSP问题，而是将考虑时间因素的VSP问题称为VRPTW （Vehicle Routing Problem with Time Windows）问题。

1.2 按性质分类

车辆优化调度问题可以根据其不同的性质分为以下几类：

（1）按运输任务可以分为纯装问题、纯卸问题和装卸混合问题。纯装问题就是每一项任务只有装货点，是一个集货的过程。纯卸问题是指每一项任务只有卸货点，是一个送货的过程。而装卸混合问题是指每一项任务有不同的装货点和卸货点，是集货、送货一体化的过程。

（2）按车辆载货情况可以分为满载问题和非满载问题。满载问题是指一次任务的货运量多于车辆的最大容量，而非满载问题是指一次任务的货运量不多于车辆的最大容量。

（3）按车辆类型分为单车型问题和多车型问题。单车型问题指所有车辆的容量都给定同一值，多车型问题指所有车辆的容量都给定不同值。

（4）按车场的数量可以分多车场和单车场问题。因为多车场问题可以转化为单车场问题，而且通常一个车场 （仓库）都会有固定的服务对象。根据传统的处理方法，在将多车场问题转化为单车场问题的过程中，先设一个虚拟车场，将所有配送点和实际车场都看作虚拟车场的配送点，这样就转化为单车场问题了。所以这里的算法只考虑单车场问题。

（5）按车辆是否返回车场可以分为车辆开放问题和车辆封闭问题。车辆开放问题是指在车辆开出车场以后不返回车场。而车辆封闭问题是指在车辆开出车场以后返回其发出车场。

（6）按优化目标可以分为单目标优化问题和多目标优化问题。单目标优化问题是指目标函数只要求一项指标最优，如要求运输路径最短。多目标优化问题是指目标函数要求多项指标最优或较优，如同时要求运输费用最少和运输路径最短。

（7）按货物种类可分为同种货物优化调度和多种货物优化调度。同种货物优化调度是指要运输的货物的种类只有一种。多种货物优化调度是指要运输的货物的种类多于一种，所以车辆装载时要考虑一些种类的货物不能同时装配运输。

（8）按有无休息时间要求可分为有休息时间的优化调度问题和无休息时间优化的调度问题。

（9）按有需求点有无时间窗要求，可分为无时间窗问题、硬时间窗问题、软时间窗问题。硬时间窗问题指车辆必须在时间窗内到达，早到则等待，晚到则拒收。软时间窗问题指车辆不一定要在时间窗内到达，但是在时间窗外到达必须受到惩罚。

建立车辆调度问题模型如下：

目标函数：a.单目标，b.多目标 （目标函数包括总费用最小、总里程最小、休息时间最大、惩罚最少等）

约束条件：a.时间约束 （无时间窗、硬时间窗、软时间窗）

b.距离约束 （无距离限制、硬距离限制、软距离限制）

c.行车路线约束 （无相交性限制、顶点不相交）

d.流量限制 （无流量限制、边限制、顶点限制）

e.满载限制 （满载，非满载）

f.其它要求

2 物流配送车辆调度算法综述

在求解车辆优化调度问题时，可以将问题归类为几个简单的组合优化基本原型，如旅行商问题（TSP）、最短路径问题、最小费用流问题、中国邮递员问题等，再用相关的理论和方法进行求解，得到模型最优解或较优解。

一般求解VRP问题主要可分两大类，一类是精确算法；一类是启发式算法。精确算法主要有分支定界法、割平面法、线性规划法、动态规划法等，它的主要思想是根据问题先建立具体的数学模型，然后利用数学方法进行求解。启发式算法主要有构造法、人工智能法等，如构造算法、两阶段法、神经网络法、遗传算法等，它的主要思想是根据直观和经验开发出能朝着最优解方向搜索或靠近的算法。

由于车辆优化调度问题的规模大、复杂性强，而各种计算和实验得出，智能算法在求解这类问题时有较强的可行性，所以这里仅探讨智能算法求解车辆优化调度问题。

2.1 遗传算法

遗传算法 （Genetic Algorithm，GA）由美国J.Holland和他的学生于1975年建立并发展起来的。遗传算法是根据自然选择和遗传理论，将生物进化过程中适者生存规则与同一群染色体的随机信息交换相结合的智能算法。遗传算法的基本思想是：首先，通过一组编码，将问题在表现型与基因型之间转换，并形成初始种群，计算种群中个体的适应度；其次，设计遗传算子 （包括复制、交叉、变异），从对已产生的解 （“父代”）中根据交叉率，从部分个体中选取部分基因，按某种组合形成新的个体；根据变异率，从部分个体中选取部分基本变异，产生新的个体；同时将 “父代”中适应度高的个体进行复制，成为新一代个体，不断操作、迭代，以形成新的一组解 （“子代”），计算个体适应度。如此反复，可求出整个种群的最优解。

遗传算法具有良好的全局搜索能力，可以快速求出全局最优解，但存在过早收敛和搜索效率低、局部搜索能力低的缺点，导致算法比较费时。目前，许多遗传算法在车辆调度问题中应用的研究都通过对编码、遗传算子的设计、基因构建和定义、适应度定义等方面来改进算法效能，如李军[1]等设计最大保留交叉来保证群体的多样性求解非满载车辆调度问题等；也有许多学者通过在遗传算法中引入其它算法来增加其局部搜索能力，如张涛[2]等用3-OPT算法结合遗传算法来加强算法的局部搜索能力，得到针对车辆调度优化问题的混合算法等，而随着模型变化，车辆调度优化问题的求解算法也会有所改变，如Giselher[3]等利用GA算法对装卸混合问题进行了研究。可见，遗传算法正从多方面影响着车辆调度问题。

2.2 模拟退火算法

模拟退火算法 （Simulated Annealing，SA）由Kirkpatrick等人于1983年成功引入组合优化领域。模拟退火法是源于材料科学和物理领域的一种搜索过程。模拟退火算法的基本思想是：首先，任意选择一个初始状态，并设定初始温度和降温次数，并在邻域中产生另一个解，根据控制参数t选择接受和舍弃，经过大量操作后，求得给定t时优化问题的相对最优解；其次，通过降温函数，不断减小t的值直到0时的最后系统状态对应优化问题的全局最优解。前半部分是通过加热增加物体能量；后半部分是通过降温和冷却降低物体的能量。对应数学模式时，问题的解就是系统状态，而问题的目标函数就是物体的能量，因此求最优解的过程就是求能量最低态的过程。

模拟退火算法的优点是有很强的全局搜索能力，但是由于允许移动到较差的解，所以可能接受目标值不好的状态，从而使算法陷入局部最优，所以要求出最优解要花费较长时间。而模拟退火的有效性取决于邻域选择设计，如果邻域以一种促进移到更好解而移出局部极小解的方式设计，那么算法将会表现出其优越性。谢秉磊[4]等用模拟退火算法求解配送/收集旅行商问题；蔡延光[5]等用模拟退火算法求解多重运输调度问题等。由于模拟退火算法一个显著缺点就是收敛速度慢，因此在求解车辆优化调度问题时，多将模拟退火算法与其它智能算法结合，加快收敛速度。

2.3 禁忌搜索算法

禁忌搜索算法 （Tabu Search，TS）由Glover在1986年提出。禁忌搜索算法是用一个禁忌表记录已经到达过的局部最优解，确保在下一次搜索过程中，不再选择这些点，从而跳出局部最优解。禁忌算法的基本思想是：首先，从一个初始可行解s开始，确定解的搜索邻域N（）s，在这个邻域内选出最优解s'，则从s移到s'继续搜索；其次，设定禁忌表最大容量，将每次的移动根据先进先出准则放入禁忌表中，在每次迭代中，表中的移动是可能被禁止的，这都取决于一个渴望水平函数，这个函数用来评价移动的损益，如果损益是可以接受的，则移动不被禁止，反之，移动被禁止；最后，根据迭代停止准则，求出问题的最优解。

从上面的算法描述中可以看出，禁忌搜索算法的主要缺点是对初始解的依赖性很强，当遇到不好的初始解时，将会导致计算时间过长。而且禁忌表最大容量的设定对禁忌搜索算法来说也起着很重要的作用，因为如果容量过多，将会导致搜索被过分限制，造成时间浪费；而容量过少，会造成循环，不利于求解。由于禁忌搜索算法只能对一个解进行操作。钟石泉[6]等在求解多车场车辆调度问题时，以一组初始解的邻域作为搜索空间，突破点点操作，减少禁忌搜索算法对初始解好坏的依赖；并且采用局部、全局两种禁忌表来避免重复操作。但总体来说，禁忌算法比较容易与其它启发式算法相结合构建混合算法。结合之前介绍的两个算法，可以看出，遗传算法在每次迭代中都会生成很多不同的调度，而且会延续到下一次迭代，而在模拟退火法和禁忌搜索法中，只有一个调度从一次迭代延续到下一次迭代。

2.4 蚁群算法

蚁群算法 （Ant Colony Algorithm，ACA）由意大利学者M.Dorigo及其导师Colorni于1991年提出并用于求解TSP问题，它是根据自然界中蚂蚁觅食行为而提出的一种优化算法。蚁群通过寻找信息素浓度最高的路径，从而求出最佳路径。蚁群算法的基本思想是：首先，初始化各蚂蚁，将m只蚂蚁放在n个顶点上，并设定初始参数，并将初始解置于当前解集中；其次，每只蚂蚁根据选择策略和转移概率选择顶点，并将该顶点置于当前解集中，则蚂蚁从初始点转移，不断操作，直到所有的点都已置于解集中，则求出各蚂蚁的适应度，记录当前最优解；通过更新信息素，不断迭代，直到结束条件满足，求出种群进化后的最优解，也就是问题的最优解。

蚁群算法的优点是其正反馈机制和分步式计算。但对于规模较大的问题，其搜索时间长且易收敛至局部最优解。目前，蚁群算法收敛性方面的理论成果则非常稀少。马良[7]等通过在蚁群算法的基础上嵌入2-OPT等算法加速其循环最优解的得出来求解带容量限制的多目标车辆路径问题；陈金[8]等结合sweep和saving算法确定客户归属的混合算法求解带时间窗的中转联盟运输调度问题。而蔡延光[9]等人也提出调整选择策略、信息素浓度与挥发速度的同向关系调节信息素更新方程的方法改进传统蚁群算法求解带软时间窗的联盟运输调度问题。许多学者在求解车辆优化调度问题时都对蚁群算法作了多种改进，这些改进都具有很强的意义。

2.5 微粒群算法

微粒群算法 （Particles Swarm Optimization，PSO）由美国心理学家Kennedy[10]和电气工程师Eberhart于1995年提出。微粒群算法起源于鸟类在搜索食物过程中，个体之间可以进行信息的交流和共享，每个成员可以得益于所有其他成员的发现和飞行经历[11]。微粒群算法的基本思想是：首先，产生一组初始解，得到初始位置并初始化速度、个体最优解、全局最优解；然后，通过位置更新方程和速度更新方程产生一组新的解，并更新个体最优解和全局最优解；如此不断操作迭代，粒子渐渐向最优解靠近，直至到达循环结束条件，此时得到问题最优解。

微粒群算法有通用性强，具有记忆能力，保留个体和全局最优信息，协同搜索的优点。但微粒群算法局部搜索能力较差，通过多点同时搜索，使运算时间大大减少，但也造成了计算精度较差的特点，所以要设置迭代次数较多，此外算法对参数设置具有很强的依赖性。现在对微粒群算法的应用研究很多，朱露露[12]等采用量子算法与微粒群算法相结合的混合算法，通过采用一种二进制的编码方式求解了经典的车辆路径问题。因此在处理车辆优化调度问题时，也可以将其它算法的思想引入到微粒群算法中，从而克服其易陷入局部最优的缺点。

3 对未来研究方向的展望

车辆优化调度问题一直是配送运输领域关注的热点，诸多学者都对其进行了不少研究，也取得了不少成果。在对该问题的算法研究虽然种类很多，但实现起来都存在不少问题。根据学者们现有的研究发现，目前对算法的改进主要表现在以下几个方面：其一，通过混合算法的方式，结合各算法优点，弥补各算法缺点，形成一条可行的方案；其二，根据对自然界的不断探索以及结合交叉学科的方式，提出新的算法；其三，改进现有算法，就现有算法中各步骤中的细节进行调整。诸如此类的研究还在进行中，因此研究车辆优化调度问题是有潜力、有意义的。

[1] 李军，谢秉磊，郭耀煌.非满载车辆调度问题的遗传算法[J].系统工程理论方法应用，2000,9(3):235-239.

[2] 张涛，王梦光.遗传算法和3-OPT结合求解带能力约束的VRP[J].东北大学学报，1999,20(3):253-256.

[3] Giselher,Pankratz.A grouping genetic algorithm for the pickup and delivery problem with time windows[J].Operation Research,2005(27):21-41.

[4] 谢秉磊，李良，郭耀煌.求解配送/收集旅行商问题的模拟退火算法[J].系统工程理论方法应用，2000,11(3):40-43.

[5] 蔡延光，钱积新，孙优贤.多重运输调度问题的模拟退火算法[J].系统工程理论与实践，1998,18(10):11-15.

[6] 钟石泉，贺国光.多车场车辆调度智能优化研究[J].华东交通大学学报，2004,21(6):25-29.

[7] 马良，朱刚，宁爱兵.蚁群优化算法[M].北京：科学出版社，2008.

[8] 陈金，蔡延光.带时间窗的中转联盟运输调度问题的混合算法研究[J].工业控制计算机，2010,23(1):70-72.

[9] 蔡延光，师凯.带软时间窗的联盟运输调度问题研究[J].计算机集成制造系统，2006,12(11):1903-1908.

[10] Kennedy J,Eberhart R.Particle Swarm Optimization[C]//Proc.IEEE Int.Conf.on Neural Networks.Perth,WA,Australia:[s.n.],1995:1942-1948.

[11] 王凌，刘波.微粒群优化与调度算法[M].北京：清华大学出版社，2008.

[12] 朱露露，叶春明，何洋林.基于量子微粒群算法的车辆路径问题研究[J].物流科技，2008(5):12-14.

[13] 闫彦，张立丽，杨文雄.物流配送车辆优化调度方法初探[J].水运科学研究，2005,3(1):37-41.

[14] 师凯，蔡延光.联盟运输调度问题模型结构与算法研究[J].计算机技术与发展，2007,17(1):56-59.

[15] 潘凌，叶如意.规模车辆调度问题的有效算法分析[J].宁波大红鹰职业技术学院学报，2006,9(3):48-52.

[16] 李芳，郑晴，邱俊茹,等.带时间窗的某物流配送车辆调度问题的方案优化分析[J].数学的实践与认识，2010,40(17):176-181.

[17] 管显笋.基于微粒群优化算法的车间调度问题研究[D].秦皇岛：燕山大学 （硕士学位论文），2010.

[18] Fukuyama Y.Fundamentals of particle swarm techniques[C]//Lee K Y,El-Sharkawi M A.Modern Heuristic Optimization Techniques with Applications to Power Systems[s.l.]:IEEE Power Engineering Society,2002:45-51.

[19] （美）Pinedo M.调度：原理、算法和系统[M].2版.北京：清华大学出版社，2007.