Constant delay lattice train schedules

DOI10.1016/J.DAM.2023.06.016MaRDI QIDQ6064831zbMATH OpenOpenAlexFDO

Authors Jean-Lou De Carufel, Darryl Hill, Anil Maheshwari, Sasanka Roy, Luís Fernando Schultz Xavier da Silveira

Publication date 11 December 2023

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2107.04657

zbMATH Keywords

clique searchingcollision-free routingschedulingscheduling with delays

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Traffic problems in operations research (90B20) Deterministic scheduling theory in operations research (90B35)

Abstract: The following geometric vehicle scheduling problem has been considered: given continuous curves $f_1,ldots,f_n:mathbbRightarrowmathbb{R}^2$, find non-negative delays $t_1,ldots,t_n$ minimizing $max{t}_1,ldots,t_n$ such that, for every distinct $i$ {and $j$} and every time $t$, $|f_j(t-t_j)-f_i(t-t_i)|>ell$, where~$ell$ is a given safety distance. We study a variant of this problem where we consider trains (rods) of fixed length $ell$ that move at constant speed and sets of train lines (tracks), each of which consisting of an axis-parallel line-segment with endpoints in the integer lattice $mathbb{Z}^d$ and of a direction of movement (towards $infty$ {or $-infty$}). We are interested in upper bounds on the maximum delay we need to introduce on any line to avoid collisions, but more specifically on universal upper bounds that apply no matter the set of train lines. We show small universal constant upper bounds for $d=2$ and any given $ell$ and also for $d=3$ and $ell=1$. Through clique searching, we are also able to show that several of these upper bounds are tight.

Recommendations

• Train scheduling: hardness and algorithms
• Train scheduling on a unidirectional path
• Fastest, average and quantile schedule
• The train frequency compatibility problem
• A railway scheduling problem

Cites work

• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• Collision-free routing problem with restricted L-path
• Conflict-free shortest-time bidirectional AGV routeing
• On the complexity of an unregulated traffic crossing
• Scheduling and routing algorithms for AGVs: A survey
• Survey of research in the design and control of automated guided vehicle systems
• Train scheduling: hardness and algorithms

This page was built for publication: Constant delay lattice train schedules

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6064831)