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

doi:10.11772/j.issn.1001-9081.2017071872

计算机应用 ›› 2018, Vol. 38 ›› Issue (2): 573-581.DOI: 10.11772/j.issn.1001-9081.2017071872

• 应用前沿、交叉与综合 • 上一篇下一篇

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

石建力¹, 张锦²

1. 西南交通大学交通运输与物流学院, 成都 610031;
2. 西南交通大学综合交通运输智能化国家地方联合工程实验室, 成都 610031

收稿日期:2017-07-31 修回日期:2017-09-28 出版日期:2018-02-10 发布日期:2018-02-10
通讯作者: 石建力
作者简介:石建力(1985-),男,河南周口人,博士研究生,主要研究方向:物流系统优化、城市配送、分批配送车辆路径问题;张锦(1963-),男,四川广元人,教授,博士生导师,博士,主要研究方向:物流系统优化与规划、交通系统优化与规划、物流大数据、交通大数据。
基金资助:
国家自然科学基金资助项目（41501123）；中央高校基本科研业务费专项资金资助项目（2682016CX058）。

Model and algorithm for split delivery vehicle routing problem with stochastic travel time

SHI Jianli¹, ZHANG Jin²

1. School of Transprotation and Logistics, Southwest Jiaotong University, Chengdu Sichuan 610031, China;
2. National United Engineering Laboratory of Integrated and Intelligent Transportation, Southwest Jiaotong University, Chengdu Sichuan 610031, China

Received:2017-07-31 Revised:2017-09-28 Online:2018-02-10 Published:2018-02-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (41501123), the Fundamental Research Funds for the Central Universities (2682016CX058).

摘要/Abstract

摘要： 为研究分批配送和等待时间对行驶时间随机的车辆路径问题（VRP）的影响，针对行驶时间随机的分批配送车辆路径问题，在软时间窗下考虑等待时间，建立带修正的随机规划模型；同时设计改进的粒子群优化（PSO）算法进行求解：使用需求点可多次出现的整数编码，设计改进的相对位置索引算法进行解码以解决粒子中出现分批需求点问题；将自适应选择用于速度更新以解决各向量长度不同的问题；将路径重连算法用于位置更新过程以解决粒子在离散空间和连续空间转换时信息丢失的问题，适应允许分批配送的特点。通过对调整的Solomon算例测试，考虑等待时间将造成总费用平均增加约3%，且更倾向于分批配送。分批配送能有效降低总费用（2%）和减少使用的车辆数（0.6）；在部分算例，特别是R2类算例中，分批配送能有效降低等待时间，平均降低0.78%。

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

Abstract: To evaluate the effect of split delivery and waiting time on Vehicle Routing Problem (VRP) with stochastic travel time, by considering the waiting time under soft time window, a stochastic programming model with correction was formulated to solve the Split Delivery VRP (SDVRP) with stochastic travel time. Meanwhile, an improved Particle Swarm Optimization (PSO) was proposed for this problem. At first, an improved relative position index method was used to decode the integer type code in which some customers (the split customers) may appear more than once. Then, an adaptive selection process was used to update the velocity in which the length of the involved vectors are different from each other besause of the split delivery. At last, the path relinking method was used to update the position of the swarm to deal with the information loss caused by the transformation between the continuous space and the discrete space. The experimental results on modified Solomon's instances show that the all-in cost is averagely increased by about 3%, and customers tend to choose split delivery when considering the waiting time. The use of split delivery can effectively reduce the all-in cost (2%) and the use of vehicles (0.6); in addition, in some instances, especially in the R2 instances, the waiting time can be reduced by about 0.78%.

Key words: Particle Swarm Optimization (PSO), split delivery, stochastic travel time, Vehicle Routing Problem (VRP), time window

中图分类号:

TP301.6

石建力, 张锦. 行驶时间随机的分批配送车辆路径问题模型与算法[J]. 计算机应用, 2018, 38(2): 573-581.

SHI Jianli, ZHANG Jin. Model and algorithm for split delivery vehicle routing problem with stochastic travel time[J]. Journal of Computer Applications, 2018, 38(2): 573-581.

参考文献

