随着中国电子商务的持续发展,电商包裹数量快速增长,物流企业在最后一公里配送场景的竞争愈加激烈。通过合理的路径规划来高效地完成配送任务,对于提高配送效率和用户体验,至关重要。近年来,城市道路交通规则开始限制大型车辆进入城市中心道路,因此物流最后一公里配送需采用小型货车,多次往返于中心仓库与客户点之间完成交付。该场景下,顾客往往也有时间窗(Time Windows,TW)的需求。若考虑带时间窗车辆路径规划问题(Vehicle Routing Problem with Time Windows,VRPTW),该问题每辆车只能执行一次行程,由于小型货车容量小,单行程的车辆利用率低,只能牺牲成本,通过增加车辆使用数来满足客户需求。因此,在最后一公里配送场景下,带时间窗多行程车辆路径优化问题(Multi-trip Vehicle Routing Problem with Time Windows,MTVRPTW)具有更高的实用价值。鉴于MTVRPTW已被证明为NP-Hard问题,且现有的MTVRPTW精确解算法求解规模较小,在短时间内不能得到高质量的求解结果,无法满足城市物流最后一公里大规模的配送场景需求。因此,设计混合启发式求解算法高效求解MTVRPTW的研究,具有重要意义。本文在对多行程车辆问题的特征、类型和主要优化问题进行分析和综述的基础上,采用运筹学、智能优化算法等方法,针对MTVRPTW问题的主要研究工作包括以下内容:(1)研究了车辆数不固定的MTVRPTW问题,构建了以总成本优化为目标的混合整数规划模型,分别设计了Solomon初始解构成策略的SILTS算法和贪婪初始解构成策略的GRILS-VND算法。基于Solomon算例,求解分析了在客户分布与时间窗密度两个纬度下,两种求解策略的优化效果;(2)研究了车辆数固定的MTVRPTW问题,构建了以里程最小化为目标的混合整数规划模型,针对问题特征,结合变邻域算法与禁忌搜索,设计了一种两阶段的混合启发式算法HVNTS,并通过与已有的求解结果对比分析,验证了算法有效性;(3)以J公司最后一公里配送场景为例,生成基于曼哈顿距离的实际路网数据,运用J公司实际路网数据,验证了Solomon初始解构成策略的SILTS算法和贪婪初始解构成策略的GRILS-VND算法在实际场景下优化总成本的效果优劣,并对车辆数固定场景下的实际MTVRPTW里程优化方法进行讨论。为物流运输企业实施物流路径规划提供了决策依据,在理论上丰富了MTVRPTW的相关优化研究。
暂无评论