期刊
INFORMS JOURNAL ON COMPUTING
卷 30, 期 3, 页码 554-569出版社
INFORMS
DOI: 10.1287/ijoc.2017.0800
关键词
vehicle routing; moving targets; Lagrangian decomposition; branch and price
资金
- NSERC [RGPIN-2017-03962, RGPIN-2017-04185]
This paper addresses a generalization of the vehicle routing problem in which the pick-up locations of the targets are nonstationary. We refer to this problem as the vehicle routing problem with floating targets and the main characteristic is that targets are allowed to move from their initial home locations while waiting for a vehicle. This problem models new applications in drone routing, ridesharing, and logistics where a vehicle agrees to meet another vehicle or a customer at a location that is away from the designated home location. We propose a Mixed Integer Second Order Cone Program (MISOCP) formulation for the problem, along with valid inequalities for strengthening the continuous relaxation. We further exploit the problem structure using a Lagrangian decomposition and propose an exact branch-and-price algorithm. Computational results on instances with varying characteristics are presented and the results are compared to the solution of the full problem using CPLEX. The proposed valid inequalities reduce the computational time of CPLEX by up to 30% on average while the proposed branch and price is capable of solving instances where CPLEX fails in finding the optimal solution within the imposed time limit.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据