动态车辆路径问题研究综述

韩娟娟，李永先

（辽宁师范大学，辽宁 大连116029）

1 引言

车辆路径问题（Vehicle Routing Problems，VRP）是一类具有重要实用价值的组合优化问题。VRP是指对安排适当的车辆路径，使车辆在满足约束条件下，经过一系列的发货点和（或）供货点并达到一定的目标。如果在车辆、时间、人员、顾客需求等信息都确定的情况下安排车辆路径，这类问题属于静态车辆路径问题。但在现实世界中，信息大多是不确定的，比如顾客需求、交通状况、天气状况、人员、车辆等信息的不确定，有些信息还会处在不断变动的状态，这对安排车辆路径造成了很大的困扰，需要根据不断更新的系统信息动态地安排车辆路径，这类问题属于动态车辆路径问题（DVRP）。根据动态信息的随机性和模糊性，动态车辆路径问题可以分为随机车辆路径问题和模糊车辆路径问题。如果可以根据历史资料或市场调查得到信息（顾客需求、车辆行驶时间、服务时间等）的概率分布或信息服从的某种变化规律，路径制定者根据信息的规律及得到的新的系统信息实时地规划车辆路径，这类问题就是随机车辆路径问题。但是，当需要的信息没有长期积累，不能获得信息的分布规律（如企业开辟新市场时，顾客的需求信息就是模糊的）或者信息不能清晰的被描述，这类问题就是模糊车辆路径问题。由于动态VRP更接近于实际的车辆配送情况，对于现实中的物流更具有应用价值，因此，动态VRP已经成为车辆配送领域研究的重点。

动态车辆路径问题是近年来国内外学术界研究的一个热点问题。本文对动态车辆路径问题的研究进行评述，分析了动态车辆路径问题在模型、算法、仿真方面的主要研究成果及存在的问题，提出了动态车辆路径问题的进一步发展方向。

2 动态车辆路径问题的研究进展

Wilson在20世纪70年代研究了动态VRP中的dial－a－ride问题，使得动态VRP受到关注。后来，Powell、Psaraftis、Gendreau等都对动态VRP的特征进行了研究，总结了动态车辆路径问题的特点。虽然动态车辆路径问题研究的历史不长，但是在静态车辆路径问题研究的基础上对动态车辆路径问题的研究还是取得了不小的进展，本文从模型、算法、仿真3个方面对动态车辆路径问题进行了综述。

2.1 动态VRP模型的研究进展

基于动态VRP实时性和复杂性的特点，动态VRP需要与之对应的新的模型和理论，一些学者在静态VRP研究的基础上，提出了一些新的模型来解决动态VRP。

Bertsimas等［1］研究了多车辆有容量约束的DVRP和动态旅行修理员问题，并提出了解决该问题的排队论模型。排队论模型成为研究动态车辆路径问题的一个重要的模型。Minkoff［2］提出了马尔可夫模型，但只能求解10个需求的小规模DVRP。Tillmar［3］在研究随机需求的车辆路径问题时，提出了一种惩罚模型，该模型规定当车的容量满足不了顾客服务要求时要按照一定的策略给予惩罚，这种模型有效地解决了路径失败的问题，对以后的研究有很好的借鉴作用。Stewart和Golden［4］提出了基于机会约束机制理论与二元可能性理论下的VRPSD的模型，这两个理论在以后的研究中应用的比较广泛。谢如鹤等［5］在对随机需求的VRP求解时，利用了一种基于车辆剩余能力的插入准则。葛显龙［6］研究了跨区域多配送中心动态需求的开放式VRP问题，提出了配送车辆共享和联合配送策略并建立符合实际的车辆路径优化模型，并利用云模型理论改进遗传算法对模型求解，得到了较好的结果。

Teodorovic和Pavkovic［7］最早研究了模糊顾客需求的VRP，顾客的信息和决策者的偏好用模糊数来表示，并建立了以倾向度为基础的模糊判定准则。Pavone［8］在动态车辆路径问题中首先考虑了顾客等待的耐心因素。祝祟隽［9］以模糊可能性分布，建立了车辆路径问题的基于置信度的三下标流模型，并提出了基于可能性分布的2－opt算法。陆琳等［10］考虑到配送者的经验对现实中的车辆路径制定的显著作用，建立了包含配送者经验的知识系统的FVRP模型，使模型不单纯理论化而更具现实应用意义。

