谭志龙，王 征，薛桂琴，王 新

(1.大连海事大学 交通运输工程学院，辽宁 大连 116026;2.大连海事大学 航运经济与管理学院，辽宁 大连 116026)

0 引言

随着零售业的不断发展，网购商品的可选范围得到了极大的拓展，除传统的需要多天配送的服装鞋帽、家电数码等商品外，线上线下相融合的本地商家进行生鲜果蔬、日用百货等生活快消品的配送也成为了网购的一股新力量。这种配送方式依托地理上分散分布的多个商店实现库存的社会化，通过运力的合理调度，在顾客规定的时间内完成从商家取货并向顾客配送的物流任务。这种社会化的库存对运力的优化调度提出了新要求，物流配送呈现出时间紧迫、取送一体化等特点。因此，如何在满足顾客需求的前提下，以较低的成本完成社会化库存的配送服务，是第三方物流公司必须解决的关键问题。理论上，这类问题可归结为一类特殊的多回程混合取送车辆路径问题，是车辆路径问题(Vehicle Routing Problem，VRP)的一类变形，仍具有NP-hard复杂性。

多回程VRP是指配送车辆可在供货点与顾客点之间往返多次，从而完成每个顾客的配送服务。该类问题的代表性研究成果包括Hernandez等[1]的分支定价法、Nguyen等[2]的禁忌搜索算法、Cattaruzza等[3]的遗传算法、Golden等[4]的适应性记忆算法、Chbichib等[5]的构建启发式、Battarra等[6]的适应性监督算法、Azi等[7]的大邻域搜索算法、以及国内学者唐加福等[8]的精确算法、王征等[9]基于路径池的算法等。然而，这些关于多回程VRP的研究通常只考虑一个供货点，而在本文问题中，货物仓储被分散在了大量商店中，每个商店都是供货点。……