Open Vehicle Routing Problem Based on Joint Distribution Mode under Time-dependent Road Networks

doi:10.12005/orms.2021.0345

Operations Research and Management Science ›› 2021, Vol. 30 ›› Issue (11): 26-33.DOI: 10.12005/orms.2021.0345

• Theory Analysis and Methodology Study • Previous Articles Next Articles

Open Vehicle Routing Problem Based on Joint Distribution Mode under Time-dependent Road Networks

LIU Chang-shi^1,2, WANG Song¹, LUO Liang³, DENG Sheng-qian¹

1. School of Business and Management, Hunan University of Technology and Business, Changsha 410205, China;
2. Key Laboratory of Hunan Province for Statistical Learning and Intelligent Computation, Hunan University of Technology and Business, Changsha 410205, China;
3. Logistics System Optimization and Operation Management Innovation Team of Collages in Hunan Province, Hunan University of Technology and Business, Changsha410205, China

Received:2020-02-12 Online:2021-11-25

时变路网条件下联合配送的开放式车辆路径问题

刘长石^1,2, 王松¹, 罗亮³, 邓胜前¹

1.湖南工商大学工商管理学院,湖南长沙 410205;
2.湖南工商大学统计学习与智能计算湖南省重点实验室,湖南长沙 410205;
3.湖南工商大学湖南省高等学校物流系统优化与运作管理创新团队,湖南长沙 410205

通讯作者: 王松(1973-),男(通讯作者),湖北荆州人,副教授,博士,研究方向:物流与供应链管理。
作者简介:刘长石(1975-),男,湖南邵阳人,副教授,博士,研究方向:物流与供应链管理。
基金资助:
国家社科基金一般项目(17BJL091);国家自然科学基金面上项目(71972069);湖南省自科基金一般项目(2019JJ40147,2021JJ30195);湖南省社科基金一般项目(16YBG004,18YBA267);湖南省教育厅一般课题(17C0881,18A297,20C0533);湖南省社科评审委一般项目(XSP20YBC251)

Abstract

Abstract: The multi-depot vehicle routing problem based on joint distribution mode in urban logistics system is studied. A multi-depot processing method is proposed in order to share all logistics resources. A calculating method for the road travel time is designed based on the time-dependent characteristics of urban road network. A mathematical model for the open time-dependent vehicle routing problem based on joint distribution mode is formulated by considering customer demand, time window, flexible vehicle departure time, fuel consumption, carbon emissions, and joint distribution mode. The objective of the model is to minimize total cost. An improved ant colony algorithm is designed to solve the problem. The experimental results verify the feasibility and validity of the proposed approaches.

Key words: time-dependent road network, joint distribution, multi-depot, open vehicle routing problem, ant colony algorithm

摘要： 针对城市物流系统中的多物流中心联合配送问题,设计一种多物流中心处理方法共享物流资源;分析城市路网的时变特性,设计路段行驶时间计算方法;综合考虑客户需求、时间窗、车辆不同出发时间、油耗、碳排放与联合配送模式等因素,以总成本最小为目标构建联合配送的开放式时变车辆路径规划模型,设计改进蚁群算法求解;实验结果表明以上方法具有可行性与有效性。

关键词: 时变路网, 联合配送, 多物流中心, 开放式车辆路径问题, 蚁群算法

CLC Number:

C931.1

LIU Chang-shi, WANG Song, LUO Liang, DENG Sheng-qian. Open Vehicle Routing Problem Based on Joint Distribution Mode under Time-dependent Road Networks[J]. Operations Research and Management Science, 2021, 30(11): 26-33.

刘长石, 王松, 罗亮, 邓胜前. 时变路网条件下联合配送的开放式车辆路径问题[J]. 运筹与管理, 2021, 30(11): 26-33.

References

