车辆路径规划问题的逆向优化方法

doi:10.16183/j.cnki.jsjtu.2020.210

摘要/Abstract

摘要：

在电商物流的“最后一公里”配送中,经验丰富的驾驶员(专家)并不总是基于最短路径成本矩阵进行路径规划.对此,提出一种逆向优化方法,通过学习专家的过往路径决策,得到能够代表专家经验的成本矩阵,并应用于路径规划模型求解,使得专家经验能够融入决策算法中.利用机器学习中的乘性权重更新算法实现对专家经验的学习.随机算例和电商实际算例的实验结果证明了方法的有效性.

关键词: 逆向优化, 车辆路径规划问题, 成本矩阵, 经验学习

Abstract:

Generally, experienced drivers or experts do not always follow the shortest path in the last mile delivery of e-commerce. Hence, an inverse optimization approach was proposed to obtain a proper cost matrix by learning from the experts’ past experience. Thus, the routing model with respect to the learned cost matrix could provide solutions as good as those given by experts. An algorithm-based multiplicative weights updates algorithm was applied to achieve the experience learning process. The experimental analyses based on the random and real-life instances demonstrate the effectiveness of this approach.

Key words: inverse optimization, vehicle routing problem(VRP), cost matrix, experience learning

中图分类号:

TP181

陈禹伊, 陈璐. 车辆路径规划问题的逆向优化方法[J]. 上海交通大学学报, 2022, 56(1): 81-88.

CHEN Yuyi, CHEN Lu. An Inverse Optimization Approach of Vehicle Routing Problem[J]. Journal of Shanghai Jiao Tong University, 2022, 56(1): 81-88.

图/表 6

表1

参数定义

符号	含义
C_true	代表专家经验的真实成本矩阵,是未知量
T	训练集中专家解的个数
μ	权重更新公式的学习率, 与参数T和n相关
C_t	第t轮的成本矩阵
X(p_t)	第t轮模型L的约束条件
$x t *$	第t轮的专家解
x_t	第t轮基于当前C_t得到的模型L最优解
w_t	第t轮的决策权重
P	代表专家经验的真实决策概率
P_t	第t轮的决策概率,形式上为归一化后的w_t
m_t	第t轮的损失成本

表1

图1

表2

MWU算法求解不同规模算例的结果

$H$	ε₁/%	ε₂	E	S/%	CPU/s
10	0.04	1.27	0.79	90.27	9460.87
15	0.32	4.25	1.14	91.29	16528.59
19	0.20	0.20	1.09	93.61	25344.56
21	0.24	1.02	2.06	89.17	27636.93
25	0.14	1.11	2.98	87.06	128741.12
34	0.08	3.26	3.57	88.86	89862.27
45	0.14	0.04	7.66	82.20	215451.29
56	0.12	0.03	10.02	81.96	345601.23
均值	0.16	1.40	3.66	88.05	107328.36

表2

图2

图3

表3

真实算例结果对比

算例	$H$	E	S/%	CPU/s
基于C₁求解	56	17.95	57.62	-
基于C_T求解	56	11.24	71.84	40128.13
优化效果	-	37.38	24.67	-

表3

参考文献 25

[1]	范厚明, 徐振林, 李阳, 等. 混合遗传算法求解多中心联合配送路径问题[J]. 上海交通大学学报, 2019, 53(8):1000-1009.
	FAN Houming, XU Zhenlin, LI Yang, et al. Hybrid genetic algorithm for solving multi-depot joint distribution routing problem[J]. Journal of Shanghai Jiao Tong University, 2019, 53(8):1000-1009.
[2]	熊浩, 鄢慧丽, 周和平, 等. 多阶段动态车辆路径问题实时优化策略[J]. 上海交通大学学报, 2013, 47(3):450-453.
	XIONG Hao, YAN Huili, ZHOU Heping, et al. Real-time optimization strategy of the multi-period dynamic vehicle routing problems[J]. Journal of Shanghai Jiao Tong University, 2013, 47(3):450-453.
[3]	BERTSIMAS D, GUPTA V, PASCHALIDIS I C. Data-driven estimation in equilibrium using inverse optimization[J]. Mathematical Programming, 2015, 153(2):595-633. doi: 10.1007/s10107-014-0819-4 URL
[4]	KOVACS A A, GOLDEN B L, HARTL R F, et al. Vehicle routing problems in which consistency considerations are important: A survey[J]. Networks, 2014, 64(3):192-213. doi: 10.1002/net.v64.3 URL
[5]	SMILOWITZ K, NOWAK M, JIANG T T. Workforce management in periodic delivery operations[J]. Transportation Science, 2013, 47(2):214-230. doi: 10.1287/trsc.1120.0407 URL
[6]	HAUGHTON M A. The efficacy of exclusive territory assignments to delivery vehicle drivers[J]. European Journal of Operational Research, 2008, 184(1):24-38. doi: 10.1016/j.ejor.2006.10.014 URL
[7]	ZHONG H S, HALL R W, DESSOUKY M. Territory planning and vehicle dispatching with driver learning[J]. Transportation Science, 2007, 41(1):74-89. doi: 10.1287/trsc.1060.0167 URL
[8]	LIU L, ANDRIS C, RATTI C. Uncovering cabdrivers’ behavior patterns from their digital traces[J]. Computers, Environment and Urban Systems, 2010, 34(6):541-548. doi: 10.1016/j.compenvurbsys.2010.07.004 URL
[9]	韦增欣, 陈进来, 罗朝晖. 基于驾驶员偏好的最优路径选择[J]. 交通运输系统工程与信息, 2010, 10(6):141-144.
	WEI Zengxin, CHEN Jinlai, LUO Chaohui. Optimal path selection based on driver’s preference[J]. Journal of Transportation Systems Engineering and Information Technology, 2010, 10(6):141-144.
