上海交通大学学报 ›› 2022, Vol. 56 ›› Issue (1): 81-88.doi: 10.16183/j.cnki.jsjtu.2020.210

• • 上一篇    下一篇

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

陈禹伊, 陈璐()   

  1. 上海交通大学 机械与动力工程学院, 上海 200240
  • 收稿日期:2020-07-08 出版日期:2022-01-28 发布日期:2022-01-21
  • 通讯作者: 陈璐 E-mail:chenlu@sjtu.edu.cn
  • 作者简介:陈禹伊(1996-),女,重庆市人,硕士生,研究方向为路径规划.
  • 基金资助:
    国家自然科学基金资助项目(51775347)

An Inverse Optimization Approach of Vehicle Routing Problem

CHEN Yuyi, CHEN Lu()   

  1. School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China
  • Received:2020-07-08 Online:2022-01-28 Published:2022-01-21
  • Contact: CHEN Lu E-mail:chenlu@sjtu.edu.cn

摘要:

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

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

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

中图分类号: