Two-Phase Bilevel Search for the Moving-Target Traveling Salesman Problem with Moving Obstacles
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Mixed-Integer Conic Program for the Moving-Target Traveling Salesman Problem based on a Graph of Convex Sets
This paper introduces a new formulation that finds the optimum for the Moving-Target Traveling Salesman Problem (MT-TSP), which seeks to find a shortest path for an agent, that starts at a depot, visits a set of moving t…
Traveling Salesman ProblemParallel, Asymptotically Optimal Algorithms for Moving Target Traveling Salesman Problems
The Moving Target Traveling Salesman Problem (MT-TSP) seeks a trajectory that intercepts several moving targets, within a particular time window for each target. When generic nonlinear target trajectories or kinematic co…
iMTSP: Solving Min-Max Multiple Traveling Salesman Problem with Imperative Learning
This paper considers a Min-Max Multiple Traveling Salesman Problem (MTSP), where the goal is to find a set of tours, one for each agent, to collectively visit all the cities while minimizing the length of the longest tou…
Bilevel OptimizationTraveling Salesman ProblemSAR Imaging of Moving Target based on Knowledge-aided Two-dimensional Autofocus
Due to uncertainty on target's motion, the range cell migration (RCM) and azimuth phase error (APE) of moving targets can't be completely compensated in synthetic aperture radar (SAR) processing. Therefore, moving target…
Computational Efficiencyparameter estimationDiscovering Traveling Companions using Autoencoders
With the wide adoption of mobile devices, today's location tracking systems such as satellites, cellular base stations and wireless access points are continuously producing tremendous amounts of location data of moving o…
Representation Learning