ALNS算法求解带软时间窗同时取送货的PCVRP问题

李 琳，陈 莹

(沈阳航空航天大学 理学院，沈阳 110136)

车辆路径问题(Vehicle Routing Problem,VRP)在物流行业有着很大的应用价值。庞燕等[1]总结了VRP的变体及其求解方法。在文献中，大多数VRP的变体问题假设配送中心具有足够数目的车辆可以满足所有客户的需求。在这类问题中，规划配送路线时，所有的客户都要被服务。但在实际生活中，存在不同客户可能存在不同的优先级和利润、每个客户不需要在特定的某天被强制访问、现有的车辆不能一次性满足所有客户的需求等情况。因此本文研究奖金收集车辆路径问题(Prize Collecting Vehicle Routing Problem,PCVRP)。PCVRP中由于实际配送条件的限制导致现有的车辆不能一次性满足所有客户的需求，只能服务部分客户。被服务的客户会给予车辆一定的奖金，被访问客户的总需求至少达到一个预定值。它的目标是使总运输成本最小化，同时使所有车辆收集到的奖金最大化。

目前对PCVRP的研究较少，对PCVRP需要进行更加深入的研究。文献[2-6]是基于带容量约束的VRP(CVRP)模型建立的PCVRP模型。其中文献[2-4]的目标函数是最小化总行驶距离和使用的车辆数目、最大化奖金收集。Long等[2]提出了一种基于Pareto的进化算法求解PCVRP。Li等[3]对建立的PCVRP模型，提出了两级自适应变邻域搜索算法，将PCVRP转化为等价的旅行商问题(TSP)，并对提出的算法进行了评价。Tang等[4]针对PCVRP问题，提出了基于循环转移的超大规模邻域迭代局部搜索算法。对100个客户的问题进行计算并验证了算法的可行性。文献[5-6]在上述基础上增加了未被服务客户对车辆的惩罚。……