行驶时间随机的分批配送车辆路径问题模型与算法研究

• •

行驶时间随机的分批配送车辆路径问题模型与算法研究

石建力¹,张锦²

1. 西南交通大学
2. 西南交通大学交通运输与物流学院，成都 610031

收稿日期:2017-07-31 修回日期:2017-09-28 发布日期:2017-09-28
通讯作者: 石建力

Model and Algorithm for the Split Delivery Vehicle Routing Problem with Stochastic travel times

ZHANG Jin²

Received:2017-07-31 Revised:2017-09-28 Online:2017-09-28

摘要/Abstract

摘要： 摘要: 本文研究行驶时间随机的分批配送车辆路径问题，在软时间窗下考虑等待时间，建立带修正的随机规划模型。设计改进的粒子群算法进行求解，对编码和解码过程、位移更新、位置更新和局部搜索等进行改进，将自适应选择和路径重连算法融入粒子群算法，以适应允许分批配送的特点。通过在调整的Solomon算例测试，考虑等待时间将造成总费用平均增加约3%，且更倾向于分批配送。分批配送能有效降低总费用和使用车辆数，分别平均降低2%和少0.6辆；在部分算例，特别是R2类算例中，分批配送能有效降低等待时间，平均降低0.78%。

关键词: 粒子群算法, 分批配送, 随机行驶时间, 车辆路径问题, 软时间窗

Abstract: Abstract: A stochastic programming with recourse was formulated to solve the split delivery vehicle routing problem with stochastic travel time, which considers the waiting time under soft time windows. An improved particle swarm optimization with adaptive selection rule and path relinking is developed for this problem, in which the coding and decoding process, the updating of the velicoty, the updating of the position and the local search process were designed for the split delivery factor. Computation tests on modified Solomon’s instances were carried out. The results showed that, the all-in cost increases about 3% averagely, and the splitted customers becomes more under the consideration of waiting time. The all-in cost decrease about 2% averagely and the number of vehicle decrease about 0.6 by allowing the split delivery. What’s more, the waiting time decreases 0.78% averagely because of the split delivery, especially in the instances in R2.

Key words: particle swarm optimization, split delivery, stochastic travel time, VRP, time windows

石建力张锦. 行驶时间随机的分批配送车辆路径问题模型与算法研究[J]. 计算机应用.

ZHANG Jin. Model and Algorithm for the Split Delivery Vehicle Routing Problem with Stochastic travel times[J]. .

[1]	李建强, 何舟. 面向多行程取送货车辆路径问题的混合NSGA-Ⅱ[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1187-1194.
[2]	林剑, 叶璟轩, 刘雯雯, 邵晓雯. 求解带容量约束车辆路径问题的多模态差分进化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2248-2254.
[3]	向峰, 李中志, 熊熙, 李斌勇. 粒子群局部优化的反距离权重插值算法[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 385-390.
[4]	肖智豪, 胡志华, 朱琳. 求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2926-2935.
[5]	刘志硕, 刘若思, 陈哲. 基于混合蚁群算法的冷链电动汽车车辆路径问题[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3244-3251.
[6]	徐郁, 朱韵攸, 刘筱, 邓雨婷, 廖勇. 基于深度强化学习的电力物资配送多目标路径优化[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3252-3258.
[7]	李进, 王凤, 杨沈宇. 换电模式下电动车货运路径优化模型与算法[J]. 计算机应用, 2021, 41(6): 1792-1798.
[8]	李华峰, 黄樟灿, 张蔷, 湛航, 谈庆. 求解需求可拆分车辆路径问题的改进的金字塔演化策略[J]. 计算机应用, 2021, 41(1): 300-306.
[9]	张庆华, 吴光谱. 带时间窗的同时取送货车辆路径问题建模及模因求解算法[J]. 计算机应用, 2020, 40(4): 1097-1103.
[10]	李卓, 李引珍, 李文霞. 应急物资运输路径多目标优化模型及求解算法[J]. 计算机应用, 2019, 39(9): 2765-2771.
[11]	杨正清, 周朝荣, 袁姝. 移动群智感知系统中基于离散布谷鸟搜索算法的任务分配[J]. 计算机应用, 2019, 39(9): 2778-2783.
[12]	张玉州, 徐廷政, 郑军帅, 饶舜. 考虑紧急度的救灾车辆路径问题建模与优化[J]. 计算机应用, 2019, 39(8): 2444-2449.
[13]	武旭晨, 朴春慧, 蒋学红. 基于GPU并行计算的电动出租车新建充电站选址模型[J]. 计算机应用, 2019, 39(10): 3071-3078.
[14]	王庆荣, 王瑞峰. 基于改进粒子群算法的配电网重构策略[J]. 计算机应用, 2018, 38(9): 2720-2724.
[15]	杜雪灵, 孟学雷, 杨贝, 汤霖. 考虑公平性的面向多灾点需求应急资源调度[J]. 计算机应用, 2018, 38(7): 2089-2094.