带时间窗的多中心半开放式车辆路径问题

doi:10.3969/j.issn.1004-132X.2020.14.013

中国机械工程 ›› 2020, Vol. 31 ›› Issue (14): 1733-1740.DOI: 10.3969/j.issn.1004-132X.2020.14.013

带时间窗的多中心半开放式车辆路径问题

辜勇, 袁源乙, 张列, 段晶晶

武汉理工大学物流工程学院, 武汉, 430063

收稿日期:2019-09-20 出版日期:2020-07-25 发布日期:2020-08-26
通讯作者: 袁源乙(通信作者),女,1994年生,硕士研究生。研究方向为物流系统分析与优化。E-mail:460915419@qq.com。
作者简介:辜勇,男,1975年生,副教授、博士。研究方向为系统分析与优化、智能物流规划与仿真。E-mail:guyong@whut.edu.cn。
基金资助:
国家重点研发计划资助项目（2018YFC1407405）

Multi-depot Half Open Vehicle Routing Problem with Time Windows

GU Yong, YUAN Yuanyi, ZHANG Lie, DUAN Jingjing

School of Logistics Engineering, Wuhan University of Technology, Wuhan, 430063

Received:2019-09-20 Online:2020-07-25 Published:2020-08-26

摘要/Abstract

摘要： 针对多中心协同配送下的车辆路径问题，建立了总成本最小化模型，所建模型满足多中心、多需求点和半开放式的特征。考虑到问题的复杂性，设计了一种三阶段求解算法：将K-mediods聚类算法用于原始数据分解，将原规模较大的多配送中心路径问题转换成多个单配送中心路径问题；设计了改进多蚁群算法来求解单配送中心路径问题，得到初始方案；在调整阶段，利用节约算法优化初始方案。分析了算例，并同其他文献的算法求解结果进行对比，结果表明，所提算法比GA-ACO算法求解得到的单中心配送最优路径值减小32.16%，总成本减小30.42%；比狼群算法解得的最优路径值和总成本均减小8.99%；比蚁群算法求得的最优路径值减小24.76%，最小配送成本减小3.40%，从而验证了所建模型的合理性和所设计多阶段算法的有效性。

关键词: 多中心车辆路径问题, 协同配送, 时间窗, K-mediods聚类, 多蚁群算法

Abstract: Aiming at the vehicle routing problem under multi-depot collaborative distribution, a minimization model of total costs was established. The model satisfied the characteristics of multi-depot, multi-demand points and half-open. Considering the complexity of the problem, a three-stage solution algorithm was designed. K-mediods clustering algorithm was used to decompose the original data. The original large-scale multi-depot VRP was transformed into multiple single distribution center routing problems. Then, an improved multi-ant colony algorithm was designed to solve the single distribution center routing problem, and the initial scheme was obtained. In the adjustment stages, the initial scheme was optimized by using the saving mileage method. At last, the simulation results were compared with ones of the other methods. The results show that the proposed algorithm is better than GA-ACO algorithm, wolf pack algorithm and ant colony algorithm. The optimal path is optimized by 32.16%, 8.99% and 24.76% respectively, and the total cost is optimized by 30.42%, 8.99% and 3.40% separately, which verifies the rationality of the model and the effectiveness of the multi-stage algorithm design.

Key words: multi-depot vehicle routing problem(VRP), collaborative distribution, time windows, K-mediods clustering, multi-ant colony algorithm

中图分类号:

F252
TP301.6

辜勇, 袁源乙, 张列, 段晶晶. 带时间窗的多中心半开放式车辆路径问题[J]. 中国机械工程, 2020, 31(14): 1733-1740.

GU Yong, YUAN Yuanyi, ZHANG Lie, DUAN Jingjing. Multi-depot Half Open Vehicle Routing Problem with Time Windows[J]. China Mechanical Engineering, 2020, 31(14): 1733-1740.

参考文献

