张 梦， 曲明成， 吴翔虎

(哈尔滨工业大学 计算机科学与技术学院， 哈尔滨 150001)

0 引 言

车辆路径问题是组合优化数学中的一类经典问题和热点课题，由Dantzig和Ramser在1959年提出，并采用了基于线性规划的求解过程[1]。学术界目前倾向于认为该类问题的大型实例不能使用精确算法求解，必须寻求这类问题的有效近似算法。因此，更倾向于使用启发式算法，如禁忌搜索算法[2]。

在此之后的几十年里，已经有大量的学者对该问题进行了深入的研究，又提出了动态车辆路径问题[3]，周鲜成等从动态要素的角度，将其划分为基于动态揽收、基于实时交通信息以及基于二者的3种类型[4]，众多学者也对此进行了相应的算法研究。针对动态揽收问题：Armas等通过先规划初始路径，再根据实时信息动态调整的二阶段策略来求解动态车辆路径问题[5]；张文博等将新增客户需求的动态过程拆分成多个静态过程，从而达到成本最小化[6]；Schyns以响应时间最小化为优化目标，将定时更新策略和实时更新策略作比较，分析其针对动态揽收的响应效率[7]。针对基于实时交通信息的问题：Wang等通过对交通信息的预测，定时接收交通流，完成车辆路径的重新规划[8]；张杨等针对于随时会产生的交通拥堵道路信息，采取了将拥堵道路的起点作为新起点，重新进行路径规划的策略[9]。针对基于二者的问题：Núez等采用了混合自适应的预测控制方法，完成路径的实时更新[10]；Wohlgemuth等采用了分级聚类方法对顾客聚类，以便实时更新路径[11]。……