1 Introduction
Ajay et al. [1] considered the following problem: given a set of curves, find a maximum subset such that, for any two distinct , there is no time when . Though there are some approximation algorithms, it is shown that most versions of these problems are NPhard. This is true even when the curves are samesized Lshapes and trajectories have the same constant speed. During a talk by Sasanka Roy on this problem at Stony Brook University, Joseph S. B. Mitchell and Esther M. Arkin posed the following variation: given where is a continuous function, we wish to assign delays so that, for any two distinct , there is no time when ; we also wish that the maximum delay is minimized.
Automated guided vehicles (AGVs) and automated vehicle routing are currently some of the most prolific fields in the domain of motor vehicle technology, enjoying a large body of research addressing a large number of related algorithmic and optimization problems. The field of automated guided vehicles has a long and rich history and is closely related to our work. For an elaborate review, the reader is referred to a survey by Vis [15], though [3] is a more recent one. A central topic in this field is collision avoidance. Kim and Tanchoco [5] propose an algorithm based on Dijkstra’s that facilitates conflictfree routing of AGVs. It runs in time, where is the number of vehicles and is the number of nodes, i.e., path intersections. Arora et al. [14]
used techniques based on game theory to design a methodology for AGV traffic control. Yan et al.
[16] studied collisionfree routing of AGVs on both unidirectional and bidirectional paths using digraphs. For more information on conflictfree routing of AGVs, the reader is referred to [6, 9, 7]. For an elaborate survey on routing and scheduling algorithms for AGVs, see [8]. Other related work in this area includes the study of One Way Road Networks (OWRNs) by Ajaykumar et al. [4], its motivation [12] and [10, 2, 13].1.1 New Results
In this paper, we study a simple vehicle scheduling problem in which, many times, we are guaranteed schedules with at most a constant delay. We consider trains of fixed length that move at constant speed and sets of train lines (tracks), each of which consisting of an axisparallel linesegment with endpoints in the integer lattice and of a direction of movement (towards or ). For an example see Figure 1. 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 and any given (Theorem 3.2) and also for and (Theorem 3.3). Through clique searching, we are also able to show that several of these upper bounds are tight (Section 4). In Appendix, we provide a Python code that we have used for clique searching, and the results are summarized in Table 1.
2 Preliminaries
Definition 2.1.
A (dimensional) train line consists of:

A track, which is a line segment in with distinct endpoints distinguished between a departure point and an arrival point;

A train length, which is a positive real number; and

A speed, which is also a positive real number.
Furthermore, a set of train lines with nonoverlapping (but possibly crossing) tracks is called a train network.
Definition 2.2.
For a set of real numbers and a real number , we denote by .
Definition 2.3.
A (collisionfree) schedule for a train network is an assignment of a delay, which is a nonnegative real number, to each of its lines. It also must result in no collisions between the trains. More precisely, for any two lines whose tracks cross, the open intervals and must not intersect, where:

and are the respective delays assigned to the lines;

and are the respective distances between the departure points of the lines and the crossing point;

and are the respective train lengths of the lines; and

and are the respective speeds of the lines.
The delay of the schedule is the maximum delay it assigns. An integer schedule is one that only assigns integer delays.
An alternative way to understand schedules is to imagine each line’s train starts “underground” with the front at the departure point and moves towards the arrival point at the line’s speed, where it moves “underground” again (“underground” trains cannot collide with other trains); see Figure 2. A delay assignment is then a schedule if, and only if, the line segments that correspond to the “aboveground” parts of these trains never cross. For an example, see Figure 3.
Definition 2.4.
A dimensional train network is regular if all its lines’ speeds are , all its train lengths are the same and integer, all its tracks are axisparallel and all its departure and arrival points are in .
Theorem 2.5.
All regular train networks admit an integer schedule of minimum delay (among all schedules, integer or otherwise).
Proof.
It is enough to show that, for an arbitrary schedule, assigning to each line a delay equal to the floor of the original delay will not result in any collisions. Indeed, take two lines whose tracks cross and define , , , , , , and as in Definition 2.3. We thus have and . The original schedule ensures that
which is equivalent to
Because and differ by less than , is either or . Therefore, since and are integers, the open interval cannot intersect , which implies our delay assignment is collisionfree. ∎
Definition 2.6.
Consider a train line with an axisparallel track that departs from and arrives at , where is the
th vector of the canonical basis of
() and . The axis of the line is the number . Furthermore, we say this line is positive if and negative if , with its sign being or , respectively.Definition 2.7.
For any modulus , we extend the modulo function to real numbers as follows: if , then . Furthermore, for a set , we denote by .
3 Results
Theorem 3.1.
Any regular dimensional train network with trains of length and only positive lines has a schedule with delay at most .
Proof.
Assign delay to lines departing from with axis . Consider then a crossing between a line departing from with axis and another line departing from with axis . In the notation of Definition 2.3, we have:

