基于萤火虫算法的动态车辆路径规划

doi:10.3969/j.issn.1007-7375.2022.06.013

工业工程 ›› 2022, Vol. 25 ›› Issue (6): 110-119,125.doi: 10.3969/j.issn.1007-7375.2022.06.013

基于萤火虫算法的动态车辆路径规划

董海¹, 雷凤达²

沈阳大学 1. 应用技术学院;
2. 机械工程学院，辽宁沈阳 110044

收稿日期:2021-07-11 发布日期:2022-12-23
通讯作者: 雷凤达 (1997—) ，男，辽宁省人，硕士研究生，主要研究方向为制造系统工程。E-mail：1986818288@qq.com E-mail:1986818288@qq.com
作者简介:董海(1967－)，男，山东省人，教授，博士，主要研究方向为网络化制造、供应链管理
基金资助:
国家自然科学基金资助项目(71672117)；中央引导地方科技发展资金计划资助项目(2021JH6/10500149)

Dynamic Vehicle Routing Problem with Time Windows and Capacity Constraints Based on Coordinate Firefly Algorithm

DONG Hai¹, LEI Fengda²

1. School of Applied Technology;
2. School of Mechanical Engineering, Shenyang University, Shenyang 110044, China

Received:2021-07-11 Published:2022-12-23

摘要/Abstract

摘要： 为解决城市交通道路信息或客户需求改变带来的成本浪费，提出带时间窗和容量约束的动态车辆路径问题模型和求解算法。建立以最小化车辆总成本为优化目标的带时间窗和容量约束的动态车辆路径模型 (dynamic vehicle routing problem with time windows and capacity constraints, CDVRPTW) ，并用DVRP求解器将DVRP分解成VRP问题的集合以解决动态性问题。提出坐标萤火虫算法，使萤火虫算法的离散解映射到连续域以适用于模型求解，运用局部搜索包括初始种群、增强路径、移除节点以及交换节点改进算法。结合数据集和实例，运用Matlab分析算法性能。结果表明，本文所提算法与经典求解DVRP算法相比，不论是求解速度还是解的质量都有明显提升，实际案例验证其现实意义。

关键词: 动态车辆路径问题, 萤火虫算法, 时间窗

Abstract: In order to solve the cost waste caused by the change of urban traffic road information or customer demand, a dynamic vehicle routing problem model and solution algorithm with time window and capacity constraints are proposed. Firstly, a dynamic vehicle routing problem with time windows and capacity constraints is established to minimize the total vehicle cost, and DVRP is decomposed into a set of VRP problems by DVRP solver to solve the dynamic problem. Secondly, the coordinate firefly algorithm is proposed to map the discrete solution of the firefly algorithm to the continuous domain to be suitable for the model. The local search is used to improve the algorithm, including initial population, enhanced path, removing nodes and exchanging nodes. Finally, combined with data sets and examples, Matlab is used to analyze the performance of the algorithm. The results show that the proposed algorithm is significantly better than the classical DVRP algorithm in both solution speed and solution quality, and the practical significance of the algorithm and model is verified by an actual case.

Key words: dynamic vehicle routing problem, firefly algorithm, time window

中图分类号:

U121

董海, 雷凤达. 基于萤火虫算法的动态车辆路径规划[J]. 工业工程, 2022, 25(6): 110-119,125.

DONG Hai, LEI Fengda. Dynamic Vehicle Routing Problem with Time Windows and Capacity Constraints Based on Coordinate Firefly Algorithm[J]. Industrial Engineering Journal, 2022, 25(6): 110-119,125.

参考文献

