带时间窗的时间依赖型同时取送货车辆路径问题研究

doi:10.16097/j.cnki.1009-6744.2024.04.022

交通运输系统工程与信息 ›› 2024, Vol. 24 ›› Issue (4): 231-242.DOI: 10.16097/j.cnki.1009-6744.2024.04.022

带时间窗的时间依赖型同时取送货车辆路径问题研究

何美玲¹，杨梅¹，韩珣^*2a,2b，武晓晖¹

1. 江苏大学，汽车与交通工程学院，江苏镇江212013；2.四川警察学院，a.智能警务四川省重点实验室， b. 道路交通管理系，四川泸州646000

收稿日期:2024-04-14 修回日期:2024-05-06 接受日期:2024-05-13 出版日期:2024-08-25 发布日期:2024-08-22
作者简介:何美玲(1982- )，女，江苏江都人，副教授。
基金资助:
教育部人文社会科学研究青年基金 (21YJCZH180)；智能警务四川省重点实验室开放课题 (ZNJW2023KFMS004)；江苏省研究生科研创新计划项目 (KYCX22_3674)。

Time-dependent Vehicle Routing Optimization Considering Simultaneous Pickup-delivery and Time Windows

HEMeiling¹,YANG Mei¹,HAN Xun^*2a,2b,WU Xiaohui¹

1. School of Automotive and Traffic Engineering, Jiangsu University, Zhenjiang 212013, Jiangsu, China; 2a. Intelligent Policing Key Laboratory of Sichuan Province, 2b. Department of Transportation Management, Sichuan Police College, Luzhou 646000, Sichuan, China

Received:2024-04-14 Revised:2024-05-06 Accepted:2024-05-13 Online:2024-08-25 Published:2024-08-22
Supported by:
TheHumanityand SocialScienceYouthFoundation of Ministry of Education of China (21YJCZH180)；Opening Project of Intelligent Policing Key Laboratory of Sichuan Province (ZNJW2023KFMS004)；Jiangsu Province Graduate Research Innovation Program (KYCX22_3674)。

摘要/Abstract

摘要： 针对带时间窗的时间依赖型同时取送货车辆路径问题(TimeDependentVehicleRouting Problem with Simultaneous Pickup-Delivery and Time Windows, TDVRPSPDTW)，本文建立以车辆固定成本、驾驶员成本、燃油消耗及碳排放成本之和为优化目标的数学模型；并在传统蚁群算法的基础上，利用节约启发式构造初始解初始化信息素，改进状态转移规则，引入局部搜索策略，提出一种带自适应大邻域搜索的混合蚁群算法(AntColony Optimization with Adaptive Large Neighborhood Search, ACO-ALNS)进行求解；最后，分别选取基准问题算例和改编生成TDVRPSPDTW算例进行实验。实验结果表明：本文提出的ACO-ALNS算法可有效解决TDVRPSPDTW的基准问题；相较于模拟退火算法和带局部搜索的蚁群算法，本文算法求解得到的总配送成本最优值平均分别改善7.56%和2.90%；另外，相比于仅考虑碳排放或配送时间的模型，本文所构建的模型综合多种因素，总配送成本平均分别降低4.38%和3.18%，可有效提高物流企业的经济效益。

关键词: 物流工程, 同时取送货车辆路径问题, 蚁群算法, 时间依赖, 时间窗

Abstract: To solve the time-dependent vehicle routing problem with simultaneous pickup-delivery and time windows (TDVRPSPDTW), this paper proposes a mathematical model with the sum of vehicle fixed cost, driver cost, fuel consumption and carbon emission cost as the optimization objective. Based on the traditional ant colony optimization, this paper introduces a hybrid ant colony optimization with adaptive large neighborhood search (ACO-ALNS). It uses heuristic initialization of pheromones, improves state transition rules, and uses local search strategies to improve solution quality. Benchmark problem instances and adapted TDVRPSPDTW instances are utilized for experimentation. The experimental results demonstrate the effectiveness of the proposed ACO-ALNS algorithm in solving the benchmark problem of TDVRPSPDTW. Compared to the simulated annealing and ant colony optimization with local search, the proposed algorithm improves the optimal value of total distribution cost by an average of 7.56% and 2.90%, respectively. In addition, the presented model incorporates multiple factors, resulting in an average reduction of 4.38% and 3.18% in total distribution costs compared to models that only consider carbon emissions or delivery time. This improvement can effectively enhance the economic benefits of logistics enterprises.

