带订单选择车辆路径问题的模型与算法

孙刘诚，孙 焰

(同济大学道路与交通工程教育部重点实验室，上海201804)

0 引言

物流是社会活动的经济基础，然而由于物流资源分散、信息封闭、重复配送等，导致物流成本一直居高不下.共同配送作为一种低成本、高效率的协作型配送模式，受到了学者和从业者等各界人士的广泛关注.共同配送包括多种形式，其中很重要的一种形式是通过企业间的信息共享，从而实现运输订单在合作企业间的相互交换和协调，企业车辆互相代为完成订单，提高车辆装载率，减少车辆的交叉重复行驶，不仅可以降低物流成本、提高企业经济效益，还具有营造良好的交通环境、降低碳排放等社会效益.

这种协作型配送模式衍生出了一类新的车辆路径问题，称为带订单选择的车辆路径问题(Vehicle Routing Problem with Request Selection,VRPRS).在此类问题中，运输企业不仅面对由托运人托付的运输订单，同时也可以通过信息平台接收到由合作企业发布的运输订单.运输企业既可以将自身订单委托给合作企业，同时支付一定的委托费；也可以接受其他企业发布的订单，并获得相应的报酬.运输企业需要同时进行订单选择及车辆路径优化使得自己利益最大化.

由于共同配送是近年才发展并兴起的协同物流运作模式中的重要内容，故目前在此背景下的车辆路径问题研究较少.Chu[1]首先提出了在运力不足的情况下可将运输订单外包给其他合作企业的车辆路径问题，并设计了一种启发式算法求解；……