虽然动态车辆路径的模型有了进一步的发展，但还是存在许多不足，比如这些模型大多是只考虑了一种或者两种不确定信息存在的情况，但是实际系统中有很多类型的不确定信息，对于这种情况还没有相应的模型，而且对不同信息之间的联系也没有建立对应的数学模型。考虑到多车辆多车型的动态VRP的模型还比较少，还不成熟。

2.2 动态VRP算法的研究进展

VRP是NP－hard问题，由于其约束条件多，节点规模大，难以用精确算法求解，所以对这类问题的求解一般要用启发式算法获得其满意解。常用的启发式算法有遗传算法、模拟退火算法、禁忌搜索算法、蚁群算法等，目前两种或者多种算法结合形成的混合算法经常被用来解决车辆路径问题。启发式算法的发展为解决VRP提供了新的思路，可以解决问题规模比较大、结构比较复杂的车辆路径问题。人们为了解决动态VRP，对启发式算法进行了改进。

1989年 Min［11］最早提出了 VRPSDP，采用先对顾客聚类，然后解决每一类顾客群体的TSP。在此基础上，对不可行路径进行补偿，从而优化各TSP路径。Chen和Gen［12］提出了一种利用推－碰－掷过程改进的混合遗传算法解决模糊车辆路径问题。Gendreau等求解动态车辆路径问题时，构造了一种具有自适应性的禁忌搜索算法，首先利用禁忌搜索算法求解，当新的需求出现时，停止运行禁忌搜索算法，并将当前的最优解存储到自适应存储单元，然后利用插入法将新的需求插入到自适应存储单元的所有解中，再继续使用禁忌搜索算法对加入了新的需求点后的动态车辆路径问题进行优化。Pureza［13］研究动态车辆路径问题时，不是按照新需求出现的顺序依次对应进行服务，而是设置一定的新需求点缓存区，在达到一定数量的新需求后再根据紧急程度安排车辆服务，这种方法更符合了实际情况。Liao［14］等将动态车辆路径问题分为两阶段处理，首先采用扫描法确定使用的车辆数量，再根据接受到的实时信息采用禁忌搜索算法优化路径。

甘勤涛等［15］利用禁忌搜索算法求解模糊需求VRP，郎茂祥等［16］研究了车辆多次巡回配送和考虑车辆故障的DVRP，利用两阶段策略求解该问题，第一阶段用禁忌搜索算法安排车辆路径，第二阶段当新的信息出现时采用局部搜索算法进行局部优化。谢秉磊等［17］研究了一类随机顾客和随机需求的车辆路径问题，需求的随机性增加了决策的复杂性和难度，首先提出了多回路策略，并设计了具有不同邻域结构的模拟退火算法。刘霞［18］把计划周期分片，将动态车辆路径问题转换成一系列的静态车辆路径问题，并用最大最小蚁群算法对一系列的静态车辆路径问题进行求解，根据数据集的特点采用并行法或顺序法构建路线。王连锋等［19］针对具有多重模糊性的模糊车辆路径问题，依据模糊可信性理论建立了模糊期望值模型，并基于MOPSO提出了自适应混合多目标粒子群优化算法。

虽然动态车辆路径问题在算法上有所改进，但是由于动态VRP的参数复杂，约束条件多，数学模型复杂，所以启发式算法也很难比较理想地解决现实中的动态车辆路径问题。

2.3 动态VRP仿真优化的研究进展

仿真是建立数学逻辑模型并在计算机上运行该模型进行实验的过程，仿真建模是模仿真实系统的行为，仿真是决策者用于车辆路径安排的最有力的工具之一。目前，仿真已经成为管理科学与运筹学领域应用最广泛的技术手段之一。近年来，随着许多仿真软件的开发和应用，各种仿真建模方法应用到了解决动态VRP问题中，通过仿真建模和仿真分析可以将现实配送系统中的各种不确定因素考虑进来。所以将仿真与优化方法结合起来是解决复杂的车辆调度问题的一个非常有效的方法。

