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

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

中国管理科学 ›› 2023, Vol. 31 ›› Issue (9): 214-221.doi: 10.16381/j.cnki.issn1003-207x.2021.0183cstr: 32146.14.j.cnki.issn1003-207x.2021.0183

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

吴腾宇¹(), 张景露², 余海燕³

^1.重庆邮电大学现代邮政学院，重庆 400065
^2.重庆邮电大学经济管理学院，重庆 400065
^3.重庆交通大学经济管理学院，重庆 400074

收稿日期:2021-01-25 修回日期:2021-08-22 出版日期:2023-09-15 发布日期:2023-09-19
通讯作者: 吴腾宇 E-mail:fly200205@163.com
基金资助:
国家自然科学基金资助项目(71702016);教育部人文社会科学研究项目(21YJC630138);重庆市技术创新与应用发展面上项目(2022TIAD-GPX0072);重庆市教育委员会科学技术研究项目(KJQN20200638)

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

Teng-yu WU¹(), Jing-lu ZHANG², Hai-yan YU³

^1.School of Mordern Post，Chongqing University of Posts and Telecommunications，Chongqing 400065，China
^2.School of Economics and Management，Chongqing University of Posts and Telecommunications，Chongqing 400065，China
^3.School of Economics and Management，Chongqing jiaotong University，Chongqing 400074，China

Received:2021-01-25 Revised:2021-08-22 Online:2023-09-15 Published:2023-09-19
Contact: Teng-yu WU E-mail:fly200205@163.com

摘要/Abstract

摘要：

即时配送物流形态随着外卖业的迅猛发展，配送时效和规模不断提高，使得配送骑手逆行、超速等违规现象激增。O2O外卖平台往往使用直线距离预估配送时间，但实际配送的城市商圈交通网络却具有非对称的结构，因此在该情形下的配送问题成为末端实时配送的重要研究问题。针对以上实际配送场景，提出非对称网络结构下的实时取送货路径优化问题。分析该问题的下界，针对需求点在特殊网络上设计JLNO算法，针对需求点在一般网络上设计JPI-rd算法和W&I算法，并进一步分析三个算法的竞争性能。使用数值仿真软件分析一般网络下的算法性能，发现非对称系数越大且配送网络结构越复杂时，JPI-rd算法更适用。结论可为O2O外卖平台的配送车辆提供不同场景下的合单配送策略和路径优化。

关键词: 非对称网络, 实时配送, 取送货, 在线算法, 旅行商问题

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

中图分类号:

C935

吴腾宇, 张景露, 余海燕. 非对称网络下的在线取送货路径优化问题[J]. 中国管理科学, 2023, 31(9): 214-221.

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.

图/表 4

表1

本文研究结果与已有研究结果对比"

	算法	上界	下界
在线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$

表1

表2

网络结构"

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

表2

图1

表3

最大非对称系数、网络结构和订单数量对目标值的影响"

实情	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

表3

参考文献 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]	王璇, 刘斌, 汤铃. 租赁设备在线更新问题及其竞争策略[J]. 中国管理科学, 2023, 31(9): 170-176.
[2]	郑梦, 代文强. 需求依赖于库存的易变质品在线采购问题研究[J]. 中国管理科学, 2022, 30(12): 26-37.
[3]	郑斐峰, 靳凯媛, 张娥, 刘明. 考虑订单类型的两台平行批处理机在线调度模型研究[J]. 中国管理科学, 2021, 29(5): 173-179.
[4]	徐东洋, 李昆鹏, 崔利刚, 田倩南. 供需未匹配的多车场多车型多货品可拆分取送货车辆路径问题[J]. 中国管理科学, 2021, 29(1): 127-137.
[5]	徐维军, 刘幼珠, 陈晓丽, 胡茂林, 高丽. 通胀市场下多设备租赁的在线策略分析[J]. 中国管理科学, 2016, 24(2): 69-75.
[6]	张桂清, 徐寅峰. 概率预期下在线报童问题的最小风险策略[J]. 中国管理科学, 2010, 18(6): 131-136.
[7]	李彦苍. 改进蚁群算法在海洋工程群项目资源调度中的应用[J]. 中国管理科学, 2007, 15(5): 83-87.
[8]	徐维军, 徐寅峰. 具有概率分布在线租赁问题策略研究[J]. 中国管理科学, 2005, (5): 33-38.

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

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

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 15

相关文章 8

Metrics

本文评价

推荐阅读 0