Key words: logistics engineering, vehicle routing problem with simultaneous pickup-delivery, ant colony optimization, time-dependent, time windows

中图分类号:

U492.22

何美玲, 杨梅, 韩珣, 武晓晖. 带时间窗的时间依赖型同时取送货车辆路径问题研究[J]. 交通运输系统工程与信息, 2024, 24(4): 231-242.

HEMeiling, YANG Mei, HAN Xun, WU Xiaohui. Time-dependent Vehicle Routing Optimization Considering Simultaneous Pickup-delivery and Time Windows[J]. Journal of Transportation Systems Engineering and Information Technology, 2024, 24(4): 231-242.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/10.16097/j.cnki.1009-6744.2024.04.022

http://www.tseit.org.cn/CN/Y2024/V24/I4/231

参考文献

[1]ZHOU S, ZHANG D, JI B, et al. A MILP model and heuristic method for the time-dependent electric vehicle routing and scheduling problem with time windows[J]. Journal of Cleaner Production, 2024, 434: 140188.

[2]周鲜成,刘长石,周开军,等.时间依赖型绿色车辆路径模型及改进蚁群算法[J].管理科学学报,2019,22 (5): 57-68. [ZHOU X C, LIU C S, ZHOU K J, et al. Improved ant colony algorithm and modelling of time dependent green vehicle routing problem[J]. Journal of Management Sciences in China, 2019, 22(5): 57-68.]

