开放式带时间窗车辆路径问题及变邻域搜索算法

doi:10.13196/j.cims.2021.10.025

计算机集成制造系统 ›› 2021, Vol. 27 ›› Issue (10): 3014-3025.DOI: 10.13196/j.cims.2021.10.025

开放式带时间窗车辆路径问题及变邻域搜索算法

陈久梅^1,2,李英娟¹,胡婷³,但斌⁴⁺,李俊³

1.重庆工商大学长江上游经济研究中心
2.重庆工商大学管理科学与工程学院
3.重庆工商大学工商管理学院
4.重庆大学经济与工商管理学院

出版日期:2021-10-31 发布日期:2021-10-31
基金资助:
国家社会科学基金重大资助项目(15ZDB169);重庆市自然科学基金面上资助项目(cstc2019jcyj-msxmX0569)。

Solving open vehicle routing problem with time windows based on variable neighborhood search algorithm

Online:2021-10-31 Published:2021-10-31
Supported by:
Project supported by the Major Program of the National Social Science Foundation,China(No.15ZDB169),and the Chongqing Municipal Natural Science Foundation,China(No.cstc2019jcyj-msxmX0569).

摘要/Abstract

摘要： 针对配送服务中开放式带时间窗车辆路径问题,构建了最小化车辆行驶成本的集分割模型,并提出变邻域搜索算法进行求解。该算法包括抖动和邻域搜索两个阶段,其中,抖动阶段通过当前解与种群历史最优、与个体历史最优之间的路径重连来实现,邻域搜索阶段通过同一条路径内以及不同路径间的交换、插入、2-opt三个操作算子来实现。通过与已有文献进行对比,结果表明该算法在求解开放式带时间窗车辆路径问题时,能得到更高质量的解,而且算法的收敛性和稳定性均较好。由此验证了该算法的可行性和有效性。

关键词: 开放式车辆路径问题, 带时间窗车辆路径问题, 变邻域搜索算法, 配送

Abstract: Aiming at the Open Vehicle Routing Problem with Time Windows (OVRPTW) in delivery service,a set partition model was built to minimize the costs of travelling,and the Variable Neighborhood Search (VNS) algorithm was proposed to solve this problem.This algorithm included two stages:shaking and neighborhood search.The shaking was realized by path relinking between the current solution,the population historical optimal solution and the individual historical optimal solution.The neighborhood search was implemented by three operators that were exchange,insertion and 2-opt within the same path and between different paths.The comparison with the existing literature showed that the proposed algorithm could obtain not only higher quality solutions,but also better convergence and stability,which verified the feasibility and effectiveness of the proposed algorithm.

Key words: open vehicle routing problem, vehicle routing problem with time windows, variable neighborhood search, delivery

中图分类号:

U49
TP311

陈久梅,李英娟,胡婷,但斌,李俊. 开放式带时间窗车辆路径问题及变邻域搜索算法[J]. 计算机集成制造系统, 2021, 27(10): 3014-3025.

[1]	周博文,黄海军,徐怡,李学俊,高寒,陈天翔,刘晓,徐佳. 无人机配送系统中端边协同的并行任务调度算法[J]. 计算机集成制造系统, 2021, 27(9): 2575-2582.
[2]	饶卫振,徐丰,段忠菲. 联合采购与配送协同成本分摊方法[J]. 计算机集成制造系统, 2021, 27(7): 2144-2155.
[3]	王勇,周雪,刘永,许茂增. 基于车辆共享的多中心共同配送联盟优化[J]. 计算机集成制造系统, 2021, 27(6): 1820-1832.
[4]	谭志龙,王征,薛桂琴,王新. 基于社会化库存的多回程物流配送问题的拉格朗日松弛算法[J]. 计算机集成制造系统, 2021, 27(3): 965-972.
[5]	邓建新,卫世丰,石先莲,陈星雨,韦婉冬. 基于数字孪生的配送管理系统研究[J]. 计算机集成制造系统, 2021, 27(2): 585-604.
[6]	王万良,朱文成,赵燕伟. 基于全局边缘排序的超启发算法在绿色物流选址—路径优化问题中的应用[J]. 计算机集成制造系统, 2020, 26(第4): 1097-1107.
[7]	郭洪飞,陈德强,屈挺,李从东,黄国全,何智慧,陈敏诗,曾云辉. 基于价值流的S生产线精益优化[J]. 计算机集成制造系统, 2020, 26(第2): 320-330.
[8]	许茂增,周翔,崔利刚,刘永,余国印. 低配送密度区域快递共同配送模式及利益分配[J]. 计算机集成制造系统, 2020, 26(第1): 181-190.
[9]	蒋海青,赵燕伟,徐兆军,柳青,张景玲. 动态需求低碳开放式选址—路径问题[J]. 计算机集成制造系统, 2020, 26(第1): 202-212.
[10]	邱晗光,高敏,甄杰,周继祥. 可选交付方式及时间窗下城市配送服务选项多目标联合定价[J]. 计算机集成制造系统, 2020, 26(7): 1965-1975.
[11]	朱惠琦,邱莹,姜天华,胡明瑶. 消费者“最后一公里”配送模式、服务方式与配送时隙的联合选择[J]. 计算机集成制造系统, 2020, 26(7): 1998-2006.
[12]	张连超,刘蔚然,程江峰,陶飞,孟少华,陈畅宇. 卫星总装数字孪生车间物料准时配送方法[J]. 计算机集成制造系统, 2020, 26(11): 2897-2914.
[13]	周林,康燕,宋寒,代应. 送提一体与终端共享下的最后一公里配送选址—路径问题[J]. 计算机集成制造系统, 2019, 25(第7): 1855-1864.
[14]	刘乐,朱洪利. 双机流水车间外包与调度联合优化问题的混合变邻域搜索算法[J]. 计算机集成制造系统, 2019, 25(第5): 1202-1222.
[15]	陈久梅,张松毅,但斌. 求解多隔室车辆路径问题的改进粒子群优化算法[J]. 计算机集成制造系统, 2019, 25(第11): 2952-2962.

开放式带时间窗车辆路径问题及变邻域搜索算法

Solving open vehicle routing problem with time windows based on variable neighborhood search algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics