王 超，刘 超，穆 东，高 扬

(1.北京工业大学 经济与管理学院，北京 100124；2.波士顿大学 物理系，波士顿 马萨诸塞州 美国 02215；3.北京现代制造业发展研究基地，北京 100124；4.北京交通大学 经济与管理学院，北京 100044)

0 引言

在当今激烈的市场竞争环境中，为了更有效地管理物流系统，企业均在优化战略和运营决策，最有效的运营决策之一是寻找最佳的车辆路径，该方法可以为降低物流成本和提高服务水平提供巨大的潜力。带时间窗和同时取送货的车辆路径问题(Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows, VRPSPDTW)，因整合企业正向物流和逆向物流过程而引起研究者的广泛关注。VRPSPDTW是经典VRP的一个重要扩展，同时取送货(Simultaneous Pickup and Delivery, SPD)意味着车辆不仅需要向顾客送货，还需要在顾客位置取货，例如快递员既要将快递、包裹送达顾客，又要从顾客处带回需要邮寄的快递或包裹等。时间窗(Time Windows, TW)规定了每个顾客最早允许开始服务时间ai和最晚允许开始服务时间bi。本文研究的是硬时间窗，不存在违约惩罚，即车辆早于ai时刻到达时，必须等待直到时间窗打开，而且车辆不允许晚于bi时刻到达。

在VRPSPDTW中，中心仓库(depot)有一些同质或异质的车辆，用于服务分散在不同位置的顾客。这些车辆首先将中心仓库的货物送达顾客，完成卸货后装载顾客处的货物，然后返回中心仓库，整个过程不能违背车辆装载容量限制，也不能违背顾客与中心仓库的时间窗限制。随着顾客规模的增加，VRPSPDTW求解的状态空间呈指数增长，现已被证实为一个NP-hard问题[1]。精确算法在理论上可以找到该问题的最优解，但由于在实践中求解时间太长且对计算机内存要求较高，仅适用于求解小型顾客规模的VRPSPDTW。……