Organizations: Robotics Institute at Carnegie Mellon University, Pittsburgh, PA 15213 · Mechanical and Aerospace Engineering at Michigan Technological University, Houghton, MI 49931 · UM-SJTU Joint Institute and Department of Automation at Shanghai Jiao Tong University, Shanghai, China · Department of Mechanical Engineering and Department of Computer Science and Engineering at Texas A&M University, College Station, TX 77843
The Moving Target Vehicle Routing Problem (MT-VRP) seeks trajectories for several agents that intercept a set of moving targets, subject to speed, time window, and capacity constraints. We introduce an exact algorithm, Branch-and-Price with Relaxed Continuity (BPRC), for the MT-VRP. The main challenge in a branch-and-price approach for the MT-VRP is the pricing subproblem, which is complicated by moving targets and time-dependent travel costs between targets. Our key contribution is a new labeling algorithm that solves this subproblem by means of a novel dominance criterion tailored for problems with moving targets. Numerical results on instances with up to 25 targets show that our algorithm finds optimal solutions more than an order of magnitude faster than a baseline based on previous work, showing particular strength in scenarios with limited agent capacities.
Figures & tables
Figure 1: Targets move along piecewise-linear trajectories with time windows shown in bold lines. Two agents begin at the depot and collectively intercept all targets. Trajectories of agents are shown in blue.
Figure 2: Example where existing VRP dominance checks fail for the MT-VRP. Since each target has one time window in this example, we represent a target-window using the index of the target. We treat the depot as a fictitious target 0. (a) τa is an optimal (i.e. minimum-distance) trajectory visiting the sequence of targets Γ=(0,3,1,2) , and τa′ is an optimal trajectory visiting the sequence Γ′=(0,1,3,2) . 3 3 3 Agents in the MT-VRP can change their speed, which is why τa and τa′ can travel the same distance, even though τa meets target 2 later than τa′ : τa can simply arrive at its interception position, then stop and wait for target 2. Conventional VRP dominance checks would conclude that Γ dominates Γ′ , since τa and τa′ have the same cost. 4 4 4 While dominance checks technically compare reduced cost , which adds bias terms to the cost, the bias terms for Γ and Γ′ are equal in Fig. 4 (a), and the same goes for Γˉ and Γˉ′ in Fig. 4 (b). (b) τˉa optimally visits Γˉ=(0,3,1,2,4,0) obtained by appending 4 and 0 to Γ , and τˉa′ optimally visits Γˉ′=(0,1,3,2,4,0) , obtained by appending 4 and 0 to Γ′ . τˉa travels more distance than τˉa′ , so Γˉ is worse than Γˉ′ . Thus Γ does not dominate Γ′ .
Figure 3: (a) and (b) show two partial tours Γ and Γ′ ending with γ1,2 . We want to check if Γ dominates Γ′ . (c) We check dominance by comparing an upper-bounding trajectory τa,ub for Γ and a lower-bounding trajectory τa,lb′ for Γ′ , as described in Section 5.2 . (d) We strengthen our dominance check by dividing γ1,2 into segments and applying the check from (c) for each segment; an example is shown for the 5th segment of γ1,2 , denoted as ξ1,2,5 .
Algorithm 1 SolvePricingProblem( λ,B )
Figure 4: (a) Varying the number of targets. The gap in computation time between BPRC and the baseline and ablations widens as we increase the number of targets up to 20. The gap shrinks at 25 targets because BPRC reaches the time limit in 5 instances. We do not show a computation time for BPRC-ablate-dominance for 25 targets because it reached the memory limit in every instance. (b) Varying the capacity. BPRC shows advantage for small capacities. (c) %Gap (as defined in Experiment 2) of each method’s relaxation solution. BPRC’s relaxation has a smaller %Gap, and is thus tighter, in every instance. (d) Varying the number of agents. BPRC shows advantage when the number of agents is 3 or larger. (e) Varying the time window lengths. BPRC’s performance advantage widens as we increase time window length up to 50, then shrinks because BPRC reaches the time limit in many instances. (f) Varying the number of segments in BPRC. Horizontal and vertical axes are log-scaled. MICP’s min, median, and max are shown as flat lines without scatter points because the quantity being varied is specific to BPRC. We only show MICP’s computation time to indicate that BPRC has smaller median computation time for a wide range of parameter values.
The Moving Target Vehicle Routing Problem with Obstacles (MT-VRP-O) seeks trajectories for several agents that collectively intercept a set of moving targets. Each target has one or more time windows where it can be visited, and the agents must avoid static obstacles and satisfy speed and capacity constraints. Previously studied VRPs are often addressed using a framework called branch-and-price. This framework requires computing the cost for a single agent to visit a given sequence of target-time window pairings, for several candidate sequences. These sequences are called tours. Computing tour costs is more expensive in the MT-VRP-O than in previously studied VRPs due to the presence of both moving targets and static obstacles. Thus, we introduce a new exact algorithm, Lazy Branch-and-Price with Relaxed Continuity (Lazy BPRC), for the MT-VRP-O. The key idea in Lazy BPRC is to use cheap-to-compute lower bounds on tour costs where costs are traditionally used, and lazily update lower bounds to true costs. When computing a tour's true cost is needed, we do so by searching for a shortest path on a graph of convex sets, and we introduce a new heuristic to accelerate the search. We demonstrate that Lazy BPRC runs up to an order of magnitude faster than two ablations.
Anoop Bhat, Geordan Gutow, David Neiman +4
Robotics Institute at Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA 15213. · Mechanical and Aerospace Engineering at Michigan Technological University, Houghton, MI 49931 · Robotics and AI Institute, Cambridge, MA 02142. +2
The Moving-Target Traveling Salesman Problem (MT-TSP) seeks a minimum cost trajectory for an agent that departs from a static depot, visits a set of moving targets, each within one of their assigned time windows, and returns to the depot. In this article, we study the Moving-Target Traveling Salesman Problem with Moving Obstacles (MT-TSP-MO), a generalization of the MT-TSP where the agent trajectory must avoid moving obstacles. We present a Mixed-Integer Conic Programming (MICP) formulation that can be solved using off-the-shelf solvers, as well as a fast and scalable Two-Phase Bilevel Search (TPBS) algorithm that computes high-quality feasible solutions for the problem. We evaluate our approaches against an existing baseline algorithm on a broad range of problem instances with up to 40 targets and 40 obstacles. The results demonstrate that both the proposed methods significantly outperform the baseline with respect to success rates, solution costs, and computation time.
Allen George Philip, Anoop Bhat, Sivakumar Rathinam +1
Mechanical Engineering, Texas A&M University, College Station, TX 77843-3123 · Robotics Institute, Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA 15213, USA · Mechanical Engineering, and Computer Science and Engineering, Texas A&M University, College Station, TX 77843-3123
The problem of route optimization with realistic constraints is becoming extremely relevant in the face of global urban population growth. While we are aware of approaches that theoretically provide an exact optimal solution, their application becomes challenging as the problem size increases because of exponential complexity. We investigate the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) and compare solutions obtaining by exact solver SCIP with heuristic algorithms such as LKH, 2-OPT, 3-OPT, the ORTools framework, and the deep learning model JAMPR. We demonstrate that for problem of size 50 deep learning and classical heuristic solutions became close to SCIP exact solution but requires less time. Additionally for problems with size 100, SCIP exact methods around 13 times slower that neural and classical heuristics with the same route cost and on around 50% worse for the first feasible solution on the same time. To conduct experiments, we developed the Smart Routes platform for solving route optimization problems, which includes exact, heuristic, and deep learning models, and facilitates convenient integration of custom algorithms and datasets.
Andrew Soroka, German Mikhelson, Alexander Mescheryakov +1
Moscow State University, Faculty of Computational Mathematics and Cybernetics, Moscow · Space Research Institute of RAS, Moscow