[3] 珠兰,马潇,刘卓凡.时间依赖型绿色车辆路径问题研究[J]. 交通运输系统工程与信息, 2021, 21(6): 187 194. [ZHU L, MA X, LIU Z F. Time-dependent green vehicle routing problem[J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(6): 187-194.]

[4]WANG H F, CHEN Y Y. A genetic algorithm for the simultaneous delivery and pickup problems with time window[J]. Computers & Industrial Engineering, 2012, 62 (1): 84-95.

[5]LIU F, WANG L, GUI M, et al. A hybrid heuristic algorithm for urban distribution with simultaneous pickup-delivery and time window[J]. Journal of Heuristics, 2023, 29(2): 269-311.

[6]辛禹辰,李润超,杨华龙.基于等待策略的同时送取货车辆路径问题干扰管理研究[J].交通运输系统工程与信息, 2023, 23(5): 155-161. [XIN Y C, LI R C, YANG H L. Disturbance management of VRPSDP based on waiting strategy[J]. Journal of Transportation Systems Engineering and Information Technology, 2023, 23(5): 155-161.]

[7]ZHOU J, LI H, GU Y J, et al. A novel two-phase approach for the bi-objective simultaneous delivery and pickup problem with fuzzy pickup demands[J]. International Journal of Production Economics, 2021, 234: 108057.

[8] ZHOU G, LI D, BIAN J, et al. Two-echelon time dependent vehicle routing problem with simultaneous pickup and delivery and satellite synchronization[J]. Computers & Operations Research, 2024, 167: 106600.

[9] ICHOUA S, GENDREAU M, POTVIN J. Vehicle dispatching with time-dependent travel times[J]. European Journal of Operational Research, 2003, 144(2): 379-396.

[10] MAJIDI S, HOSSEINI MOTLAGH S M, IGNATIUS J. Adaptive large neighborhood search heuristic for pollution-routing problem with simultaneous pickup and delivery[J]. Soft Computing, 2018, 22(9): 2851-2865.

[11] ANDRES FIGLIOZZI M. The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics[J]. Transportation Research Part E: Logistics and Transportation Review, 2012, 48(3): 616 636.

[12] 范厚明, 李荡,孔靓,等.模糊需求下时间依赖型车辆路径优化[J]. 控制理论与应用,2020, 37(5): 950-960. [FAN H M, LI D, KONG L, et al. Optimization for time dependent vehicle routing problem with fuzzy demand[J]. Control Theory & Applications, 2020, 37(5): 950-960.]

[13] WANG C, MU D, ZHAO F, et al. A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup-delivery and time windows[J]. Computers & Industrial Engineering, 2015, 83: 111-122.

[14] 王超, 刘超, 穆东,等.基于离散布谷鸟算法求解带时间窗和同时取送货的车辆路径问题[J].计算机集成制造系统, 2018, 24(3): 570-582. [WANG C, LIU C, MU D, et al. VRPSPDTW problem solving by discrete cuckoo search[J]. Computer Integrated Manufacturing Systems, 2018, 24(3): 570-582.]

[15] WU H, GAO Y. An ant colony optimization based on local search for the vehicle routing problem with simultaneous pickup-delivery and time window[J]. Applied Soft Computing, 2023, 139: 110203.

[16] CHEN J, LIAO W, YU C. Route optimization for cold chain logistics of front warehouses based on traffic congestion and carbon emission[J]. Computers & Industrial Engineering, 2021, 161: 107663.

带时间窗的时间依赖型同时取送货车辆路径问题研究

Time-dependent Vehicle Routing Optimization Considering Simultaneous Pickup-delivery and Time Windows

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	杨华龙, 石兴江, 辛禹辰. 全渠道电商库存路径及定价问题优化研究[J]. 交通运输系统工程与信息, 2024, 24(4): 223-230.
[2]	孙文杰, 张锦, 刘娇, 李国旗. 客车代运与送提一体下的山区农村寄递网络优化[J]. 交通运输系统工程与信息, 2024, 24(3): 94-102.
[3]	许波桅, 范会尧, 李军军. 基于势博弈的自动化码头路网流量均衡研究[J]. 交通运输系统工程与信息, 2024, 24(3): 255-264.
[4]	刘新全, 汪鑫羽, 黄英艺. 基于用户偏好行为的物流枢纽网络负载均衡优化[J]. 交通运输系统工程与信息, 2024, 24(3): 265-276.
[5]	宋丽英, 赵世超, 卞骞, 杜鹏, 沈鹏举. 低碳视角下城乡区域混合车队生鲜配送路径问题研究[J]. 交通运输系统工程与信息, 2023, 23(6): 250-261.
[6]	刘永, 岳志城, 王勇. 托盘装载约束下带时间窗的配送车辆路径优化研究[J]. 交通运输系统工程与信息, 2023, 23(6): 262-273.
[7]	辛禹辰, 李润超, 杨华龙. 基于等待策略的同时送取货车辆路径问题干扰管理研究[J]. 交通运输系统工程与信息, 2023, 23(5): 155-161.
[8]	任婧璇, 常孝亭, 巫威眺, 靳文舟. 考虑候选站点和全服务过程的需求响应接驳公交调度[J]. 交通运输系统工程与信息, 2023, 23(5): 202-214.
[9]	温斌宾, 何世伟, 迟居尚, 金福才. 基于改进分支定价算法的器具取配送运输问题研究[J]. 交通运输系统工程与信息, 2023, 23(3): 223-234.
[10]	张锦, 朱红星, 申皓, 李国旗. 复杂环境下工程建设项目应急物流选址一路径问题研究[J]. 交通运输系统工程与信息, 2023, 23(3): 280-289.
[11]	郑琰, 贲宇姝, 王康得, 姜晓红. 物流企业的碳排放效率评价及驱动因素分析[J]. 交通运输系统工程与信息, 2023, 23(2): 11-21.
[12]	吴暖, 代焕杰, 李季涛, 蒋奇含. 考虑时间容忍度的冷链物流配送路径多目标优化[J]. 交通运输系统工程与信息, 2023, 23(2): 275-284.
[13]	石褚巍, 马昌喜, 麻存瑞. 基于两阶段鲁棒优化的可靠性物流网络设计[J]. 交通运输系统工程与信息, 2023, 23(2): 285-299.
[14]	闫芳, 邓德萍, 柴福良, 马艳芳. 考虑环境负效应的智能垃圾桶动态收运路径优化问题[J]. 交通运输系统工程与信息, 2023, 23(1): 265-274.
[15]	靳志宏, 黄颖, 张佳艺, 徐世达. 甩箱模式下考虑多箱型任务组合的集卡调度优化[J]. 交通运输系统工程与信息, 2022, 22(5): 243-252.