[1] EHMKE J F, CAMPBELL A M, URBAN T L. Ensuring service levels in routing problems with time windows and stochastic travel times[J]. European Journal of Operational Research, 2015, 240(2):539-550.
[2] LI X, TIAN P, LEUNG S C H. Vehicle routing problems with time windows and stochastic travel and service times:models and algorithm[J]. International Journal of Production Economics, 2010, 125(1):137-145.
[3] DROR M, TRUDEAU P. Savings by split delivery routing[J]. Transportation Science, 1989, 23(2):141-145.
[4] ARCHETTI C, SPERANZA M G. Vehicle routing problems with split deliveries[J]. International Transactions in Operational Research, 2012, 19(1/2):3-22.
[5] FRIZZELL P W, GIFFIN J W. The split delivery vehicle scheduling problem with time windows and grid network distances[J]. Computers & Operations Research, 1995, 22(6):655-667.
[6] HO S C, HAUGLAND D. A Tabu search heuristic for the vehicle routing problem with time windows and split deliveries[J]. Computers & Operations Research, 2004, 31(12):1947-1964.
[7] BELFIORE P, YOSHIDA YOSHIZAKI H T. Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil[J]. European Journal of Operational Research, 2009, 199(3):750-758.
[8] MCNABB M E. Exploring heuristics for the vehicle routing problem with split deliveries and time windows[D]. Ohio:Air University, Department of the Air Force, Wright-Patterson Air Force Base, 2014:29-63.
[9] SALANI M, VACCA I. Branch and price for the vehicle routing problem with discrete split deliveries and time windows[J]. European Journal of Operational Research, 2011, 213(3):470-477.
[10] DESAULNIERS G. Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows[J]. Operations Research, 2010,58(1):179-192.
[11] ARCHETTI C, BOUCHARD M, DESAULNIERS G. Enhanced branch and price and cut for vehicle routing with split deliveries and time windows[J]. Transportation Science, 2011, 45(3):285-298.
[12] BOUZAIENE-AYARI B, DROR M, LAPORTE G. Vehicle routing with stochastic demand and split deliveries[J]. Discrete Applied Mathematics, 1994, 50(3):239-254.
[13] LEI H, LAPORTE G, GUO B. The vehicle routing problem with stochastic demands and split deliveries[J]. INFOR:Information Systems & Operational Research, 2012, 50(2):59-71.
[14] ZHANG J, LAM W H K, CHEN B Y. A stochastic vehicle routing problem with travel time uncertainty:trade-off between cost and customer service[J]. Networks and Spatial Economics, 2013, 13(4):471-496.
[15] 杨信丰,杨庆丰.随机车辆路径问题的模型及其算法[J].交通运输系统工程与信息,2006,6(4):75-80. (YANG X F, YANG Q F. Model and algorithm of vehicle routing problem with stochastic travel time[J]. Journal of Transponation systems Engineering and Information Technology, 2006, 6(4):75-80.)
[16] 李锋,魏莹.求解随机旅行时间的C-VRP问题的混合遗传算法[J].系统管理学报,2014,23(6):819-825. (LI F, WEI Y. Hybrid genetic algorithm for capacitated vehicle routing problem with stochastic travel time[J]. Journal of Systems & Management, 2014, 23(6):819-825.)
[17] 王征,胡祥培,王旭坪.行驶时间延迟下配送车辆调度的干扰管理模型与算法[J].系统工程理论与实践,2013,33(2):378-387. (WANG Z, HU X P, WANG X P. Disruption management model and algorithm for distribution vehicle scheduling problems under accidental travel time delay[J]. Systems Engineering-Theory & Practice, 2013, 33(2):378-387.)
[18] 李妍峰,高自友,李军.基于实时交通信息的城市动态网络车辆路径优化问题[J].系统工程理论与实践,2013,33(7):1813-1819. (LI Y F, GAO Z Y, LI J. Vehicle routing problem in dynamic urban network with real-time traffic information[J]. Systems Engineering-Theory & Practice, 2013, 33(7):1813-1819.)
[19] ANDO N, TANIGUCHI E. Travel time reliability in vehicle routing and scheduling with time windows[J]. Networks and Spatial Economics, 2006, 6(3/4):293-311.
[20] RUSSELL R A, URBAN T L. Vehicle routing with soft time windows and erlang travel times[J]. The Journal of the Operational Research Society, 2008, 59(9):1220-1228.
[21] 李相勇,田澎.带时间窗和随机时间车辆路径问题:模型和算法[J].系统工程理论与实践,2009,29(8):81-90. (LI X Y, TIAN P. Vehicle routing problems with time windows and stochastic times:models & algorithm[J]. Systems Engineering-Theory & Practice, 2009, 29(8):81-90.)
[22] TAŞ, DELLAERT N, VAN WOENSEL T, et al. Vehicle routing problem with stochastic travel times including soft time windows and service costs[J]. Computers & Operations Research, 2013, 40(1):214-224.
[23] TAŞ, GENDREAU M, DELLAERT N, et al. Vehicle routing with soft time windows and stochastic travel times:a column generation and branch-and-price solution approach[J]. European Journal of Operational Research, 2014, 236(3):789-799.
[24] EHMKE J F, CAMPBELL A M, URBAN T L. Ensuring service levels in routing problems with time windows and stochastic travel times[J]. European Journal of Operational Research, 2015, 240(2):539-550.
[25] MARINAKIS Y, MARINAKI M, DOUNIAS G. A hybrid particle swarm optimization algorithm for the vehicle routing problem[J]. Engineering Applications of Artificial Intelligence, 2010, 23(4):463-472.
[26] KECHAGIOPOULOS P N, BELIGIANNIS G N. Solving the urban transit routing problem using a particle swarm optimization based algorithm[J]. Applied Soft Computing, 2014, 21:654-676.
[27] AI T J, KACHITVICHYANUKUL V. Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem[J]. Computers & Industrial Engineering, 2009, 56(1):380-387.
[28] CHEN M-C, HSIAO Y-H, HIMADEEP REDDY R, et al. The self-learning particle swarm optimization approach for routing pickup and delivery of multiple products with material handling in multiple cross-docks[J]. Transportation Research Part E:Logistics and Transportation Review, 2016, 91:208-226.
[29] NOROUZI N, SADEGH-AMALNICK M, ALINAGHIYAN M. Evaluating of the particle swarm optimization in a periodic vehicle routing problem[J]. Measurement, 2015, 62:162-169.
[30] BOUDIA M, PRINS C, REGHIOUI M. An effective memetic algorithm with population management for the split delivery vehicle routing problem[C]//HM'07:Proceedings of the 4th International Conference on Hybrid Metaheuristics, LNCS 4771. Berlin:Springer, 2007:16-30.
[31] MARINAKIS Y. An improved particle swarm optimization algorithm for the capacitated location routing problem and for the location routing problem with stochastic demands[J]. Applied Soft Computing, 2015, 37:680-701.
[32] MARINAKIS Y, MARINAKI M. Combinatorial expanding neighborhood topology particle swarm optimization for the vehicle routing problem with stochastic demands[C]//GECCO'13:Proceedings of the 2013 Conference on Genetic and Evolutionary Computation. New York:ACM, 2013:49-56.
[33] SOLOMON M M. Algorithms for the vehicle routing and scheduling problems with time window constraint[J]. Operations Research, 1987, 35(2):254-265.
[34] SILVA M M, SUBRAMANIAN A, OCHI L S. An iterated local search heuristic for the split delivery vehicle routing problem[J]. Computers & Operations Research, 2015, 53:234-249.
[35] TAŞ, DELLAERT N, VAN WOENSEL T, et al. Vehicle routing problem with stochastic travel times including soft time windows and service costs[J]. Computers & Operations Research, 2013, 40(1):214-224.

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