[1] PSARAFTIS H N. Vehicle routing: methods and studies[M]. Amsterdam: Elsevier Science Publishers, 1988: 223-248.
[2] YANG J, JAILLET P, MAHMASSANI H. Real-time multivehicle truckload pickup and delivery problems[J]. Transportation Science, 2004, 38(2): 135-148
[3] MONTEMANNI R, GAMBARDELLA L M, RIZZOLI A E, et al. Ant colony system for a dynamic vehicle routing problem[J]. Combinatorial Optimization, 2005, 10(4): 327-343
[4] CHEN Z, XU H. Dynamic column generation for dynamic vehicle routing with time windows[J]. Transportation Science, 2006, 40(1): 74-88
[5] 吴斌, 倪卫红, 樊树海. 开放式动态网络车辆路径问题的粒子群算法[J]. 计算机集成制造系统, 2009, 15(9): 1788-1794
WU Bin, NI Weihong, FAN Shuhai. Particle swarm optimization for vehicle routing problem in open dynamic networks[J]. Computer Integrated Manufacturing Systems, 2009, 15(9): 1788-1794
[6] PILLAC V, GUERET C, Medaglia A L. An event-driven optimization framework for dynamic vehicle routing[J]. Decision Support Systems, 2012, 47(10): 154-169
[7] 宁涛, 陈荣, 郭晨, 等. 一种基于双链量子编码的动态车辆路径问题解决策略[J]. 运筹学学报, 2015, 19(2): 72-82
NING Tao, CHEN Rong, GUO Chen, et al. A dynamic vehicle routing problem solving strategy based on double-chain quantum coding[J]. Journal of Operational Research, 2015, 19(2): 72-82
[8] BRISEIDA S, KARL F, VERENA S, et al. Variable neighborhood search for the stochastic and dynamic vehicle routing problem[J]. Annals of Operations Research, 2016, 236(2): 425-461
[9] ALCHAMI Z, MANIER H, MANIER M-A, et al. A hybrid genetic algorithm to solve a multi-objective pickup and delivery problem[J]. IFAC, 50(1), 2017: 14656-14661.
[10] 闫凯, 李爱光, 郭健. 基于混合算法的单配送中心路径优化方法[J]. 测绘科学技术学报, 2017, 33(6): 650-653
YAN Kai, LI Aiguang, GUO Jian. Method of single distribution center route optimization based on hybrid algorithm[J]. Journal of Surveying and Mapping Science and Technology, 2017, 33(6): 650-653
[11] 孙俊成, 李丹. 基于改进萤火虫算法的开放式车辆路径问题[J]. 系统仿真学报, 2018, 48(4): 182-190
SUN Juncheng, LI Dan. Open vehicle routing problem based on improved firefly algorithm[J]. Journal of System Simulation, 2018, 48(4): 182-190
[12] MAROUA G, NOUREDDINE D, SALIM B. GPU-based distributed bee swarm optimisation for dynamic vehicle routing problem[J]. International Journal of Ad Hoc and Ubiquitous Computing, 2019, 31(3): 289-307
[13] 辜羽洁, 占维, 魏强. 客户动态变更配送需求的配送路线优化研究[J]. 数学的实践与认识, 2019, 49(19): 28-41
GU Yujie, ZHAN Wei, WEI Qiang. Research on distribution route optimization of customer dynamic change distribution demand[J]. Journal of Mathematics in Practice and Theory, 2019, 49(19): 28-41
[14] 范双南, 陈纪铭, 高为民, 等. 基于改进智能水滴算法的动态车辆配送路径优化[J]. 系统仿真学报, 2020, 32(9): 1808-1817
FAN Shuangnan, CHEN Jiming, GAO Weimin, et al. Dynamic vehicle distribution route optimization based on improved intelligent water drop algorithm[J]. Journal of System Simulation, 2020, 32(9): 1808-1817
[15] ORIVALDE S, SILVA J, JOSE E L, et al. A multiple ant colony system with random variable neighborhood descent for the dynamic vehicle routing problem with time windows[J]. Soft Computing, 2020, 25(4): 1-14
[16] RESMI R, MICHAEL A. A solution to dynamic green vehicle routing problemswith time windows using spiking neural P systems with modified rules and learning[J]. The Journal of Supercomputing, 2021, 34(3): 253-285
[17] ASMA M, ABDULQADER M, ABDULLATIF G. An improved hybrid firefly algorithm for capacitated vehicle routing problem[J]. Applied Soft Computing Journal, 2019, 33(1): 409-427
[18] YANG X, HE X. Firefly algorithm: recent advances and applications[J]. International Journal of Swarm Intelligence, 2013, 1(1): 36-50

基于萤火虫算法的动态车辆路径规划

Dynamic Vehicle Routing Problem with Time Windows and Capacity Constraints Based on Coordinate Firefly Algorithm

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 14

编辑推荐

Metrics

本文评价

[1]	曹紫萱, 林宇鹏, 吴植英, 毛宁, 陈庆新, 余龙水. 客舱清洁人员调度及时间窗冲突的影响分析[J]. 工业工程, 2022, 25(5): 120-127.
[2]	王玖河, 安聪琢, 郭田宇. 时变路网下电动冷藏车配送路径优化研究[J]. 工业工程, 2022, 25(4): 60-69,107.
[3]	闫军, 常乐, 王璐璐, 赵彤. 带时间窗的同时取送货车辆路径问题求解算法[J]. 工业工程, 2021, 24(5): 72-76.
[4]	王宁, 张玉萍, 赵姣, 金子阳. 考虑碳排放及时间窗的LIRP模型与算法研究[J]. 工业工程, 2021, 24(2): 34-42.
[5]	李玉民, 邱梦, 黑柏林, 方曾利. 考虑高铁时间窗和客户满意度的生鲜品公铁联运路径选择[J]. 工业工程, 2021, 24(2): 49-56.
[6]	李博威, 户佐安, 贾叶子, 唐诗韵. 带软时间窗的同时取送货车辆路径问题研究[J]. 工业工程, 2020, 23(5): 75-81.
[7]	冯春, 秦冰芳, 叶露. 共享电动车电池配送问题研究[J]. 工业工程, 2019, 22(3): 52-56.
[8]	户佐安, 贾叶子, 李博威, 刘陆. 考虑客户满意度的车辆路径优化研究[J]. 工业工程, 2019, 22(1): 100-107.
[9]	王维军, 罗伟. 基于改进智能水滴算法的冷链物流配送路径优化问题研究[J]. 工业工程, 2017, 20(2): 38-43.
[10]	朱婷1，王旭磊2，赵来军1. 带时间窗的时变多目标危险化学品道路运输路径优化[J]. 工业工程, 2016, 19(2): 62-67.
[11]	任盼，刘冉，江志斌，董蕊. 考虑油耗的车辆调度问题模型与算法[J]. 工业工程, 2015, 18(5): 134-140.
[12]	张帆1,2，汤兵勇1. 顾客时间窗和维修需求变动下车辆维修的干扰管理优化[J]. 工业工程, 2015, 18(5): 148-153.
[13]	谢天保1，张晓雯1，仵凯博2，胡丹1. 电子商务下基于协同配送的配送中心选址研究[J]. 工业工程, 2015, 18(3): 75-81.
[14]	雷卫东，车阿大 . 带时间窗口的自动化混流生产线调度方法[J]. 工业工程, 2011, 14(5): 110-115.