;

;

; and

.
Thus, modulo ,
since, for axes , we have from the fact that the lines cross. However, there cannot be an intersection between and because . Therefore, and there are no collisions. ∎
Theorem 3.2.
Any regular 2dimensional train network with trains of length has a schedule with delay at most , where
Proof.
Assign delay
to lines departing from with axis and sign . Consider then a horizontal line departing from with sign that crosses a vertical line departing from with sign . In the notation of Definition 2.3, we have:

;

;

; and

.
Note that and so it is enough to show that
Indeed, then does not intersect , which implies , i.e., a lack of collisions. We prove this by cases starting when , which gives us, modulo ,
Because , we have that
In case and , we have, modulo ,
Because and are multiples of , we must have that
is an odd multiple of
. Moreover, since is an even multiple of , must indeed be in .To complete the remaining two cases, note that if and were simultaneously multiplied by , so would be . However, is closed under negation modulo . ∎
Theorem 3.3.
Any regular 3dimensional train network with trains of length has a schedule with delay at most .
Proof.
We delay each line by the only integer in that is equivalent to modulo and equivalent to modulo 2, where is its departure point, is its axis and is its sign (the existence and uniqueness of this integer is assured by the Chinese Remainder Theorem).
Consider then two crossing lines that:

Depart respectively from and ;

Have respective signs ; and

Have and as their respective axes (axis arithmetic is done modulo ).
Thus, in the notation of Definition 2.3, we have and . Modulo , we also have and . Therefore, in case , also modulo ,
However, since the lines cross, and, since and , it must be that modulo , so . The collision avoidance condition for these lines is and must be true since but .
On the other hand, if , then note that, modulo ,
and
Therefore, again modulo ,
as, once more, . As before, but
which is either or . No collisions are therefore possible. ∎
4 Clique Searching and Lower Bounds
Whether a train network admits an integer schedule with delay at most can be decided with a clique search: create a graph containing a vertex for each line and time ; for every pair of distinct lines and and for each pair of times which would not result in a collision if assigned as delays respectively to and , put an edge between and . Note that if and do not cross, then is an edge for all . Note also that an integer schedule with delay at most exists if, and only if, has a clique with as many vertices as there are lines. This is because two vertices associated with the same line cannot be selected and we encoded potential collisions in the edges between vertices associated with different lines. So, essentially, the clique is a delay assignment.
Due to Theorem 2.5, we can decide whether a regular train network has a schedule with delay at most a given number . We have implemented this algorithm with the Cliquer clique solver [11] and recorded some lower bounds for regular train networks in Table 1.
Delay  Tight?  Figure  

2  Theorem 3.1  4a  
2  1  1  Theorem 3.2  4a  
2  2  7  Theorem 3.2  4b  
3  1  2  Theorem 3.1  4c 
For greater exposition we will walk through a simple example of determining the lower bounds for a train network with only positive lines and a train length of . Referring to Theorem 3.1 we see that a delay of is possible. Therefore we will test a train network using the configuration in Figure 4a and a delay of . If we construct a graph as outlined above and cannot find a clique of size , then our configuration does not admit a network with a delay of , and by Theorem 3.1 and Theorem 2.5 our lower bound on the delay must then be . Although not necessary to our lower bound proof, for completeness we also show a graph built using a delay of and illustrate a clique of size , which represents an assignment of delays that would result in no collisions.
We will express our train network in the following format:^{1}^{1}1This input format is a more readable version of the input we used to run our Python script, which built the graph in Cliquer readable format, and for which we refer the reader to the appendix.
<label> <train_len> <axis><direction> <x> <y> <z>
where:
<label>  is the line’s label; 