[1] 殷脂,叶春明.多配送中心物流配送车辆调度问题的分层算法模型[J].系统管理学报,2014,23(4):602-606.
[2] Tu W, Fang Z X, Li Q Q, et al. A bi-level Voronoi diagram-based metaheuristic for a large-scale multi-depot vehicle routing problem[J]. Transportation Research Part E, 2014, 61: 84-97.
[3] 刘家利,马祖军.存在车辆租赁及共享且有时间窗的多配送中心开环VRP[J].系统工程理论与实践,2013,33(3):666-675.
[4] Wang Y, Ma XL, Li Z B, et al. Profit distribution in collaborative multiple centers vehicle routing problem[J]. Journal of Cleaner Production, 2017, 144: 203-219.
[5] 葛显龙,王旭,邓蕾.基于联合配送的开放式动态车辆路径问题及算法研究[J].管理工程学报,2013,27(3):60-68.
[6] 葛显龙,黄钰,谭柏川.城市物流跨区域联合配送模型与算法[J].控制与决策,2017,32(5):789-796.
[7] 盛虎宜.生鲜电商物流配送的车辆路径问题研究[D].电子科技大学,2019.
[8] 鲍春玲,张世斌.考虑碳排放的冷链物流联合配送路径优化[J].工业工程与管理,2018,23(5):95-101.
[9] 范厚明,杨翔,李阳.基于生鲜品多中心联合配送的半开放式车辆路径问题[J].计算机集成制造系统,2019,25(1):256-266.
[10] Zhou L, Balldacci R, Vigo D, et al. A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution[J]. European Journal of Operational Research, 2018, 265: 765-778.
[11] 肖玉徽,楼振凯,戴晓震.带时间窗的多配送中心协同配送问题研究[J].数学的实践与认识,2018,48(14):171-177.
[12] 付朝晖,刘长石.生鲜电商配送的开放式时变车辆路径问题研究[J].计算机工程与应用,2021,57(1):271-278.
[13] Ichoua S, Gendreau M, Potvin J Y. Vehicle dispatching with time-dependent travel times[J]. European Journal of Operational Research, 2003, 144(2): 379-396.
[14] Xiao Y Y, Konak A. A genetic algorithm with exact dynamic programming for the green vehicle routing & scheduling problem[J]. International Journal of Production Economics, 2017, 167: 1450-1463.
[15] 李妍峰,高自友,李军.动态网络车辆路径派送问题研究[J].管理科学学报,2014,17(8):1-9.
[16] Hickman J, Hassel D, Joumard R, Samaras Z, Sorenson S. Methodology for calculating transport emissions and energy consumption[R]. Technical Report, Transport Research Laboratory, 1999.
[17] Naderipour M, Alinaghian M. Measurement, evaluation and minimization of CO₂, NO_x, and CO emissions in the open time dependent vehicle routing problem[J]. Measurement, 2016, 90: 443-452.
[18] Coe E. Average carbon dioxide emission resulting from gasoline and diesel fuel[R]. United States Environment Protection Agency, 2005.
[19] 游晓明,刘升,吕金秋.一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用[J].控制与决策,2017,32(3):552-556.
[20] Solomon M M. Algorithms for the vehicle routing problem with time windows constrains[J]. Operation Research, 1987, 35(2): 254-265.
[21] Shen L, Tao F M, Wang S Y. Multi-depot open vehicle routing problem with time windows based on carbon trading[J]. International Journal of Environment Research and Public Health, 2018, 15: 2025.

Open Vehicle Routing Problem Based on Joint Distribution Mode under Time-dependent Road Networks

时变路网条件下联合配送的开放式车辆路径问题

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 11

Recommended Articles

Metrics

[1]	WANG Xin, WANG Zheng, XU Wei. Vehicle and Drone Joint Distribution Routing Problem with Multiple Drone Hubs [J]. Operations Research and Management Science, 2021, 30(5): 31-37.
[2]	YU Xiao-hui, HE Ming-ke, ZHANG Qiang, PANG Jin-hui. Game Analysis of the “Last Kilometer”Joint Distribution Driven by the Block Chain [J]. Operations Research and Management Science, 2020, 29(1): 17-22.
[3]	ZHANG Jian-tong, YANG Wen-juan. The Optimization Based on Priority for a Mixed Arrival-Departure Aircraft Sequencing Problem [J]. Operations Research and Management Science, 2018, 27(6): 115-121.
[4]	WANG Shu-qin, HUANG Qian. Route Optimization Model of Military Orienteering and ItsSolution to a Hybrid Ant Colony Algorithm [J]. Operations Research and Management Science, 2018, 27(4): 105-111.
[5]	HAN Wen-min, CHEN Ting, GAO Long-long, LI Zheng-yi, WENG Hong-Bing. Virtual Cellular Rescheduling under Interference of Emergency Order [J]. Operations Research and Management Science, 2018, 27(2): 68-78.
[6]	LI Jie, ZHAO Xu-dong, WANG Yu-xia, CHU Chao-hsien. Integrated Optimization of Electric Vehicle Allocation & Routing forLarge Scale E-Commerce Terminal Logistics Distribution [J]. Operations Research and Management Science, 2018, 27(10): 23-30.
[7]	WANG Dao-ping, XU Zhan, YANG Cen. Study on Location-routing Problem of Logistics Distribution Based on Two-stage Heuristic Algorithm [J]. Operations Research and Management Science, 2017, 26(4): 70-75.
[8]	WU Nuan, WANG Nuo, LIU Zhong-bo, LU Yue. Ship Dredging Scheduling Optimization at Port Based on Human-computer Interactive Ant Colony Algorithm [J]. Operations Research and Management Science, 2017, 26(10): 34-41.
[9]	ZHANG Zong-yi, XING Wen-ting, WU Sheng-li. Residential Customer Time-of-use Natural Gas Pricing Model and Optimized Solving Method [J]. Operations Research and Management Science, 2016, 25(3): 26-31.
[10]	LI Jian-bin, ZHOU Wei, CHEN Feng. Applied Optimal Strategies for Warehouse Picking Routing in B2C [J]. Operations Research and Management Science, 2014, 23(1): 7-14.
[11]	CHEN Li-gang, LI Yi-jun, AI Wen-guo. Allocation of Advertising Slots for Portal Websites Using Combinatorial Auctions [J]. Operations Research and Management Science, 2011, 20(2): 108-116.