[10]	PAHLAVANI P, DELAVAR M R. Multi-criteria route planning based on a driver’s preferences in multi-criteria route selection[J]. Transportation Research Part C: Emerging Technologies, 2014, 40:14-35. doi: 10.1016/j.trc.2014.01.001 URL
[11]	HE Z C, CHEN K Y, CHEN X Y. A collaborative method for route discovery using taxi drivers’ experience and preferences[J]. IEEE Transactions on Intelligent Transportation Systems, 2018, 19(8):2505-2514. doi: 10.1109/TITS.2017.2753468 URL
[12]	黄敏, 毛锋, 钱宇翔. 基于出租车司机经验的约束深度强化学习算法路径挖掘[J]. 计算机应用研究, 2020, 37(5):1298-1302.
	HUANG Min, MAO Feng, QIAN Yuxiang. Mining fastest route using taxi drivers’ experience via constrained deep reinforcement learning[J]. Application Research of Computers, 2020, 37(5):1298-1302.
[13]	AHUJA R K, ORLIN J B. Combinatorial algorithms for inverse network flow problems[J]. Networks, 2002, 40(4):181-187. doi: 10.1002/(ISSN)1097-0037 URL
[14]	AHUJA R K, ORLIN J B. Inverse optimization[J]. Operations Research, 2001, 49(5):771-783. doi: 10.1287/opre.49.5.771.10607 URL
[15]	ZHANG J Z, LIU Z H. Calculating some inverse linear programming problems[J]. Journal of Computational and Applied Mathematics, 1996, 72(2):261-273. doi: 10.1016/0377-0427(95)00277-4 URL
[16]	ZHANG J Z, LIU Z H. A general model of some inverse combinatorial optimization problems and its solution method under l_∞ norm[J]. Journal of Combinatorial Optimization, 2002, 6(2):207-227. doi: 10.1023/A:1013807829021 URL
[17]	HEUBERGER C. Inverse combinatorial optimization: A survey on problems, methods, and results[J]. Journal of Combinatorial Optimization, 2004, 8(3):329-361. doi: 10.1023/B:JOCO.0000038914.26975.9b URL
[18]	YOU S I, CHOW J Y J, RITCHIE S G. Inverse vehicle routing for activity-based urban freight forecast modeling and city logistics[J]. Transportmetrica A: Transport Science, 2016, 12(7):650-673. doi: 10.1080/23249935.2016.1189723 URL
[19]	牟健慧, 郭前建, 高亮, 等. 基于混合的多目标遗传算法的多目标流水车间逆调度问题求解方法[J]. 机械工程学报, 2016, 52(22):186-197.
	MOU Jianhui, GUO Qianjian, GAO Liang, et al. Multi-objective genetic algorithm for solving multi-objective flow-shop inverse scheduling problems[J]. Journal of Mechanical Engineering, 2016, 52(22):186-197.
[20]	BÄRMANN A, MARTIN A, POKUTTA S, et al. An online-learning approach to inverse optimization[DB/OL]. (2020-03-29)[2020-07-08]. https://arxiv.org/abs/1810.12997v2.
[21]	ASWANI A, SHEN Z J M, SIDDIQ A. Inverse optimization with noisy data[J]. Operations Research, 2018, 66(3):870-892. doi: 10.1287/opre.2017.1705 URL
[22]	CHAN T C Y, LEE T, TEREKHOV D. Inverse optimization: Closed-form solutions, geometry, and goodness of fit[J]. Management Science, 2019, 65(3):1115-1135. doi: 10.1287/mnsc.2017.2992 URL
[23]	SAEZ-GALLEGO J, MORALES J M. Short-term forecasting of price-responsive loads using inverse optimization[J]. IEEE Transactions on Smart Grid, 2018, 9(5):4805-4814. doi: 10.1109/TSG.5165411 URL
[24]	ARORA S, HAZAN E, KALE S. Fast algorithms for approximate semidefinite programming using the multiplicative weights update method[C]// 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05). Pittsburgh, USA: IEEE, 2005: 339-348.
[25]	ARORA S, HAZAN E, KALE S. The multiplicative weights update method: A meta-algorithm and applications[J]. Theory of Computing, 2012, 8(1):121-164. doi: 10.4086/toc URL