[1] 刘冉,江志斌,耿娜,等. 半开放式多车场车辆路径问题[J].上海交通大学学报,2010,44(11):1539-1545. LIU Ran, JIANG Zhibin, GENG Na, et al. Semi-open Multi-depot Vehicle Routing Problem[J]. Journal of Shanghai Jiaotong University, 2010, 44(11):1539-1545.
[2] SOTO M, SEVAUX M, REINHOLZ A,et al. Multiple Neighborhood Search, Tabu Search and Ejection Chains for the Multi-depot Open Vehicle Routing Problem[J].Computers & Industrial Engineering,2017,107:211-222.
[3] 戴树贵,陈文兰,潘荫荣,等.多配送中心车辆路径安排问题混合蚁群算法[J].四川大学学报(工程科学版),2008,40(6):154-158. DAI Shugui, CHEN Wenlan, PAN Yinrong, et al. A Hybrid Ant Colony Algorithm for Multi Depot Vehicle Routing Problem[J]. Journal of Sichuan University(Engineering Science Edition),2008,40(6):154-158.
[4] FITRIANA R, MOENGIN P, KUSUMANINGRUM U. Improvement Route for Distribution Solutions MDVRP (Multi Depot Vehicle Routing Problem) Using Genetic Algorithm[J]. IOP Conference Series:Materials Science and Engineering, 2019, 528(1):12-42.
[5] 盛虎宜,刘长石,鲁若愚.基于共同配送策略的农村电商集送货一体化车辆路径问题[J].系统工程,2019,37(3):98-104. SHENG Huyi, LIU Changshi, LU Ruoyu. Vehicle Routing Problem with Simultaneous Pick-up and Delivery in Rural Electronic Commerce Based on Joint Distribution Strategy[J]. System Engineering, 2019,37(3):98-104.
[6] 陈呈频,韩胜军,鲁建厦,等.多车场与多车型车辆路径问题的多染色体遗传算法[J].中国机械工程,2018,29(2):218-223. CHEN Chengpin, HAN Shengjun, LU Jianxia, et al. A Multi-chromosome Genetic Algorithm for Multi-depot and Multi-type Vehicle Routing Problems[J]. China Mechanical Engineering, 2018,29(2):218-223.
[7] HEECHUL B, ILKYEONG M. Multi-depot Vehicle Routing Problem with Time Windows Considering Delivery and Installation Vehicles[J]. Applied Mathematical Modelling, 2016, 40(13/14):6536-6549.
[8] 于滨,靳鹏欢,杨忠振.两阶段启发式算法求解带时间窗的多中心车辆路径问题[J].系统工程理论与实践,2012,32(8):1793-1800. YU Bin, JIN Penghuan, YANG Zhongzhen. Two Stage Heuristic Algorithm for Multi-depot Vehicle Routing Problem with Time Windows[J]. System Engineering Theory and Practice, 2012,32(8):1793-1800.
[9] 肖玉徽,楼振凯,戴晓震.带时间窗的多配送中心协同配送问题研究[J].数学的实践与认识,2018,48(14):171-177. XIAO Yuhui, LOU Zhenkai, DAI Xiaozhen. Study on Collaborative Distribution Problem of Multiple-distribution with Time Windows[J]. Mathematics in Practice and Understanding, 2018,48(14):171-177.
[10] 闫军,董海鹰,王亚楠,等.电子商务条件下城市物流协同配送车辆路径问题研究[J].兰州交通大学学报,2019,38(1):37-42. YAN Jun, DONG Haiying, WANG Yanan, et al. Research on Vehicle Routing Problem of Logistics Collaborative Distribution under the Condition of E-commerce[J]. Journal of Lanzhou Jiaotong University, 2019,38(1):37-42.
[11] LI Jian, LI Yang, PARDALOS P M. Multi-depot Vehicle Routing Problem with Time Windows under Shared Depot Resources[J]. Journal of Combinatorial Optimization, 2016,31(2):515-532.
[12] WANG Xuping, ZHAN Hongxin, ZHANG Jun. Research of Oil Product Secondary Distribution Optimization Based on Collaborative Distribution[J]. Procedia Computer Science,2015,60:1367-1376.
[13] GIOSA I D, TANSINI I L, VIERA I O. NewAssignment Algorithms for the Multi-depot Vehicle Routing Problem[J]. Journal of the Operational Research Society, 2002, 53(9):977-984.
[14] 辜勇,张列,李志远,等.基于GA-ACO的带时间窗车辆路径问题[J].物流技术,2019,38(3):53-60. GU Yong, ZHANG Lie, LI Zhiyuan,et al. Vehicle Routing Problem with Time Window Based on GA-ACO[J]. Logistics Technology, 2019,38(3):53-60.
[15] 叶勇,张惠珍.多配送中心车辆路径问题的狼群算法[J].计算机应用研究,2017,34(9):2590-2593. YE Yong, ZHANG Huizhen. Wolf Swarm Algorithm for Multi-distribution Center Vehicle Routing Problem[J]. Computer Application Research, 2017,34(9):2590-2593.
[16] 范厚明,杨翔,李荡, 等. 基于生鲜品多中心联合配送的半开放式车辆路径问题[J].计算机集成制造系统,2019,25(1):256-266. FAN Houming, YANG Xiang, LI Dang, et al. Semi-open Vehicle Routing Problem Based on Fresh Products Multi-center Joint Distribution[J]. Computer Integrated Manufacturing System, 2019, 25(1):256-266.

带时间窗的多中心半开放式车辆路径问题

Multi-depot Half Open Vehicle Routing Problem with Time Windows

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

[1]	刘雪梅1;王笑1;柳跃雷2. 模糊时间窗约束下的装配线物料配送方案优化[J]. 中国机械工程, 2020, 31(17): 2095-2103.
[2]	贺长征1;宋豫川1;雷琦1;吕向飞1;刘软香1;陈进2. 柔性作业车间多自动导引小车和机器的集成调度[J]. 中国机械工程, 2019, 30(04): 438-447.
[3]	肖鹏飞1;张超勇1;罗敏1;林文文2. 基于自适应动态无偏最小二乘支持向量机的刀具磨损预测建模[J]. 中国机械工程, 2018, 29(07): 842-849.
[4]	朱传军 , 宋文家, 张超勇, 曹静 , 朱孟周. 基于维修时间窗的柔性作业车间调度优化研究[J]. 中国机械工程, 2016, 27(10): 1337-1343.
[5]	周蓉, 沈维蕾, 刘明周, 赵韩. 带时间窗装卸一体化车辆路径问题的混合离散粒子群优化算法[J]. 中国机械工程, 2016, 27(04): 494-502.
[6]	刘琼, 刘秀城, 张超勇, 饶运清. 基于改进蚁群算法的带时间窗废品收集车辆路径问题[J]. 中国机械工程, 2015, 26(2): 247-244.