张 凯，靳 鹏，崔 勇

合肥工业大学 管理学院，合肥230009

传统物流企业利用自有车辆为客户提供揽收/配送服务。由于自有车辆具有使用成本高、管理难度大等缺点，在共享经济大背景下，物流企业开始采用一种基于外部车辆的新型揽收配送模式，利用外部车辆为客户提供揽收/配送服务，外部车辆主要是社会闲置车辆。新型揽收配送模式可以减少企业自有车辆的使用，降低物流成本，并对提高社会闲置车辆利用率和环境保护方面具有重要意义。

本文研究了基于新型揽收配送模式下的一种带时间窗的多车型需求可拆分揽收配送问题（Multi-Vehicle Split Pickup and Delivery Problem with Time Windows，MVSPDPTW），使用社会闲置车辆作为揽收/配送任务的资源，社会闲置车辆拥有自己的起点、终点以及最早出发时间和最晚返回时间，车辆必须在最早出发时间后从起点出发为客户提供揽收/配送服务，并在最晚返回时间前返回终点。在服务客户的过程中，车辆需要在客户时间窗内提供服务，并且允许需求拆分，同一客户需求可由多辆车完成，以便充分利用车辆的装载能力。

车辆路径问题（Vehicle Routing Problems，VRP）[1]自1959 年被提出以来，一直是物流研究领域的热点问题。目前，在VRP 的研究中一般限制客户的需求只能由一辆车来完成，属于需求不可拆分的VRP。文献[2]在1989年首次研究了需求可拆分的VRP（Split Delivery Vehicle Routing Problems，SDVRP），指出对客户需求进行合理的拆分有利于提高车辆装载率和节约总成本，并在1994 年证明SDVRP 是NP-hard[3]问题。目前已有不少学者从不同角度对SDVRP展开了研究。由于……