上海交通大学学报

上海交通大学学报 >

2022 , Vol. 56 >Issue 1: 81 - 88

DOI: https://doi.org/10.16183/j.cnki.jsjtu.2020.210

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

展开
  • 上海交通大学 机械与动力工程学院, 上海 200240
陈禹伊(1996-),女,重庆市人,硕士生,研究方向为路径规划.

收稿日期: 2020-07-08

  网络出版日期: 2022-01-21

基金资助

国家自然科学基金资助项目(51775347)

收起

An Inverse Optimization Approach of Vehicle Routing Problem

Expand
  • School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China

Received date: 2020-07-08

  Online published: 2022-01-21

Fold

摘要

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

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

本文引用格式

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

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

参考文献

[1] 范厚明, 徐振林, 李阳, 等. 混合遗传算法求解多中心联合配送路径问题[J]. 上海交通大学学报, 2019, 53(8):1000-1009.
[1] 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.
[2] 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.
[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.
[5] SMILOWITZ K, NOWAK M, JIANG T T. Workforce management in periodic delivery operations[J]. Transportation Science, 2013, 47(2):214-230.
[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.
[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.
[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.
[9] 韦增欣, 陈进来, 罗朝晖. 基于驾驶员偏好的最优路径选择[J]. 交通运输系统工程与信息, 2010, 10(6):141-144.
[9] 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.
[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.
[12] 黄敏, 毛锋, 钱宇翔. 基于出租车司机经验的约束深度强化学习算法路径挖掘[J]. 计算机应用研究, 2020, 37(5):1298-1302.
[12] 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.
[14] AHUJA R K, ORLIN J B. Inverse optimization[J]. Operations Research, 2001, 49(5):771-783.
[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.
[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.
[17] HEUBERGER C. Inverse combinatorial optimization: A survey on problems, methods, and results[J]. Journal of Combinatorial Optimization, 2004, 8(3):329-361.
[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.
[19] 牟健慧, 郭前建, 高亮, 等. 基于混合的多目标遗传算法的多目标流水车间逆调度问题求解方法[J]. 机械工程学报, 2016, 52(22):186-197.
[19] 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.
[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.
[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.
[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.
Options
文章导航

/

〈 〉