The non-stop disjoint trajectories problem

Hoch B, Liers-Bergmann F, Neumann S, Zaragoza Martínez FJ (2024)

Publication Type: Journal article

Publication year: 2024

Journal

Discrete Optimization Elsevier

Book Volume: 52

Article Number: 100837

DOI: 10.1016/j.disopt.2024.100837

Abstract

Consider an undirected network with traversal times on its edges and a set of commodities with connection requests from sources to destinations and release dates. The non-stop disjoint trajectories problem is to find trajectories that fulfill all requests, such that the commodities never meet. In this extension to the NP-complete disjoint paths problem, trajectories must satisfy a non-stop condition, which disallows waiting at vertices or along arcs. This problem variant appears, for example, when disjoint aircraft trajectories shall be determined or in bufferless packet routing. We study the border of tractability for feasibility and optimization problems on three graph classes that are frequently used where space and time are discretized simultaneously: the path, the grid, and the mesh. We show that if all commodities have a common release date, feasibility can be decided in polynomial time on paths. For the unbounded mesh and unit-costs, we show how to construct optimal trajectories. In contrast, if commodities have individual release intervals and turns are forbidden, then even feasibility is NP-complete for the path. For the mesh and arbitrary edge costs, with individual release dates and turning abilities of commodities restricted to at most 90°, we show that optimization and approximation are not fixed-parameter tractable.

Authors with CRIS profile

Benno Hoch Professur für Optimization under Uncertainty & Data Analysis Frauke Liers-Bergmann Professur für Optimization under Uncertainty & Data Analysis

Involved external institutions

Fraunhofer-Institut für Integrierte Schaltungen (IIS) DE Germany (DE) Universidad Autónoma Metropolitana (UAM) MX Mexico (MX)

How to cite

APA:

Hoch, B., Liers-Bergmann, F., Neumann, S., & Zaragoza Martínez, F.J. (2024). The non-stop disjoint trajectories problem. Discrete Optimization, 52. https://doi.org/10.1016/j.disopt.2024.100837

MLA:

Hoch, Benno, et al. "The non-stop disjoint trajectories problem." Discrete Optimization 52 (2024).

BibTeX: Download