Alkhamis［20］讨论了车辆路径问题中约束条件带有随机性函数的情况，文中使用粒子群优化求解，用几次仿真的均值来估计约束中的函数值，即用仿真方法对随机性的约束进行了有效处理。Taniguchi等［21］提出了一个有时间窗的车辆路径问题和动态交通仿真的集成模型。李永先［22］提出了用仿真的方法求解随机约束条件下车辆路径问题的新思路，建立了在需求量及行驶速度随机变动情况下的有时间窗的车辆路径的数学模型，并基于物流系统仿真平台eM－Plant设计了随机约束条件下VRP的仿真模型，而且实现了对该问题的求解。孙中悦［23］在其博士论文中讨论了动态车辆路径问题的求解方法。针对车辆在实际配送过程中经常出现不确定信息情况，提出了基于定时触发的动态仿真方法，该仿真的推进依靠真实时长的定时器触发，而不是依赖虚拟时钟，在新信息发生后，使得仿真过程和实际配送过程同步，并根据智能决策的优化方法进行调整得到新问题的仿真优化结果，确保在出现新的信息后车辆能够得到优化的配送路线。

仿真在物流系统领域的研究较少，现有的研究还存在一些不足，在解决动态车辆问题方面还存在算法效率不高、智能化程度不高等不足，还没有解决现实中的大规模的路径安排问题的能力。

3 动态车辆路径问题未来的研究方向

国内外学者在动态车辆路径问题理论和实践中都取得了一些研究成果，但是在动态车辆路径问题建模、信息处理和应用领域方面尚存在一些问题有待改进和提高，例如建模方法尚不完善，一些复杂的问题尚无法建立准确的模型来求解；不确定信息的处理还不成熟；动态车辆路径问题在新的物流模型（绿色物流，冷链物流等）中还没有得到很好的应用。动态车辆路径问题应在以下几个方面进行进一步的研究。

3.1 多约束多目标模型

目前，人们对模糊车辆路径问题研究的很少，而且对其研究主要集中在模糊需求的研究上，虽然对随机车辆路径问题研究的相对比较多，但是其研究方向也是主要集中于对随机需求的研究上，进一步的研究方向应从随机和模糊的预约时间、费用、顾客、车辆数、交通堵塞等方面进行。

人们研究动态车辆问题时，一般是单独研究随机车辆路径问题和模糊车辆路径问题，但是实际的物流系统中，往往是既存在随机信息又存在模糊信息，将这两种信息结合起来放到一个模型中解决物流配送问题将是未来的一个研究方向。

动态车辆路径问题与静态车辆路径问题一个重要的区别在于系统信息，动态车辆路径问题中的信息具有不确定性，所以信息多种多样但信息之间又有关联，如何将各种信息联系起来系统的分析车辆路径问题也是一个值得研究的方向。

因此，随着对动态车辆路径问题研究的深入，为了使物流配送和车辆调度问题更加符合实际情况，多约束多目标的动态车辆路径问题模型将是未来研究的趋势。

3.2 分布估计算法的应用

分布估计算法是最近几年新兴起的一种启发式算法，分布估计算法的概念是在1999年提出的，在遗传算法的基础上提出了一种全新的进化模型，并迅速成为计算进化领域的研究热点和解决工程问题的有效方法。分布估计算法是遗传算法和统计学习相结合的思想，其基本方法是通过统计学习的手段建立解空间内个体分布的概率模型，然后对概率模型随机采样产生新的群体，如此反复，实现群体的进化。由于分布估计算法是基于概率模型的进化，更能适应动态VRP的优化。目前，利用分布估计算法研究动态VRP还很少，这将是未来的一个研究方向。

3.3 研究领域的扩展

绿色物流是一种新的物流模型，绿色物流是指在物流过程中抑制物流对环境造成危害的同时，实现对物流环境的净化，使物流资源得到充分利用。绿色物流包括集约资源、绿色运输、绿色仓储、绿色包装和逆向物流。其中绿色运输要求对货运点、配送中心的设置做合理布局与规划，并通过缩短车辆路径和降低空载率，实现节能减排的目标。绿色物流中的绿色运输是一种动态车辆路径问题，由于绿色物流顺应了世界发展的潮流，因此如何将绿色物流中的一些参数融合到动态车辆路径问题模型中来解决绿色物流问题是一个值得研究的问题。

冷链物流是指冷藏冷冻类食品从原料、生产、加工、储藏、运输、销售直到消费前的各个环节始终处于规定的低温环境，以保证食品质量、减少食品损耗的一项系统工程。由于冷藏冷冻类食品易变质易腐烂，因此冷藏冷冻类食品在运输过程中较其他物流对时间的要求更苛刻。在冷链物流中不仅包括了一般的车辆安排中存在的不确定信息，还有冷藏冷冻类食品随时间变质的情况，如何将冷链物流的这一特性与动态车辆路径安排结合，减少食品损耗和运输时间将是未来研究的一个热点。

4 结语

