We address a generalization of the Vehicle Routing Problem (VRP) which consists of intercepting moving targets with a fleet of vehicles in order to bring them to a common destination in shortest time. The targets are allowed to move from their initial known locations according to a predictable motion. We classify this problem as the Interceptor VRP. The Interceptor VRP may have applications in ride-sharing systems in which moving passengers are picked up by cars and in target tracking problems.
We propose a novel Mixed Integer Second Order Conic Programming (MISOCP) formulation for the problem, along with valid inequalities for strengthening the relaxation. To solve the MISOCP problem to optimality, we design and implement a Branch and Price algorithm. Computational results are presented by comparing CPLEX to the proposed new algorithm. The Branch and Price is significantly more computationally efficient than CPLEX on the tested instances.
| Subject : | : | Abstracts |
| Topics | : | Dynamic vehicle routing |
| Topics | : | Exact methods |
| Topics | : | TSP variants |
| PDF version | : |  PDF version |
