动态车辆路径问题研究综述作者：韩娟娟李永先来源：《绿色科技》2015年第05期摘要：[HT5”K]指出了动态车辆路径问题是运筹学和组合优化领域的前沿研究方向，研究动态车辆路径问题具有重要的理论和现实意义。

阐述了动态车辆问题（DVRP），根据动态信息的特征将动态车辆路径问题分为随机车辆路径问题（SVRP）和模糊车辆路径问题（FVRP）。

从动态车辆路径问题的建模、算法和仿真优化三个方面分析了其研究成果，对现有研究的不足进行了探讨，提出了动态车辆路径问题的进一步研究方向。

关键词：[HT5”K]动态车辆路径问题；随机VRP；模糊VRP；算法中图分类号：[HT5”SS]F2.24文献标识码：[JY]文章编号：[HT5”SS]1674994.4（2015）05028504[HK]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等研究了多车辆有容量约束的DVRP和动态旅行修理员问题，并提出了解决该问题的排队论模型。

排队论模型成为研究动态车辆路径问题的一个重要的模型。

Minkoff提出了马尔可夫模型，但只能求解10个需求的小规模DVRP。

Tillmar在研究随机需求的车辆路径问题时，提出了一种惩罚模型，该模型规定当车的容量满足不了顾客服务要求时要按照一定的策略给予惩罚，这种模型有效地解决了路径失败的问题，对以后的研究有很好的借鉴作用。

Stewart和Golden提出了基于机会约束机制理论与二元可能性理论下的VRPSD的模型，这两个理论在以后的研究中应用的比较广泛。

谢如鹤等在对随机需求的VRP求解时，利用了一种基于车辆剩余能力的插入准则。

葛显龙研究了跨区域多配送中心动态需求的开放式VRP问题，提出了配送车辆共享和联合配送策略并建立符合实际的车辆路径优化模型，并利用云模型理论改进遗传算法对模型求解，得到了较好的结果。

Teodorovic和Pavkovic最早研究了模糊顾客需求的VRP，顾客的信息和决策者的偏好用模糊数来表示，并建立了以倾向度为基础的模糊判定准则。

Pavone在动态车辆路径问题中首先考虑了顾客等待的耐心因素。

祝祟隽以模糊可能性分布，建立了车辆路径问题的基于置信度的三下标流模型，并提出了基于可能性分布的2-opt算法。

陆琳等考虑到配送者的经验对现实中的车辆路径制定的显著作用，建立了包含配送者经验的知识系统的FVRP模型，使模型不单纯理论化而更具现实应用意义。

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

考虑到多车辆多车型的动态VRP的模型还比较少，还不成熟。

2.2动态VRP算法的研究进展VRP是NP-hard问题，由于其约束条件多，节点规模大，难以用精确算法求解，所以对这类问题的求解一般要用启发式算法获得其满意解。

常用的启发式算法有遗传算法、模拟退火算法、禁忌搜索算法、蚁群算法等，目前两种或者多种算法结合形成的混合算法经常被用来解决车辆路径问题。

启发式算法的发展为解决VRP提供了新的思路，可以解决问题规模比较大、结构比较复杂的车辆路径问题。

人们为了解决动态VRP，对启发式算法进行了改进。

1989年Min最早提出了VRPSDP，采用先对顾客聚类，然后解决每一类顾客群体的TSP。

在此基础上，对不可行路径进行补偿，从而优化各TSP路径。

Chen和Gen提出了一种利用推-碰-掷过程改进的混合遗传算法解决模糊车辆路径问题。

Gendreau等求解动态车辆路径问题时，构造了一种具有自适应性的禁忌搜索算法，首先利用禁忌搜索算法求解，当新的需求出现时，停止运行禁忌搜索算法，并将当前的最优解存储到自适应存储单元，然后利用插入法将新的需求插入到自适应存储单元的所有解中，再继续使用禁忌搜索算法对加入了新的需求点后的动态车辆路径问题进行优化。

Pureza研究动态车辆路径问题时，不是按照新需求出现的顺序依次对应进行服务，而是设置一定的新需求点缓存区，在达到一定数量的新需求后再根据紧急程度安排车辆服务，这种方法更符合了实际情况。

Liao等将动态车辆路径问题分为两阶段处理，首先采用扫描法确定使用的车辆数量，再根据接受到的实时信息采用禁忌搜索算法优化路径。

甘勤涛等利用禁忌搜索算法求解模糊需求VRP，郎茂祥等研究了车辆多次巡回配送和考虑车辆故障的DVRP，利用两阶段策略求解该问题，第一阶段用禁忌搜索算法安排车辆路径，第二阶段当新的信息出现时采用局部搜索算法进行局部优化。

谢秉磊等研究了一类随机顾客和随机需求的车辆路径问题，需求的随机性增加了决策的复杂性和难度，首先提出了多回路策略，并设计了具有不同邻域结构的模拟退火算法。

刘霞把计划周期分片，将动态车辆路径问题转换成一系列的静态车辆路径问题，并用最大最小蚁群算法对一系列的静态车辆路径问题进行求解，根据数据集的特点采用并行法或顺序法构建路线。

王连锋等针对具有多重模糊性的模糊车辆路径问题，依据模糊可信性理论建立了模糊期望值模型，并基于MOPSO提出了自适应混合多目标粒子群优化算法。

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

23动态VRP仿真优化的研究进展[JP3]仿真是建立数学逻辑模型并在计算机上运行该模型进行实验的过程，仿真建模是模仿真实系统的行为，仿真是决策者用于车辆路径安排的最有力的工具之一。

目前，仿真已经成为管理科学与运筹学领域应用最广泛的技术手段之一。

近年来，随着许多仿真软件的开发和应用，各种仿真建模方法应用到了解决动态VRP问题中，通过仿真建模和仿真分析可以将现实配送系统中的各种不确定因素考虑进来。

所以将仿真与优化方法结合起来是解决复杂的车辆调度问题的一个非常有效的方法。

[JP]Alkhamis讨论了车辆路径问题中约束条件带有随机性函数的情况，文中使用粒子群优化求解，用几次仿真的均值来估计约束中的函数值，即用仿真方法对随机性的约束进行了有效处理。

Taniguchi等提出了一个有时间窗的车辆路径问题和动态交通仿真的集成模型。

李永先提出了用仿真的方法求解随机约束条件下车辆路径问题的新思路，建立了在需求量及行驶速度随机变动情况下的有时间窗的车辆路径的数学模型，并基于物流系统仿真平台eM-Plant设计了随机约束条件下VRP的仿真模型，而且实现了对该问题的求解。

孙中悦在其博士论文中讨论了动态车辆路径问题的求解方法。

针对车辆在实际配送过程中经常出现不确定信息情况，提出了基于定时触发的动态仿真方法，该仿真的推进依靠真实时长的定时器触发，而不是依赖虚拟时钟，在新信息发生后，使得仿真过程和实际配送过程同步，并根据智能决策的优化方法进行调整得到新问题的仿真优化结果，确保在出现新的信息后车辆能够得到优化的配送路线。

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

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

动态车辆路径问题应在以下几个方面进行进一步的研究。

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

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

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