动态车辆路径问题的研究对解决现实中的即使配送、第三方物流、交通拥挤、智能运输、绿色物流等问题有非常重大的意义。动态车辆路径问题取得了一定的研究成果，但是其研究的深度还不够，一般只考虑含一种或者两种约束条件的模型，多约束多目标的动态车辆路径问题的模型研究还很少。对动态信息处理的研究不成熟，解决实际问题的能力还比较差。目前的启发式算法对引入了动态信息的复杂的动态车辆路径问题有一定的局限，利用分布估计算法解决动态VRP是一个值得研究的方向。动态车辆问题还应该在其多约束多目标建模、研究领域的扩展、启发式算法的改进等方面做进一步的研究。

［1］Bertsimas D J，Ryzin G V.A stochastic and dynamic vehicle routing problems in the euclidean plane［J］.Operations Research，1991（39）：601～615.

［2］Minkoff A S.A markov decision mode land decomposition heuristic for dynamics algorithms，addressing uncertainty［J］.Operations Research，1993（41）：77～90.

［3］Tillman F.The multiple terminal delivery problem with probabilistic demands［J］.Transportation Science，1969，3（3）：192～204.

［4］Stewart W，Golden B.Stochastic vehicle routing：a comprehensive approach［J］.European Journal of Operational Research，1983，14（4）：371～385.

［5］谢如鹤，刘 霆，邱祝强.基于剩余装载能力的逆向物流车辆路径问题［J］.系统工程，2004（10）：20～23.

［6］葛显龙，王 旭，邓 蕾.基于联合配送的开放式动态车辆路径问题及算法研究［J］.管理工程学报，2013（3）：60～68.

［7］Teodorovic D，Radivojevic G.The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain［J］.Fuzzy Sets and Systems，1996（82）：307～317.

［8］Pavone M，Bisnik N，Frazzoli E，et al.A stochastic and dynamic vehicle routing problem with time windows and customer impatience［J］.Mobile Networks＆Applications，2009，14（3）：350～364.

［9］祝崇隽，刘 民，吴 澄，等.针对模糊需求的两种2－opt算法［J］.电子学报，2001（8）：1035～1037.

［10］路 琳.不确定信息车辆路径问题及其算法研究［D］.南京：南京航空航天大学，2007.

［11］Min H.The multiple vehicle routing problem with simultaneous delivery and pick－up points［J］.Transportation Research A，1989（23）：377～386.

［12］Chen R，Gen M.Vehicle routing problem with fuzzy due－time using genetic algorithms［J］.Japanese Journal of Fuzzy Theory and Systems，1995，7（5）：1050～1061.

［13］Pureza V，Laporte G.Waiting and buffering strategies for the dynamic pickup and delivery problem with time windows［J］.Information Systems and Operational Research，2008，46（3）：165～175.

［14］Liao T Y，Hu T Y.An object－oriented evaluation framework for dynamic vehicle routing problems under real－time information［J］.Expert Systems with Applications，2011，38（10）：12548～12558.

［15］甘勤涛，阳平华，童钟灵.模糊需求车辆路径问题的禁忌搜索算法研究［J］.长春理工大学学报，2006（1）：84～86.

［16］朗茂祥，胡思继.车辆路径问题的禁忌搜索算法研究［J］.北方交通大学学报，2004（2）：81～84.

［17］谢秉磊.随机车辆路径问题的多回路优化策略［J］.系统工程理论与实践，2007（2）：167～171.

［18］刘 霞.基于最大最小蚂蚁系统的动态车辆路径问题研究［J］.计算机工程与科学，2013，35（1）：130～136.

［19］王连锋，宋建社，曹继平，等.带硬时间窗模糊车辆路径问题的多目标优化［J］.计算机工程，2013，39（4）：9～17.

［20］Talal M.Alkhamis，Mohamed A.Ahmed.Simulatin－based optimization for repairable systems using particles swarm algorithm［C］//Proceedings of the 37th conference on Winter simulation.Orlando，Florida.2005：857～861.

［21］Taniguchi E，Yamada T，Hosokawa T.Dynamic traffic simula－tion with optimal truck routing and scheduling［A］.Transporation and Traffic，Abbreviated Presentation Sessions of the 14th International symposium on Transportation and Traffic Theory［C］.Jerusalem，1999：419～439.

［22］李永先.车辆路径问题的仿真模型及优化方法研究［D］.大连：大连理工大学，2007.

［23］孙中悦.车辆路径问题的仿真优化方法研究［D］.北京：北京交通大学，2012.