山东大学学报 (工学版) ›› 2024, Vol. 54 ›› Issue (5): 62-73.doi: 10.6040/j.issn.1672-3961.0.2023.139
李二超,张智钊*
LI Erchao, ZHANG Zhizhao*
摘要： 针对客户满意度和时间窗时域单一的问题,提出一种多时域分级方式衡量车辆配送进度,该设计细化普通时间窗时域,分成多个时域衡量车辆行进位置,算法方面,遗传算法(genetic algorithm, GA)与变邻域下降搜索算法(variable neighborhood descent, VND)的组合优化形式得到静态预优化路径最优车辆行进线路。动态调度周期中,现有贪婪订单插入算法(greedy order insertion algorithm, GOIA)搜索效率不高,提出一种改进后的贪婪订单插入算法(improved new greedy insertion algorithm, IGOIA),摒弃了GOIA随机插入路径的方式,最有原则的将订单插入到配送路径中去,将其与变邻域下降搜索算法组合优化(Genetic algorithm-Variable Neighborhood Descent, GAVND),对未服务的客户点进行局部优化。通过数学模型优化和求解算法改进,在统一平台上与IGOIA-GAVND、GOIA-GAVND与GOIA-GA2-opt的遗传算法改进形式进行对比试验,改进后的动态订单插入算法在不同规模的Solomon算例下,平均目标值降低了11%,算法平均计算时间降低了2.74 s,实例分析中,成本解分别节约了23%、31%、21%,研究结果证明了原则订单插入算法在滚动周期策略作用下可以获得较高质量的解。
中图分类号:
| [1] BOZORGI-AMIRI A, KHORSI M. A dynamic multi-objective location-routing model for relief logistic planning under uncertainty on demand, travel time, and cost parameters[J]. The International Journal of Advanced Manufacturing Technology, 2016, 85: 1633-1648. [2] JAMES J Q, YU W, GU J. Online vehicle routing with neural combinatorial optimization and deep reinforcement learning[J]. IEEE Transactions on Intelligent Trans-portation Systems, 2019, 20(10): 3806-3817. [3] SAINT-GUILLAIN M, PAQUAY C, LIMBOURG S. Time-dependent stochastic vehicle routing problem with random requests: Application to online police patrol management in Brussels[J]. European Journal of Operational Research, 2021, 292(3): 869-885. [4] 王仁民, 闭应洲, 刘阿宁, 等. 改进变邻域搜索算法求解动态车辆路径问题[J]. 计算机工程与应用, 2014, 50(2):237-241. WANG Renmin, GUAN Yingzhou, LIU Aning, et al. Improved variable neighborhood search algorithm for Dynamic Vehicle Routing Problem[J]. Computer Engineering and Applications, 2014, 50(2): 237-241. [5] 马欢, 张建伟, 赵进超, 等. 求解VRPSDP的变邻域混合遗传算法[J]. 郑州大学学报(工学版), 2015, 36(3): 120-124. MA Huan, ZHANG Jianwei, ZHAO Jinchao, et al. Variable neighborhood hybrid genetic algorithm for VRPSDP[J]. Journal of Zhengzhou University(Engineering Edition), 2015, 36(3): 120-124. [6] 康熙沛, 杨家其, 余昊, 等. 基于离散灰狼算法的带软时间窗车辆路径规划问题[J]. 武汉理工大学学报(交通科学与工程版), 2022, 46(4): 598-603. KANG Xipei, YANG Jiaqi, YU Hao, et al. Vehicle path planning with soft time window based on discrete Gray Wolf algorithm[J]. Journal of Wuhan University of Technology(Transportation Science and Engineering), 2022, 46(4): 598-603. [7] SOLOMON M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research, 1987, 35(2): 254-265. [8] 郭富蓉, 巩建忠, 崔袁丁. 时变需求环境下同时取送货的车辆路径问题优化研究[J]. 甘肃科技纵横, 2021, 50(5): 51-56. GUO Furong, GONG Jianzhong, CUI Yuan-Ding. Research on optimization of vehicle routing problem for simultaneous pickup and delivery under time-varying demand environment[J]. Gansu Science and Technology, 2021, 50(5): 51-56. [9] 陈萍, 黄厚宽, 董兴业. 求解卸装一体化的车辆路径问题的混合启发式算法[J]. 计算机学报, 2008(4): 565-573. CHEN Ping, HUANG Houkuan, DONG Xingye. Hybrid Heuristic Algorithm for Solving Vehicle Routing Problem with integrated unloading and loading[J]. Chinese Journal of Computers, 2008(4): 565-573. [10] 陈久梅, 李英娟, 胡婷, 等. 开放式带时间窗车辆路径问题及变邻域搜索算法[J]. 计算机集成制造系统, 2021, 27(10): 3014-3025. CHEN Jiumei, LI YingJuan, HU Ting, et al. Open vehicle routing problem with time window and variable neighborhood search algorithm[J]. Computer Integrated Manufacturing Systems, 2021, 27(10): 3014-3025. [11] 李兵, 郑四发, 曹剑东, 等. 求解客户需求动态变化的车辆路径规划方法[J]. 交通运输工程学报, 2007(1): 106-110. LI Bing, ZHENG Sifa, CAO Jiandong, et al. Vehicle path planning method to Solve the dynamic change of Customer Demand[J]. Journal of Traffic and Transportation Engineering, 2007(1): 106-110. [12] XUE G, WANG Y, GUAN X, et al. A combined GA-TS algorithm for two-echelon dynamic vehicle routing with proactive satellite stations[J]. Computers & Industrial Engineering, 2022, 164(2): 107899. [13] FABRI A, RECHT P. On dynamic pickup and delivery vehicle routing with several time windows and waiting times[J]. Transportation Research Part B: Method-ological, 2006, 40(4): 335-350. [14] 宋娟, 崔艳. 基于改进遗传算法的同城快递配送模型[J]. 电子技术应用, 2014, 40(12): 136-139. SONG Juan, CUI Yan. Same-city express distribution model based on improved genetic algorithm[J]. Application of Electronic Technique, 2014, 40(12): 136-139. [15] POTVIN J Y, XU Y, BENYAHIA I. Vehicle routing and scheduling with dynamic travel times[J]. Computers & Operations Research, 2006, 33(4): 1129-1137. [16] DONATI A V, MONTEMANNI R, CASAGRANDE N, et al. Time dep-endent vehicle routing problem with a multi ant colony system[J]. European Jounal of Operational Research, 2008, 185(3): 1174-1191. [17] SALHI S, NAGY G. A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling[J]. Journal of the operational Research Society, 1999, 50(10): 1034-1042. [18] 杨丹. 动态车辆路径问题的算法设计与系统实现[D]. 哈尔滨: 哈尔滨工业大学, 2016. YANG Dan. Algorithm design and system implementation of dynamic vehicle routing problem[D]. Harbin: Harbin Institute of Technology, 2016. [19] 焦尚强. 取送货一体化的动态车辆路径问题研究[D]. 广州: 广东工业大学, 2021. JIAO Shangqiang. Research on dynamic vehicle routing problem of pick-up and delivery integration[D]. Guangzhou: Guangdong University of Technology, 2021. [20] 王咪. 基于2-Opt免疫遗传算法的冷链配送路径优化问题研究[J]. 物流技术, 2016, 35(7): 72-75. WANG Mi. Research on cold chain distribution route optimization based on 2-Opt immune genetic algorithm[J]. Logistics Technology, 2016, 35(7): 72-75. [21] 葛显龙, 王旭, 邓蕾. 基于联合配送的开放式动态车辆路径问题及算法研究[J]. 管理工程学报, 2013, 27(3): 60-68. GE Xianlong, WANG Xu, DENG Lei. Research on open dynamic vehicle routing problem and Algorithm based on joint distribution[J]. Journal of Management Engineering, 2013, 27(3): 60-68. |
| [1] | 赵姣,杨倩倩,胡大伟,胡卉,李洋. 基于排队模型的电动物流车充电站选址和运输路径问题[J]. 山东大学学报 (工学版), 2024, 54(2): 47-59. |
| [2] | 孙东磊,杨思,韩学山,叶平峰,王宪,刘蕊. 高比例风电接入下计及时段间耦合旋转备用响应风险的动态经济调度方法[J]. 山东大学学报 (工学版), 2022, 52(5): 111-122. |
| [3] | 孙东磊, 鉴庆之, 李智琦, 韩学山, 王明强, 陈博, 付一木. 源网协调的电力系统均匀性规划[J]. 山东大学学报 (工学版), 2022, 52(5): 92-101. |
| [4] | 宋修广,张营超,庄培芝,杨鹤,张海凤,王娟. 基于遗传算法的道路安定极限优化求解方法[J]. 山东大学学报 (工学版), 2021, 51(5): 1-7. |
| [5] | 郭蓉蓉,张汝华,马信辉,郭森垚. 近交叉口路中式快速公交站点选址优化[J]. 山东大学学报 (工学版), 2021, 51(3): 61-67. |
| [6] | 孙润稼,朱海南,刘玉田. 基于偏好多目标优化和遗传算法的输电网架重构[J]. 山东大学学报 (工学版), 2019, 49(5): 17-23. |
| [7] | 顾雪平, 杨超, 梁海平, 王元博, 李少岩. 异步电网并行协调恢复策略的优化制定方法[J]. 山东大学学报 (工学版), 2019, 49(5): 9-16. |
| [8] | 公冶小燕,林培光,任威隆. 基于Grefenstette编码和2-opt优化的遗传算法[J]. 山东大学学报 (工学版), 2018, 48(6): 19-26. |
| [9] | 陈嘉杰,王金凤. 基于蚁群算法求解Choquet模糊积分模型[J]. 山东大学学报(工学版), 2018, 48(3): 81-87. |
| [10] | 王飞,徐健,李伟,汪新浩,施啸寒. 基于分布式储能系统的风储滚动优化调度方法[J]. 山东大学学报(工学版), 2017, 47(6): 89-94. |
| [11] | 王常顺,肖海荣. 基于自抗扰控制的水面无人艇路径跟踪控制器[J]. 山东大学学报(工学版), 2016, 46(4): 54-59. |
| [12] | 刘德宝, 吴耀华, 郭耀阳, 王艳艳. 基于串并行混合拣选策略的自动拣选系统品项分配优化[J]. 山东大学学报(工学版), 2015, 45(6): 36-44. |
| [13] | 董红斌, 张广江, 逄锦伟, 韩启龙. 一种基于协同进化方法的聚类集成算法[J]. 山东大学学报(工学版), 2015, 45(2): 1-9. |
| [14] | 梁兴建, 詹志辉. 基于双模式变异策略的改进遗传算法[J]. 山东大学学报(工学版), 2014, 44(6): 1-7. |
| [15] | 孙鹏,程世庆*,谢敬思,张海瑞. 预测混合生物质灰熔点的CV-GA-SVM模型[J]. 山东大学学报(工学版), 2012, 42(2): 108-111. |
|
