Optimal Solutions for the Moving Target Vehicle Routing Problem via Branch-and-Price with Relaxed Continuity
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Optimal Solutions for the Moving Target Vehicle Routing Problem with Obstacles via Lazy Branch and Price
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 must be vis…
Motion PlanningAn Attention-LSTM Hybrid Model for the Coordinated Routing of Multiple Vehicles
Reinforcement learning has recently shown promise in learning quality solutions in a number of combinatorial optimization problems. In particular, the attention-based encoder-decoder models show high effectiveness on var…
Combinatorial OptimizationComputational EfficiencyDecoderTraveling Salesman ProblemA Multi-Objective approach to the Electric Vehicle Routing Problem
The electric vehicle routing problem (EVRP) has garnered great interest from researchers and industrialists in an attempt to move from fuel-based vehicles to healthier and more efficient electric vehicles (EVs). While it…
Learning to Deliver: a Foundation Model for the Montreal Capacitated Vehicle Routing Problem
In this paper, we present the Foundation Model for the Montreal Capacitated Vehicle Routing Problem (FM-MCVRP), a novel Deep Learning (DL) model that approximates high-quality solutions to a variant of the Capacitated Ve…
Language ModellingLarge Language ModelA Deep Reinforcement Learning Approach for Solving the Traveling Salesman Problem with Drone
Reinforcement learning has recently shown promise in learning quality solutions in many combinatorial optimization problems. In particular, the attention-based encoder-decoder models show high effectiveness on various ro…
Combinatorial OptimizationComputational EfficiencyDecoderDeep Reinforcement Learning+3