孙 亮潘全科邹温强王亚敏

(1.上海大学机电工程与自动化学院,上海 200072;2.山东理工大学交通与车辆工程学院,山东淄博 255049;3.南京审计大学信息工程学院,江苏南京 211815)

1 引言

车辆路径问题(vehicle routing problem,VRP)是指在满足一定的约束条件(如需求量、车辆容量等)下,配送中心构造有限条车辆运行路径为客户提供配送服务,最终实现客户服务水平和运输成本等决策目标的最优化.配送完成时间是衡量客户服务水平的一个重要因素.但配送完成时间受交通拥堵等多种因素的影响,很难通过精确的概率分布进行描述,使得随机规划方法[1]处理不确定旅行时间条件下的车辆路径问题(vehicle routing problem with uncertain travel times,VRP–UT)的效果不够理想.与随机规划方法不同,鲁棒优化方法[2]利用不确定数据集的边界关系,可以将不确定的优化模型转化为确定的优化模型进行求解.目前常用的最坏场景鲁棒优化方法[3],要求所有车辆均需要在客户指定的时间内将货物送达客户,但从实际营运角度看,稍微偏离客户允许时间范围的配送服务并不对服务水平构成影响.轻鲁棒优化方法[4–7]通过对鲁棒优化模型中的某些约束进行松弛,以约束违背最小化为优化目标,从而改善最坏实现下目标函数值与预期值之间的偏差.所以采用轻鲁棒优化方法研究VRP–UT,更具有理论意义和实际价值.

从求解算法看,求解此类问题的算法主要有邻域搜索算法[8–10]、分支定界算法[11–13]和超启发式算法[14]等.现有算法主要关注总变动成本的……