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

An Inverse Optimization Approach of Vehicle Routing Problem

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

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.