<train_len>  is the line’s train length, 
a positive integer;  
<axis>  is the axis the track is 
parallel to (“x”, “y”, or “z”);  
<direction>  is the line’s direction of 
movement (“” or “+”);  
<x> <y> <z>  are the line’s departure 
point. 
Our train network in the above format based on the configuration of Figure 4a and illustrated in Figure 4(a), is then:
A 2 x+ 0 1 0
B 2 x+ 0 2 0
C 2 y+ 1 0 0
D 2 y+ 2 0 0
We will refer to the above train network as Network 1. We create a vertex for each combination of line and possible delay, then for each pair of vertices consisting of distinct lines, we connect them with an edge if the delay assignment does not result in a collision. See Figure 4(b). We may then search this graph for cliques of size , the number of train lines. To facilitate this search, we built our graph using a Python script, and fed the output into the Cliquer clique solver [11]. Figure 6 shows the graph resulting from Network 1 with a maximum delay of , and the resulting clique which gives a delay assignment that will not result in any collisions.
5 Open Problems
The main problem that remains open is whether, for values of , every threedimensional regular train network with trains of length admits a schedule with delay bounded by a constant. However, we are also interested in extending the lower bounds in Table 1 to more values of .
Acknowledgements
We would like to thank Joseph S. B. Mitchell, Esther M. Arkin, Sándor Fekete and members of the Computational Geometry group at Carleton University.
References
 [1] Ajay, Jammigumpula and Jana, Satyabrata and Roy, Sasanka Collisionfree routing problem with restricted Lpath. Discrete Applied Mathematics, 2021
 [2] Dasler, Philip and Mount, David M. On the complexity of an unregulated traffic crossing. Algorithms and Data Structures, Lecture Notes in Computer Science, vol. 9214, Springer, pages 224–235, 2015.
 [3] Hyla, P. and Szpytko, J. Automated guided vehicles: the survey. Journal of KONES, 24, 2017.
 [4] Ajaykumar, Jammigumpula and Das, Avinandan and Saikia, Navaneeta and Karmakar, Arindam Problems on one way road networks. Proceedings of the 28th Canadian Conference on Computational Geometry, pages 303–308, 2016.
 [5] Kim, Chang W. and Tanchoco, J. M. A. Conflictfree shortesttime bidirectional AGV routing. The International Journal of Production Research, 29(12):2377–2391, 1991.
 [6] Koff, Gary A. Automatic guided vehicle systems: applications, controls and planning. Material flow, 4(1–2):3–16, 1987.
 [7] Zeng, Laiguang and Wang, HsuPin (Ben) and Jin, Song Conflict detection of automated guided vehicles: a Petri net approach. The International Journal of Production Research, 29(5):866–879, 1991.
 [8] Qiu, Ling and Hsu, WenJing and Huang, ShellYing and Wang, Han Scheduling and routing algorithms for AGVs: a survey. The International Journal of Production Research, 40(3):745–760, 2002.
 [9] Malmborg, Charles J. A model for the design of zone control automated guided vehicle systems. The International Journal of Production Research, 28(10):1741–1758, 1990.
 [10] Kakikura, Masayoshi and Takeno, Jun Ichi and Mukaidono, Masao A tour optimization problem in a road network with oneway paths. IEEJ Transactions on Electronics, Information and Systems, 98(8):257–264, 1978.
 [11] Niskanen, Sampo and Östergård, Patric R. J. Cliquer user’s guide, version 1.0. Communications Laboratory, Helsinki University of Technology, Espoo, Finland, Technical Report T48, 2003.
 [12] Robbins, Herbert Ellis A theorem on graphs, with an application to a problem of traffic control. The American Mathematical Monthly, 46(5):281–283, 1939.
 [13] Scheffer, Christian Train scheduling hardness and algorithms. The 13th International Conference and Workshop on Algorithms and Computation, Lecture Notes in Computer Science, vol. 12049, Springer, pages 342–347, 2020.
 [14] Arora, Sudha and Raina, A. K. and Mittal, A. K. Collision avoidance among AGVs at junctions. Intelligent Vehicles Symposium, 2000.
 [15] Vis, Iris F. A. Survey of research in the design and control of automated guided vehicle systems. European Journal of Operational Research, 170(3):677–709, 2006.
 [16] Yan, Xuejun and Zhang, Canrong and Qi, Mingyao MultiAGVs collisionavoidance and deadlockcontrol for itemtohuman automated warehouse. Industrial Engineering, Management Science and Application (ICIMSA), pages 1–5, 2017.