Model and algorithm for split delivery vehicle routing problem with stochastic travel time

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[2]	李进, 王凤, 杨沈宇. 换电模式下电动车货运路径优化模型与算法[J]. 计算机应用, 2021, 41(6): 1792-1798.
[3]	樊小毛, 熊红林, 赵淦森. 带约束的清洁排班问题模型及其求解[J]. 计算机应用, 2021, 41(2): 577-582.
[4]	王泽昆, 贺毅朝, 李焕哲, 张发展. 基于新颖S型转换函数的二进制粒子群优化算法求解具有单连续变量的背包问题[J]. 计算机应用, 2021, 41(2): 461-469.
[5]	李华峰, 黄樟灿, 张蔷, 湛航, 谈庆. 求解需求可拆分车辆路径问题的改进的金字塔演化策略[J]. 计算机应用, 2021, 41(1): 300-306.
[6]	罗斌, 于波. 移动边缘计算中基于粒子群优化的计算卸载策略[J]. 计算机应用, 2020, 40(8): 2293-2298.
[7]	周文峰, 梁晓磊, 唐可心, 李章洪, 符修文. 具有拓扑时变和搜索扰动的混合粒子群优化算法[J]. 计算机应用, 2020, 40(7): 1913-1918.
[8]	曾明华, 全轲. 双层规划的改进混合布谷鸟搜索量子行为粒子群优化算法[J]. 计算机应用, 2020, 40(7): 1908-1912.
[9]	施晓倩, 陈祺东, 孙俊, 冒钟杰. 变分布的量子行为粒子群优化算法求解工程约束优化问题[J]. 计算机应用, 2020, 40(5): 1382-1388.
[10]	霍晴晴, 郭健全. 基于改进遗传算法的生鲜多目标闭环物流网络模型[J]. 计算机应用, 2020, 40(5): 1494-1500.
[11]	张庆华, 吴光谱. 带时间窗的同时取送货车辆路径问题建模及模因求解算法[J]. 计算机应用, 2020, 40(4): 1097-1103.
[12]	张青, 郑岩. 基于蛙跳退火粒子群算法的民航发动机单元体修理级别决策及成本优化[J]. 计算机应用, 2020, 40(12): 3541-3549.
[13]	李贺, 江登英, 黄樟灿, 王占占. 彩色图像颜色量化问题的求解方法[J]. 计算机应用, 2019, 39(9): 2646-2651.
[14]	杨正清, 周朝荣, 袁姝. 移动群智感知系统中基于离散布谷鸟搜索算法的任务分配[J]. 计算机应用, 2019, 39(9): 2778-2783.
[15]	李卓, 李引珍, 李文霞. 应急物资运输路径多目标优化模型及求解算法[J]. 计算机应用, 2019, 39(9): 2765-2771.