非对称网络下的在线取送货路径优化问题

doi:10.16381/j.cnki.issn1003-207x.2021.0183

Abstract

Abstract:

With the rapid development of takeaway industry， the time and scale of real-time distribution have been improved， which makes the traffic violations such as retrograde motion and overspeed increase sharply. The delivery time estimated through the straight-line distance by the platform， but the actual distribution network is asymmetric. Considering the above distribution situations， the real-time pick-up and delivery problem with the asymmetric network is proposed and analyzed with online algorithm. A competitive algorithm that matches the lower bound of the problem is designed， JLNO algorithm is presented for positive half-line metric space， JPI-rd algorithm and W&I algorithm are presented for general metric network， and the performance of three algorithms is further analyzed. A sensitivity analysis of various parameters indicates that the JPI-rd algorithm is more suitable when the asymmetry coefficient and the network are larger. The conclusion can provide delivery strategies and path optimization for delivery vehicles on O2O delivery platforms under different scenarios.

Key words: asymmetrical network, real-time delivery, pick-up and delivery, online algorithm, traveling salesman problem

CLC Number:

C935

Teng-yu WU,Jing-lu ZHANG,Hai-yan YU. The Real-time Pick-up and Delivery Problem with the Asymmetric Network[J]. Chinese Journal of Management Science, 2023, 31(9): 214-221.

Figures/Tables 4

	算法	上界	下界
在线ATSP 问题研究结果	Zealous算法	$2 + a$	$a$
在线ATSP 问题研究结果	Return home 算法	$1 + a + 1$	$a$
本文研究结果	W&I算法	$2 + a$	$a + 1$
本文研究结果	JPI-rd算法	$m a x ? {1 + (a + 1) β, 2}$	$a + 1$

网络	网络最大距离	网络平均距离
$d 1$	2.54	1.23
$d 2$	9.01	6.31

实情	W&I/offline		JPI-rd/offline		JPI-rd/W&I
实情	Mean	Std	Mean	Std	Mean	Std
$t 60 r 20 d 2 a 1.01$	1.26	0.08	1.22	0.28	0.98	0.27
$t 60 r 20 d 2 a 2$	1.41	0.14	1.26	0.29	0.9	0.22
$t 60 r 20 d 2 a 4$	1.67	0.25	1.3	0.22	0.79	0.16
$t 60 r 20 d 1 a 1.01$	1.05	0.03	1.29	0.34	1.23	0.33
$t 60 r 20 d 1 a 2$	1.07	0.05	1.21	0.27	1.14	0.27
$t 60 r 20 d 1 a 4$	1.12	0.05	1.4	0.44	1.25	0.39
$t 60 r 20 d 1 a 8$	1.23	0.12	1.33	0.38	1.09	0.35
$t 60 r 30 d 1 a 1.01$	1.06	0.04	1.37	0.36	1.28	0.35
$t 60 r 30 d 1 a 2$	1.09	0.04	1.32	0.33	1.21	0.33
$t 60 r 30 d 1 a 4$	1.18	0.06	1.3	0.35	1.1	0.3
$t 60 r 30 d 2 a 1.01$	1.49	0.15	1.26	0.17	0.86	0.13
$t 60 r 30 d 2 a 2$	1.68	0.17	1.29	0.2	0.77	0.16
$t 60 r 30 d 2 a 4$	2.13	0.24	1.44	0.29	0.68	0.15

References 15

1	Cacchiani V， Bolton C C， Toth P. Models and algorithms for the Traveling Salesman Problem with Time-dependent Service times［J］. European Journal of Operational Research， 2020， 283（3）： 825-843.
2	Ausiello G， Bonifaci V， Laura L. The on-line asymmetric traveling salesman problem［J］. Journal of Discrete Algorithms， 2008， 6（2）： 290-298.
3	Agarwal Y K， Venkateshan P. A new model for the asymmetric vehicle routing problem with simultaneous pickup and deliveries［J］. Operations Research Letters， 2020， 48（1）： 48-54.
4	Zhukova G N， Ul’yanov M V， Fomichev M I. A hybrid exact algorithm for the asymmetric traveling salesman problem： construction and a statistical study of computational efficiency［J］. Automation and Remote Control， 2019， 80（11）： 2054-2067.
5	Liu Yanchao. An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones［J］. Computers & Operations Research， 2019， 111（1）： 1-20.
6	Yildiz B， Savelsbergh M. Provably high-quality solutions for the meal delivery routing problem［J］. Transportation Science， 2019， 53（5）： 1213-1499.
7	张金良，李超. 碳排放影响下的动态配送车辆路径优化研究［J］. 中国管理科学， 2022，30（9）：184-194.
	Zhang Jinliang， Li Chao. Research on dynamic distribution vehicle route optimization under the influence of carbon emission［J］. Chinese Journal of Management Science， 2022， 30（9）：184-194.
