闫 军，常 乐，王璐璐，赵 彤

(1.兰州交通大学 甘肃省物流与信息技术研究院，甘肃 兰州 730070；2.兰州交通大学 机电技术研究所，甘肃 兰州730070；3.呼和浩特铁路局集团公司包头货运中心，内蒙古 包头 014000)

车辆路径问题 (vehicle routing problem，VRP) 是物流生产活动中的核心环节，也是组合优化和运筹学领域的研究热点[1]。在实际的物流服务中，时间窗和取送货服务是需要满足的现实要求，所以带时间窗的同时取送货的车辆路径问题 (pickup and delivery problem with time windows, PDPTW)得到越来越多的关注[2]。

起初解决多车辆的PDPTW问题主要是依靠精确算法，从1991年Dumas等[3]的列生成算法到Furtado等[4]设计基于特殊有效不等式的分支切线方法。精确算法虽然无法求解大规模客户的实际案例，但丰富了PDPTW的数学模型，为目前的启发式算法求解问题提供基础。本文也以此为基础建立优化模型。Nanry等[5]最早使用响应式禁忌启发搜索算法对PDPTW进行求解，并进行25、50和100个客户规模的数据实验。Li等[6]在禁忌搜素算法的基础上混合模拟退火算法进行研究，而且将其研究的数据集进行公布作为PDPTW的研究基础。吴璟莉[7]使用遗传算法对拥有10个客户规模的多车、多货物仓库进行PDPTW问题的求解。为减少运行的车辆数目，Nagata等[8]运用引导式弹射搜索算法来对问题进行求解，实验证明可以有效减少车辆数。Zou等[9]使用混合粒子群算法对PDPTW进行求解，目的是为优化多目标的PDPTW问题。蚁群算法被用来进行PDPTW问题的求解，首次出现于2017年。Tchoupo等[10]强化蚁群算法局部优化能力后，与以往实验结果进行对比，发现其方法在98.2%的数据实验上取得相同或更好的结果，证明了蚁群算法在此类问题上的有效性。……