Appendix
We share our implementation, in Python 3, of a program to convert a train
network with a parameter into a graph that has a clique
with as many vertices as the network has lines if, and only if, there is an
integer schedule for the network with delay at most . If the script were saved as, for example, trains.py, then a call to:
./trains.py <D>
where <D> is the parameter would initiate the script. Network 1 from Section 4 would then be input from the command line as:
2 x+ 0 1 0
2 x+ 0 2 0
2 y+ 1 0 0
2 y+ 2 0 0
The output from this script is meant to be piped into (or read from a file) the cliquer. We will give a brief overview of the format, but for more details we refer the reader to the Cliquer clique solver [11] technical report. The first line of output would be:
p graph <V> 0
The character p indicates to the cliquer that this is the format line. The graph entry indicates the format, but it is there for consistency with older formats and is ignored by the cliquer. The <V> field is the number of vertices in the output graph. The 0 field indicates the number of edges, but the cliquer ignores this number as well, and determines the number of edges from the input. Each edge of the resulting graph would then be output on a separate line consisting of:
e <> <>
where and are integers representing a vertex. The above output should be piped into the cliquer, which would output the largest clique found and the vertices contained therein. The line number (starting with line ) and delay assignment from a vertex on a network with lines total could be obtained with the following formulas:
Line number:  div . 

Delay assignment:  mod . 
Our Python script, given below, operates from the command line but could be easily modified to read from and write to text files.
#!/usr/bin/env python3 import sys import itertools # Standard input: one train line per input line, each in the form # <train_len> <axis><dir> <x> <y> <z> # where: # * <train_len> is the line’s train length, a positive integer; # * <axis> is the axis the track is parallel to ("x", "y", or "z"); # * <dir> is the line’s direction of movement ("" or "+"); and # * <x>, <y> and <z> are the line’s departure point. # # Command line argument: a nonnegative integer D. # # Output: a graph in a Cliquercompatible format that has a clique of size # equal to the number of train lines (or input lines) if, and only if, the # lines form a network that has an integer schedule with delay at most D. class TrainLine: # train_len: a positive integer, the line’s train length # start: a 3d point, the line’s departure point # axis: the number of the axis the track is parallel to (0, 1 or 2) # dir: the line’s direction of movement (1 or 1) def __init__(l, train_len, start, axis, dir): l.train_len = train_len l.start = start l.axis = axis l.dir = dir # l[i] is the departure point’s ith coordinate (i is 0, 1 or 2) def __getitem__(l, i): return l.start[i] # Whether two line’s tracks overlap def overlaps(l0, l1): if l0.axis != l1.axis: return False a = l0.axis if l0[(a+1)%3] != l1[(a+1)%3] or l0[(a+2)%3] != l1[(a+2)%3]: return False return l0.dir == l1.dir or l0[a]*l0.dir < l1[a]*l0.dir # Input: two train lines with nonoverlapping tracks. # Output: None if the line’s tracks do not cross and a pair with the # respective distances from the line’s departure points to the # crossing point otherwise. def distances_to_crossing(l0, l1): other_axis = 0 while other_axis == l0.axis or other_axis == l1.axis: other_axis+= 1 if l0[other_axis] != l1[other_axis]: return None if l0[l1.axis]*l1.dir <= l1[l1.axis]*l1.dir: return None if l1[l0.axis]*l0.dir <= l0[l0.axis]*l0.dir: return None return ( (l1[l0.axis]l0[l0.axis])*l0.dir, (l0[l1.axis]l1[l1.axis])*l1.dir ) # Reads a train line from a text line @staticmethod def read(text_line): tokens = text_line.split() train_len = int(tokens[0]) axis = {"x": 0, "y": 1, "z": 2}[tokens[1][0]] dir = {"": 1, "+": 1}[tokens[1][1]] start = tuple(map(int, tokens[2:5])) return TrainLine(train_len, start, axis, dir) # Whether two open intervals intersect def intervals_overlap(I0, I1): (a0, b0) = I0 (a1, b1) = I1 return a0 < b1 and a1 < b0 # Command line argument D = int(sys.argv[1]) # Read standard input into a list of train lines L = [TrainLine.read(input_line) for input_line in sys.stdin.readlines()] # Check input tracks are nonoverlapping for l0, l1 in itertools.combinations(L, 2): if l0.overlaps(l1): raise Exception("Input contains overlapping tracks") # Assign vertices to lines for i in range(len(L)): L[i].vertices = range((D+1)*i, (D+1)*(i+1)) # Print the graph print("p graph %d 0" % ((D+1)*len(L))) for l0, l1 in itertools.combinations(L, 2): ds = l0.distances_to_crossing(l1) if ds is not None: d0, d1 = ds for t0, t1 in itertools.product(range(D+1), repeat=2): if ds is None or not intervals_overlap( (t0 + d0, t0 + d0 + l0.train_len), (t1 + d1, t1 + d1 + l1.train_len) ): print("e %d %d" % (l0.vertices[t0]+1, l1.vertices[t1]+1))
Comments
There are no comments yet.