8	葛显龙，温鹏哲，薛桂琴．基于需求预测的两级动态配送路径优化研究［J］.中国管理科学，2022，30（8）：210-220.
	Ge Xianlong， Wen Pengzhe， Xue Guiqin. Two-echelon dynamic vehicle routing problem with request forecasting［J］. Chinese Journal of Management Science， 2022，30（8）：210-220.
9	邱晗光，周继祥，龙跃. 顾客可选末端交付方式和时间窗的城市配送动态订单接受优化研究［J］. 中国管理科学， 2020， 28（8）： 114-126.
	Qiu Hanguang， Zhou Jixiang， Long Yue. Research on the dynamic acceptance in urban delivery considering customer choice of the last-mile delivery modes and times slots［J］. Chinese Journal of Management Science， 2020， 28（8）： 114-126.
10	王新玉，赵志明. 动态取送问题研究综述［J］. 系统工程理论与实践， 2021， 41（2）： 319-331.
	Wang Xinyu， Zhao Zhiming. Survey of the dynamic pickup and delivery problems［J］. System Engineering Theory and Practice， 2021， 41（2）： 319-331.
11	Ausiello G， Feuerstein E， Leonardi S， et al. Algorithms for the On-Line Travelling Salesman ［J］. Algorithmica， 2001， 29（4）： 560-581.
12	Jaillet P， Wagner M R. Online routing problems： value of advanced information as improved competitive ratios［J］. Transportation Science， 2006， 40（2）：200-210.
13	马军平，徐寅峰，吴腾宇. 转向限制网络中基于预知时间的快递车辆在线揽件路径选择研究［J］. 系统工程理论与实践， 2017， 37（9）： 2394-2402.
	Ma Junping， Xu Yinfeng， Wu Tengyu. Online routing of express pick-up vehicles with advanced information on the turn restriction network［J］. System Engineering Theory and Practice， 2017， 37（9）： 2394-2402.
14	Ascheuer N， Krumke S O， Rambau J. Online dial-a-ride problems： minimizing the completion time［C］//Proceeding of the 17th Annual Symp on Theoretical Aspects of Computer Science， Berlin， Springer， 2000：639-650.
15	吴腾宇，陈嘉俊，蹇洁，等. O2O模式下的配送车辆实时取送货路径选择问题［J］. 系统工程理论与实践， 2018， 38（11）： 2885-2891.
	Wu Tengyu， Chen Jiajun， Jianjie， et al. The online pick-up and delivery vehicle routing problem under O2O delivery［J］. System Engineering Theory and Practice， 2018， 38（11）： 2885-2891.

[1]	Xuan WANG,Bin LIU,Ling TANG. Competitive Strategy for Online Replacement Problem of Leasing Equipment [J]. Chinese Journal of Management Science, 2023, 31(9): 170-176.
[2]	ZHENG Meng, DAI Wen-qiang. Online Procurement Problem of Inventory-dependent Deteriorating Items [J]. Chinese Journal of Management Science, 2022, 30(12): 26-37.
[3]	ZHENG Fei-feng, JIN Kai-yuan, ZHANG E, LIU Ming. Online Two Parallel Batch Machines Scheduling with Order Types [J]. Chinese Journal of Management Science, 2021, 29(5): 173-179.
[4]	ZHANG Gui-qing, XU Yin-feng. The Minimal Risk Strategy of the Online Newsboy Problem Based on Probabilistic Forecast [J]. Chinese Journal of Management Science, 2010, 18(6): 131-136.
[5]	YU Ming-zhu, LI Jian-bin, LEI Dong. The Research of VRP with Pick-up and Delivery and a New Tabu Search Based on Insertion Method [J]. Chinese Journal of Management Science, 2010, 18(2): 89-95.
[6]	WANG Yang, DONG Yu-cheng, XU Yin-feng, XU Wei-jun. Competitive Analysis for the Online Multistage Leasing Problem [J]. Chinese Journal of Management Science, 2009, 17(3): 101-106.
[7]	XU Yin-feng, ZHANG Wei-guo, HU Mao-lin. Competitive Strategy Analysis for Online Leasing with Continuous Change of Purchasing Price and Renting Cost [J]. Chinese Journal of Management Science, 2006, (2): 94-99.
[8]	LIU Xin-bao, YE Qiang, LIU Lin, YANG Shan-lin. Branching Ant Colony with Dynamic Perturbation Algorithm for Solving TSPs [J]. Chinese Journal of Management Science, 2005, (6): 57-63.
[9]	XU Wei-jun, XU Yin-feng. Strategy Research for Online Leasing Problem with Probability Distribution [J]. Chinese Journal of Management Science, 2005, (5): 33-38.

The Real-time Pick-up and Delivery Problem with the Asymmetric Network

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 4

References 15

Related Articles 9

Metrics

Comments

Recommended 0