基于改进蚁群算法的外卖配送路径规划研究
作者:
中图分类号:

F252;TP18

基金项目:

中央高校基本科研业务费战略新兴资助项目(N2103028)


Takeout delivery path planning based on improved ant colony optimization algorithm
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • | | |
  • 文章评论
    摘要:

    从外卖配送员角度出发提出一种改进蚁群算法(Improved Ant Colony Optimization,IACO),在此基础上进行外卖配送路径规划研究.首先通过蚁群算法(Ant Colony Optimization,ACO)求解得到初始规划路径,然后通过大规模邻域搜索算法(Large Neighborhood Search,LNS)优化初始规划路径,通过将ACO和LNS算法结合,提高求解质量.为了验证方法的有效性,对外卖配送过程进行仿真,并且选用不同订单数量场景进行对照分析.根据最优配送方案路线图和目标罚函数的最优值可以得出,IACO算法是有效的,且可以提高外卖配送员外卖配送的效率.IACO算法不但能够提升配送的智能化水平,还从外卖配送员的角度提出一种更为人性化的配送方法,支持网络互联外卖平台派送系统的可持续化发展.

    Abstract:

    It is impossible for takeaway delivery staff to plan the takeout delivery route balancing rationality and efficiency.To address this problem,an Improved Ant Colony Optimization (IACO) algorithm is proposed.The initial routes are obtained using the Ant Colony Optimization (ACO) algorithm and then optimized using Large Neighborhood Search (LNS) algorithm.The solution quality is improved by combining the ACO algorithm with the LNS algorithm.The proposed algorithm is verified by simulating the delivery routes for different number of takeout orders.Comparative analysis shows that the proposed IACO algorithm can increase the takeout delivery efficiency,according to the optimal distribution plan and the ideal value of the objective penalty function.The proposed strategy can enhance the intelligence and promote the long-term growth of the delivery system of Internet-connected takeout platforms.

    参考文献
    [1] 初良勇,闫淼,胡美丽,等.生鲜产品物流配送路径优化研究综述及展望[J].物流研究,2021,3(1):5-13 CHU Liangyong,YAN Miao,HU Meili,et al.Review and prospect of fresh product logistics distribution route optimization[J].Logistics Research,2021,3(1):5-13
    [2] 赵金龙,蒋忠中,万明重,等.考虑配送截止时间的"货到人"订单拣选优化问题研究[J/OL].中国管理科学:1-12[2022-12-08].https://doi.org/10.16381/j.cnki.issn1003-207x.2022.1049 ZHAO Jinlong,JIANG Zhongzhong,WAN Mingzhong,et al.Optimization of parts-to-picker order picking with due dates[J/OL].China Management Science:1-12[2022-12-08].https://doi.org/10.16381/j.cnki.issn1003-207x.2022.1049
    [3] 周成昊,吕博轩,周翰宇,等.以商圈为中心的O2O动态外卖配送路径优化模型与算法[J].运筹学学报,2022,26(3):17-30 ZHOU Chenghao,LÜ Boxuan,ZHOU Hanyu,et al.Optimization model and algorithm for online to offline dynamic take-out delivery routing problem centered on business districts[J].Operations Research Transactions,2022,26(3):17-30
    [4] 刘云忠,宣慧玉.车辆路径问题的模型及算法研究综述[J].管理工程学报,2005,19(1):124-130 LIU Yunzhong,XUAN Huiyu.Summarizing research on models and algorithms for vehicle routing problem[J].Journal of Industrial Engineering and Engineering Management,2005,19(1):124-130
    [5] 毕华玲,赵亚风,卢福强,等.考虑客户风险偏好的第四方物流路径问题研究[J/OL].南京信息工程大学学报(自然科学版):1-12[2022-06-16].http://kns.cnki.net/kcms/detail/32.1801.N.20220615.1221.002.html BI Hualing,ZHAO Yafeng,LU Fuqiang,et al.Research on 4PL routing problem considering customer risk preference[J/OL].Journal of Nanjing University of Information Science & Technology (Natural Science Edition):1-12[2022-06-16].http://kns.cnki.net/kcms/detail/32.1801.N.20220615.1221.002.html
    [6] 苏涛,韩庆田,李文强,等.VRP问题蚁群算法研究[J].计算机与现代化,2012(11):18-21,25 SU Tao,HAN Qingtian,LI Wenqiang,et al.Research on VRP problem based on ant colony algorithm[J].Computer and Modernization,2012(11):18-21,25
    [7] 贺琪,官礼和,崔焕焕.硬时间窗VRP的混合变邻域禁忌搜索算法[J].计算机工程与应用,2023,59(13):82-91 HE Qi,GUAN Lihe,CUI Huanhuan.Hybrid variable neighborhood tabu search algorithm for vehicle routing problem with hard time window[J].Computer Engineering and Application,2023,59(13):82-91
    [8] 王东.改进多种群遗传算法的研究及其在车辆路径优化的应用[D].南宁:广西大学,2016 WANG Dong.Research on improved multi-population genetic algorithm and its application in vehicle routing optimization[D].Nanning:Guangxi University,2016
    [9] 董平先,郭放,陈晨,等.基于优化蚁群算法的电缆敷设路径规划[J].南京信息工程大学学报(自然科学版),2023,15(2):210-217 DONG Pingxian,GUO Fang,CHEN Chen,et al.Cable laying path planning based on optimized ant colony algorithm[J].Journal of Nanjing University of Information Science & Technology (Natural Science Edition),2023,15(2):210-217
    [10] Zhang X,Wang J Q.Hybrid ant algorithm and applications for vehicle routing problem[J].Physics Procedia,2012,25:1892-1899
    [11] 王晓东,张永强,薛红.基于改进蚁群算法对VRP线路优化[J].吉林大学学报(信息科学版),2017,35(2):198-203 WANG Xiaodong,ZHANG Yongqiang,XUE Hong.Improved ant colony algorithm for VRP[J].Journal of Jilin University (Information Science Edition),2017,35(2):198-203
    [12] Donati A V,Montemanni R,Casagrande N,et al.Time dependent vehicle routing problem with a multi ant colony system[J].European Journal of Operational Research,2008,185(3):1174-1191
    [13] Kalayci C B,Can K Y.An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery[J].Expert Systems with Applications,2016,66:163-175
    [14] 李琳,刘士新,唐加福.改进的蚁群算法求解带时间窗的车辆路径问题[J].控制与决策,2010,25(9):1379-1383 LI Lin,LIU Shixin,TANG Jiafu.Improved ant colony algorithm for solving vehicle routing problem with time windows[J].Control and Decision,2010,25(9):1379-1383
    [15] Blum C,Eremeev A,Zakharova Y.Hybridizations of evolutionary algorithms with large neighborhood search[J].Computer Science Review,2022,46:100512
    [16] 徐倩,熊俊,杨珍花,等.基于自适应大邻域搜索算法的外卖配送车辆路径优化[J].工业工程与管理,2021,26(3):115-122 XU Qian,XIONG Jun,YANG Zhenhua,et al.Based on an adaptive large neighborhood search algorithm for take-out delivery vehicle routing optimization[J].Journal of Industrial Engineering and Management,2021,26 (3):115-122
    [17] Natalia C,Triyanti V,Setiawan G,et al.Completion of capacitated vehicle routing problem (CVRP) and capacitated vehicle routing problem with time windows (CVRPTW) using bee algorithm approach to optimize waste picking transportation problem[J].Journal of Modern Manufacturing Systems and Technology,2021,5(2):69-77
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

唐传茵,章明理,李静红,苑莹,卫美荣.基于改进蚁群算法的外卖配送路径规划研究[J].南京信息工程大学学报(自然科学版),2024,16(2):145-154
TANG Chuanyin, ZHANG Mingli, LI Jinghong, YUAN Ying, Wei Meirong. Takeout delivery path planning based on improved ant colony optimization algorithm[J]. Journal of Nanjing University of Information Science & Technology, 2024,16(2):145-154

复制
分享
文章指标
  • 点击次数:1192
  • 下载次数: 1600
  • HTML阅读次数: 1605
  • 引用次数: 0
历史
  • 收稿日期:2023-03-11
  • 在线发布日期: 2024-04-03
  • 出版日期: 2024-03-28

地址:江苏省南京市宁六路219号    邮编:210044

联系电话:025-58731025    E-mail:nxdxb@nuist.edu.cn

南京信息工程大学学报 ® 2025 版权所有  技术支持:北京勤云科技发展有限公司