陈久梅,李英娟,胡 婷,但 斌,李 俊

(1.重庆工商大学 长江上游经济研究中心,重庆 400067；2.重庆工商大学 管理科学与工程学院，重庆 400067；3.重庆工商大学 工商管理学院，重庆 400067；4.重庆大学 经济与工商管理学院，重庆 400044)

0 引言

近年来，随着O2O平台的快速发展，物流配送需求大幅度增长，人们的消费模式从线下向线上转变。相比线下而言，线上平台面临更多挑战，如配送时效性与准确性、配送成本等。以美团外卖为例，在消费者下单、商家接单和骑手配送的几大环节中，骑手配送是关键，面临最大的挑战便是车辆调度问题。与传统车辆路径问题(Vehicle Routing Problem, VRP)不同，骑手配送环节往往由第三方平台负责，配送结束后车辆不必返回商家，这属于开放式车辆路径问题。此外，顾客往往对接受配送有最早和最晚时间的要求。该车辆路径具有受时间窗约束的特征，这类问题属于学术界研究的开放式带时间窗车辆路径问题(Open Vehicle Routing Problem with Time Windows, OVRPTW)。

OVRPTW在现实中应用广泛，如报纸配送、牛奶配送、快递服务、校园班车、大型生产制造业原材料的运输等。以校园班车为例，校车下午从学校出发，沿着预定路线，依次按照预定时间到达学生下车点，直到最后一位学生下车，早上接学生的情况正好相反。又如，当某些公司不拥有车队，或其车队不合适或不足以满足顾客需求时，这家公司需要将全部或部分货物交付第三方或借助外部载体进行运输，这种情况下车辆不必返回仓库，费用主要取决于行驶距离，即开放路线的长度。……