张景玲，刘金龙，赵燕伟，王宏伟，冷龙龙, 冯勤炳

(浙江工业大学 特种装备制造与先进加工技术教育部重点实验室，浙江 杭州 310014)

0 引言

在当今激烈的市场竞争中，越来越多的企业趋向为客户提供全生命周期的产品及服务，如家电、食品、汽车行业，这就要求企业在保证配送时效的同时，对客户点进行配送与回收服务。传统车辆路径问题(Vehicle Routing Problem, VRP)的研究不能描述城市物流配送过程中同时取送货的特点，越来越多的学者转向对其分支问题——同时取送货的车辆路径问题(Vehicle Routing Problem with Simultaneous Delivery and Pickup, VRPSDP)进行研究。

Min[1]于1989年首次提出VRPSDP用于解决公共图书馆问题;Poonthalir等[2]从路径最短的角度对混合回程的车辆路径问题进行建模，并考虑车辆巡航以及空载时燃油消耗及碳排放;Ninikas等[3]研究了一种动态VRPSDP，在执行预制定的配送方案过程中实时接收动态的取货请求;Lin等[4]提出一个集成了混合邻域搜索算法的决策支持系统(Decision Support System, DSS)原型来解决离线和在线需求的动态车辆路径问题;Hu等[5]研究了货物不兼容情况下，具有不确定性送货和确定性取货的动态闭环VRP;Wang等[6]等以降低人力成本、运输成本以及提高客户满意度为目标，采用邻域搜索算法对带软时间窗的VRPSDP进行多目标优化;王超等[7]提出一种离散布谷鸟算法(Discrete Cuckoo Search, DCS)算法，以最小化分配成本与行驶成本之和为目标对硬时间窗的VRPSDP进行建模并求解。上述研究很少涉及时间依赖型的VRPSDP，现有时间依赖型车辆路径问题的研究多集中在无取货的VRP。Malandraki等[8]对时间依赖型车辆路……