15th October 2020, 44 min read

Online Dial-A-Ride

Original post is here eklausmeier.goip.de/blog/2020/10-15-online-dial-a-ride.

• Introduction
• 1. Preliminaries
• 2. State of the art
• 3. Algorithms
• 3.1 Algorithm: ABORT
  • 3.1.1 ABORT for open online Dial-a-Ride
  • 3.1.2 ABORT for closed online Dial-a-Ride
• 3.2 Algorithm: ABORT-AND-WAIT (AAW)
  • 3.2.1 AAW for closed online Dial-a-Ride
  • 3.2.2 AAW for open online Dial-a-Ride
• 3.3 Algorithm: ABORT-OR-REPLAN (AOR)
  • 3.3.1 AOR for closed online Dial-a-Ride on the halfline ($c=\infty$)
• 4. Literature

Introduction

We consider the online Dial-a-Ride Problem where objects are to be transported between points in a metric space in the shortest possible completion time. In contrast to the offline case, these transportation requests arrive over time and can only be served after they are released.

One main way to measure the quality of an online algorithm is via competitive analysis where we determine its competitive ratio, i.e., the smallest ratio we can guarantee for all possible requests between the completion time of the online algorithm and the completion time of the optimal (offline) solution which knows all requests in advance. For different variations of the problem, different competitive ratios are known.

This thesis is organized as follows: In the first chapter I formally define the problem with some of its variations and introduce notation. In the second chapter I give an overview of the state of the art of currently best known competitive ratios. In the third chapter, the main part of this thesis, I present three algorithms for the preemptive and uncapacitated open and closed case: ABORT, ABORT-AND-WAIT and ABORT-OR-REPLAN. They are all based on the approach that whenever new requests arrive the server tries to abort its current schedule and return to its starting position to begin a new optimal schedule for the remaining requests from there. Table 1 gives an overview of the competitive ratios of the first strategy ABORT.

Table 1: Competitive ratios of the ABORT-strategy

The second strategy ABORT-AND-WAIT extends ABORT by a waiting routine which improves its competitiveness. In BjeldeDisser17 a similar algorithm has already been investigated for the open case on the real line. I slightly changed the algorithm such that it also works efficiently on general metric spaces for the open and closed case. Table 2 contains the competitive ratios of AAW.

Table 2: Competitive ratios of the ABORT-AND-WAIT-strategy

The last algorithm I present is ABORT-OR-REPLAN for the uncapacitated closed case on the halfline. This algorithm further improves AAW such that a current schedule is not always aborted but instead sometimes the server serves unserved requests starting from its current position instead. For the closed case on the halfline this algorithm improves the best known competitive ratio of $2$ which was given for general metric spaces by Ascheuer with $(3+\sqrt{2}/2)/2 \approx 1.8536$.

Thanks to Prof. Yann Disser for suggesting this topic and useful literature.

Nicholas Pischke and Björn Schäfer spell-checked the manuscript.

1. Preliminaries

An instance of the basic online Dial-a-Ride problem consists of a metric space $M=(X,d)$ with a distinguished origin $0 \in X$ and a set of requests $\sigma = \{\sigma_1, ...,\sigma_n\}$. Each request is of the form $\sigma_i = (a_i,b_i;t_i)$ where $a_i, b_i \in M$ are the source and destination of the request, respectively, and $t_i \geq 0$ is the release time of the request. The requests are to be served by a single server starting at the origin in the shortest possible completion time, i.e. the time the last request is served, and cannot be served before their release. By $\sigma_{\leq t}$ we denote all unserved requests released up to time t. Similarly by $\sigma_{=t}$ or $\sigma_{=t_k,...,t_l}$ we denote all requests released at time $t$, respectively at one of the times $t_i$ for $i \in \{k,...,l\}$.

We distinguish multiple versions of the problem. For one, we give special attention to the case where source and destination of each request coincide. This case yields the traveling salesman problem (TSP). For another, we look at different capacities $c \in \mathbb{N} \cup \{\infty\}$ which bound the number of requests the server can carry simultaneously. Here, we also distinguish the preemptive and non-preemptive case. The former means that requests can be unloaded at any point in time to be picked up and delivered to their destination at a later time while the latter only allows requests to be unloaded once at their destination. Other versions of the problem have been investigated but are not part of this thesis, e.g. multiple servers by multi-server or so called fair adversaries where the movement of the optimal solution is restricted by MRIN and many more.

By $\hbox{OPT}(\sigma)$ we denote the completion time of the optimal (offline) solution for $\sigma$ which knows all requests in advance. Similarly for an online algorithm ALG, we denote by $\hbox{ALG}(\sigma)$ the completion time of the algorithm. This allows us to formally define what it means for an online algorithm ALG to be competitive.

Definition. an online algorithm ALG is said to be $\rho$-competitive if for all possible sets of requests $\sigma$ we have

The competitive ratio of ALG is the infimum over all $\rho \geq 1$ for which ALG is $\rho$-competitive.

In general the goal of competitive analysis is to determine an online algorithm with the lowest possible competitive ratio. Competitive analysis thus should be considered as a worst-case analysis and might not yield the best-possible average-case algorithms.

For the analysis of our algorihtms we will need the following notation: We define $L^{\ast}(t,p,R)$, resp. $L(t,p,R)$, to denote the length of a shortest possible closed, respectively open, schedule for $R \subseteq \sigma$ starting at time $t$ and position $p$. Note that in the closed case for all $0 \leq t \leq t', p,p' \in M, R \subseteq R' \subseteq \sigma$ we have

In particular, we have $L^{\ast}(0,0,\sigma) = \hbox{OPT}(\sigma)$. The same properties hold for $L(\cdot,\cdot,\cdot)$ in the open case.

2. State of the art

In recent works on online Dial-a-Ride the real line and halfline have received considerable attention. Table 3 gives an overview of the currently best known lower and upper bounds for competitive ratios of online Dial-a-Ride. As mentioned earlier, in this thesis, we will mainly focus on the uncapacitated and preemptive case. The table also contains bounds for the non-preemptive case and the traveling salesmen problem as some bounds for the non-preemptive case and TSP carry over to the other cases.

Table 3: Overview of the best known bounds for the competitive ratios of online Dial-a-Ride. Bold results are new from this thesis. Results without reference are direct consequences from other bounds.

3. Algorithms

3.1 Algorithm: ABORT

In this section we analyze the competitiveness of the ABORT-strategy that always returns to the origin when a new request arrives and then starts a shortest schedule for the remaining unserved requests from there.

ABORT for open/closed online Dial-a-Ride
this function is called upon receiving a new request

input: unserved requests $\sigma_{\leq t}$, current server-position $p^{\hbox{AAW}}(t)$ output: closed tour serving $\sigma_{\leq t}$

$T^{\hbox{return}} \longleftarrow$ shortest-possible tour back to the origin unloading every currently carried request at its respective source or delivering it to its destination

$T^{\hbox{new}} \longleftarrow$ open/closed tour of length $L(t,0,\sigma_{\leq t})$, resp. $L^{\ast}(t,0,\sigma_{\leq t})$, starting at the origin and serving $\sigma_{\leq t}$

return: $T^{\hbox{return}} \oplus T^{\hbox{new}}$

Lemma 3.1. In the preemptive setting, suppose at time $t^{\hbox{start}}$ the server is located empty at the origin while all requests are located at their respective sources. If the server follows a schedule $S$ after $t^{\hbox{start}}$ until time $t^{\hbox{ente}}$, then the inverse schedule $S^{-1}$ of length $|S^{-1}|=|S|=(t^{\hbox{ente}} - t^{\hbox{start}})$ which returns to the origin in the same way that $S$ has moved out, i.e. for all $t \in [(t^{\hbox{ente}}-t^{\hbox{start}}), 2(t^{\hbox{ente}}-t^{\hbox{start}})]$

can return every request carried at time $t^{\hbox{ente}}$ at its respective source.

Proof. Clearly, if $S^{-1}$ is followed after time $t^{\hbox{ente}}$, then the server ends at $p^{\hbox{ALG}}(2(t^{\hbox{ente}}-t^{\hbox{start}})) = 0$. Now suppose that at time $t^{\hbox{ente}}$ the server is carrying $k \leq c$ requests. Let $t^{\hbox{start}} + t_1, ..., t^{\hbox{start}} + t_k$ be the corresponding times when each of the k requests was picked up at its respective source $a_i$ ($i\in \{1,...,k\}$). At time $2(t^{\hbox{ente}}-t^{\hbox{start}})-(t^{\hbox{start}}+t_i)$ the server is at position $a_i$ again and can unload the corresponding request at its source.     ☐

3.1.1 ABORT for open online Dial-a-Ride

Theorem 3.2. Algorithm ABORT is $3$-competitive for preemptive open online Dial-a-Ride and the ratio is tight.

Proof. Let $t_n$ be the last release time from $\sigma$. Further, let $t^{\hbox{start}}$ denote the last time the server is located empty at the origin before $t_n$ and let $t_i$ be the first release time after $t^{\hbox{start}}$. At time $t_i$ the server aborts its current schedule and returns to the origin by a schedule $T^{\hbox{return}}$. By Lemma 3.1 we know the inverse tour of how the server moved after $t^{\hbox{start}}$ allows to return to the origin and unload every at $t_i$ carried request at its respective source in time $(t_i-t^{\hbox{start}})$. Thus we have $T^{\hbox{return}} \leq (t_i-t^{\hbox{start}}) \leq \hbox{OPT}(\sigma)$ where the last inequality holds as OPT must respect release time. This yields for the completion time of ABORT

The following TSP-instance shows that this ratio is tight even on the halfline $\mathbb{R}^+_0$. Consider $\sigma = \{(1;0), (1;1-\epsilon)\}$ with some small $\epsilon>0$. Right before ABORT is able to serve $(1;0)$ at time $1-\epsilon$ the server aborts its schedule to return to the origin to only get back to position 1. This yields a total completion time of $\hbox{ABORT}(\sigma) = 3-2\epsilon$ while we have $\hbox{OPT}(\sigma)=1$. Thus, the ratio $\hbox{ABORT}(\sigma) / \hbox{OPT}(\sigma)$ can be made arbitrarily close to $3$ by choosing $\epsilon$ sufficiently small.     ☐

Theorem 3.3. Algorithm ABORT is $3$-competitive for uncapacitated open online Dial-a-Ride if one omits unloading requests and the ratio is tight.

Proof. The proof is identical to the proof of theorem 3.2 if one omits unloading requests.     ☐

3.1.2 ABORT for closed online Dial-a-Ride

Theorem 3.4. Algorithm ABORT is $2.5$-competitive for preemptive closed online Dial-a-Ride and the ratio is tight.

Proof. Again, let $t_n$ be the last release time from $\sigma$, let $t^{\hbox{start}}$ denote the last time the server is located empty at the origin before $t_n$ and let $t_i$ be the first release time after $t^{\hbox{start}}$. At time $t_i$ the server aborts its current schedule and returns to the origin by a schedule $T^{\hbox{return}}$. We distinguish two cases now. If $(t_i-t^{\hbox{start}}) \leq 1/2 \hbox{OPT}(\sigma_{\leq t^{\hbox{start}}})$, then at $t_i$ going back to the origin in the same way as the server has moved out at $t^{\hbox{start}}$ allows to unload all currently carried requests at their respective sources in time $(t_i-t^{\hbox{start}})$ by Lemma 3.1. Thus we have

If $(t_i-t^{\hbox{start}}) > 1/2 \hbox{OPT}(\sigma_{\leq t^{\hbox{start}}})$, then we have $T^{\hbox{return}} < 1/2 \hbox{OPT}(\sigma_{\leq t^{\hbox{start}}})$ since completing the tour for $\sigma_{\leq t^{\hbox{start}}}$ obviously delivers every request carried at time $t_i$ to its destination. Thus, inequality (1) holds in both cases and we obtain

The following TSP-instance shows that this ratio is tight even on the halfline $\mathbb{R}^+_0$. Consider $\sigma = \{(1;1), (0;2-\epsilon)\}$ with some small $\epsilon>0$. Right before ABORT is able to serve $(1;1)$ at time $2-\epsilon$ the server aborts its schedule to only return to the origin and then move up to $1$ and return to $0$ again. This yields a total completion time of $\hbox{ABORT}(\sigma) = 5-2\epsilon$ while we have $\hbox{OPT}(\sigma)=2$. Thus, the ratio $\hbox{ABORT}(\sigma) / \hbox{OPT}(\sigma)$ can be made arbitrarily close to $2.5$ by choosing $\epsilon$ sufficiently small.     ☐

Theorem 3.5. Algorithm ABORT is $2.5$-competitive for uncapacitated closed online Dial-a-Ride if one omits unloading requests and the ratio is tight.

Proof. The proof is identical to the proof of theorem 3.4 if one omits unloading requests.     ☐

3.2 Algorithm: ABORT-AND-WAIT (AAW)

3.2.1 AAW for closed online Dial-a-Ride

In this section we present a $2$-competitive algorithm for preemptive closed Online Dial-a-Ride. The algorithm can be slightly modified to also work for the uncapacitated case. The algorithm is very simple: Once new requests are released, the AAW-server immediately aborts its current schedule by following a shortest-possible tour which returns all currently carried requests to their respective sources and ends at the origin. Once the AAW-server is located at the origin and not carrying any requests (empty), it waits until time $\hbox{OPT}(\sigma_{\leq t})$ and then starts a new optimal closed schedule for all unserved requests.

ABORT-AND-WAIT (AAW) for closed Online Dial-a-Ride
this function is called upon receiving a new request

input: unserved requests $\sigma_{\leq t}$, current server-position $p^{AAW}(t)$ output: closed tour serving $\sigma_{\leq t}$

$T^{\hbox{return}} \longleftarrow$ shortest-possible tour back to the origin unloading every currently carried request at its respective source

$T^{\hbox{new}} \longleftarrow$ closed tour of length $L^{\ast}(t,0,\sigma_{\leq t})$ starting at the origin and serving $\sigma_{\leq t}$

return: $T^{\hbox{return}} \oplus \hbox{waituntil}(\hbox{OPT}(\sigma_{\leq t})) \oplus T^{\hbox{new}}$

Theorem 3.6. Algorithm ABORT-AND-WAIT is $2$-competitive for preemptive closed online Dial-a-Ride.

Proof. Let $t_n$ be the last release time of requests from $\sigma$.

Possibly, after $t_n$ the AAW-server is able to return empty to the origin before time $\hbox{OPT}(\sigma)$. In this case, the server waits at the origin until time $\hbox{OPT}(\sigma)$ and then starts a schedule for $\sigma_{\leq t_n}$. This yields

Hence, we can assume that the AAW-server is not able to return empty to the origin before time $\hbox{OPT}(\sigma)$. In particular, the server is not already located at the origin being empty at time $t_n$. Let $t^{\hbox{start}}$ be the last point in time before $t_n$ when the AAW-server left the origin while not carrying any requests. Further, let $t_i \leq t_n$ be the first time after $t^{\hbox{start}}$ when a request from $\sigma$ is released. Note that at time $t_i$ the server starts a shortest possible tour $T^{\hbox{return}}$ to return to the origin and unload all currently carried requests at their respective sources. We obtain for the completion time of AAW:

For the tour returning to the origin, we have

by Lemma 3.1. By the triangle inequality, we further obatin

Plugging (3) and (4) into (2) yields

where the last inequality holds since OPT needs to respect release times.     ☐

Theorem 3.7. Algorithm ABORT-AND-WAIT is $2$-competitive for uncapacitated closed online Dial-a-Ride if one omits unloading requests.

Proof. The proof is identical to the proof of Thrm 3.6 if one omits unloading requests.     ☐

Ausiello have shown that a competitive ratio of $2$ is best-possible for preemptive or uncapacitated closed online Dial-a-Ride on arbitrary metric spaces. This ratio was already attained by the SMARTSTART algorithm presented by Ascheuer.

If one is only focusing on the real line $\mathbb{R}$ or the halfline $\mathbb{R}^+$ better competitive ratios than $2$ might be possible (cf. Table 3). One might think of adjusting the waiting routine of AAW to obtain better competitiveness-results.

Remark 3.8. Replacing the waiting routine of AAW such that the server waits until time $\theta \hbox{OPT}(\sigma_{\leq t})$ for some $\theta \in [0,1)$ instead of $\hbox{OPT}(\sigma_{\leq t})$ before starting a new schedule yields no better competitive ratio than $2$ even on the halfline $\mathbb{R}^+$.

Consider the following TSP-instance on $\mathbb{R}^+$: First, a request $\sigma_1=(1;1)$ is presented. For $\theta \leq 0.5$, we present as a second request $\sigma_2=(0;2-\epsilon)$ for some small $\epsilon > 0$ right before the AAW-server serves $\sigma_1$. In this case, we have $\hbox{AAW}(\{\sigma_1,\sigma_2\})=5-2\epsilon \geq 2\hbox{OPT}(\{\sigma_1,\sigma_2\}) = 2(2-\epsilon)$ for small enough $\epsilon > 0$. For $\theta > 0.5$, we present as a second request $\sigma_2'=(0;2\theta+1-\epsilon)$. In this case, we have $\hbox{AAW}(\{\sigma_1,\sigma_2'\})=2\theta+4-2\epsilon$ and $\hbox{OPT}(\{\sigma_1,\sigma_2'\})=2\theta+1-\epsilon$ for small enough $\epsilon>0$ yielding a competitive ratio of at least $\frac{6-2\epsilon}{3-\epsilon}=2$ for $\theta < 1$.

3.2.2 AAW for open online Dial-a-Ride

In this section I present a $(1+\sqrt{2})$-competitive algorithm for preemptive open online Dial-a-Ride on arbitrary metric spaces.

ABORT-AND-WAIT (AAW) for open Online Dial-a-Ride
this function is called upon receiving a new request

input: unserved requests $\sigma_{\leq t}$, current server-position $p^{AAW}(t)$ output: open tour serving $\sigma_{\leq t}$

$T^{\hbox{return}} \longleftarrow$ shortest-possible tour back to the origin unloading every currently carried request at its respective source

$T^{\hbox{new}} \longleftarrow$ open tour of length $L(t,0,\sigma_{\leq t})$ starting at the origin and serving $\sigma_{\leq t}$

return: $T^{\hbox{return}} \oplus \hbox{waituntil}(\sqrt{2} \hbox{OPT}(\sigma_{\leq t})) \oplus T^{\hbox{new}}$

Theorem 3.9. Algorithm ABORT-AND-WAIT is $(1+\sqrt{2})$-competitive for preemptive open online Dial-a-Ride.

Proof. Let $t_n$ be the last release time from $\sigma$. Analogously to the proof of Thrm 3.6 for the closed case, if the AAW-server is able to return to the origin being empty before time $\sqrt{2} \hbox{OPT}(\sigma)$, then AAW is $(1+\sqrt{2})$-competitive. In such a case the server waits until $\sqrt{2} \hbox{OPT}(\sigma)$ at the origin before starting a new open schedule for $\sigma_{\leq t_n}$ and we have

In contrast to the closed case though, in the open case the server is always able to return to the origin and unload all currently carried requests at their sources in time $\sqrt{2} \hbox{OPT}(\sigma)$. To show this, suppose that the server is not empty at the origin at time $t_n$. Now let $t^{\hbox{start}}$ be the last time before $t_n$ when the AAW-server was empty at the origin and let $t_i$ be the first release time after $t^{\hbox{start}}$. We distinguish two cases depending on the value of $t_i$.

If $t_i \geq (1+\sqrt{2}) \hbox{OPT}(\sigma_{\leq t^{\hbox{start}}})$, then the AAW-server has just served all requests from $\sigma_{\leq t^{\hbox{start}}}$ at time $t_i$ and must not unload any requests. Thus, the server returns from a position not further away from the origin than $\hbox{OPT}(\sigma_{\leq t^{\hbox{start}}})$ in time at most

where the first inequality holds only if $t_i \geq (1+\sqrt{2}) \hbox{OPT}(\sigma_{\leq t^{\hbox{start}}})$.

If $t_i < (1+\sqrt{2}) \hbox{OPT}(\sigma)$, then the AAW-server might still carry requests at time $t_i$. Taking the same route back to the origin as the one started at time $t^{\hbox{start}}$ allows to return all carried requests and arrive at $0$ in time

where the second-last inequality uses $t_i < (1+\sqrt{2}) \hbox{OPT}(\sigma)$.     ☐

3.3 Algorithm: ABORT-OR-REPLAN (AOR)

3.3.1 AOR for closed online Dial-a-Ride on the halfline ($c=\infty$)

In this section we present a $1.85$-competitive algorithm AOR for Closed Online Dial-a-Ride for the case that the metric space is $\mathbb{R}^+$ with the usual distance function $d(x,y) = |x-y|$ for $x,y \in \mathbb{R}^+$ and that the server has infinte capacity $c = \infty$.

Note that if the metric space we are operating on is the halfline $\mathbb{R}^+$ and the server has infinte capacity $c = \infty$, then staying close to the origin for as long as possible can have the following advantage: From the origin the AOR-server can serve all known requests up to that point in time in a single tour to the rightmost position of the requests. While going up, all known requests are eventually picked up and at the latest on the way back down all requests are delivered to their respective destinations. We denote the rightmost position of all requests released up to time $t$ that are not served if the AOR-server returns to the origin from its current position by

By $p_R(=t)$ we denote the rightmost position of all requests released at time $t$, i.e.

Trying to use this possibility of a single tour serving all released requests motivates a waiting scheme: If at the origin, before starting a new schedule, the AOR-server waits for as long as it can be $\theta$-competitive until time $\theta \hbox{OPT}(\sigma_{\leq t}) - 2p_R(\leq t)$ to start a single tour for the rightmost position. Here $\theta \geq 1+\sqrt{2}/2$ is a scalable waiting parameter. Further, the AOR-server always aborts its current schedule and returns to the origin whenever it can do so and still be $\theta$-competitive. For this purpose we define for the length of the abortion-schedule

We will see that it is not always possible for AOR to abort and stay $\theta$-competitive. In particual, it can happend that while going up to the current rightmost position, new requests denoted by $\sigma^{crit}_{\leq t}$ are released that do not allow an abortion while staying $\theta$-competitive (cf. Lemma !unknown!). In such a case, AOR switches to a different strategy: The AOR-server continues its tour to the rightmost position of its current schedule but instead of mindlessly going down back to 0, it serves all requests not served otherwise in a shortest possible way on its tour back to $0$. We will see that in this case AOR is $(1+\theta/2)$-competitive.

Theorem 3.10. For $\theta \in [1+\sqrt{2}/2,2]$ algorithm $\hbox{AOR}$ is $(1+\theta/2)$-competitive.

Proof. First of all, note that we have

for any point in time the server leaves the origin as the server would wait otherwise. For the first time the server leaves the origin we find that equality holds in (5) by Lemma and 3.12. Further, the following claim holds.

Claim 1. Whenever the server starts a new schedule at a time $t^{\hbox{start}} = \theta \hbox{OPT}(\sigma_{\leq t^{\hbox{start}}}) - 2p_R(\leq t^{\hbox{start}})$, then one of the two cases apply:

• If we have $\hbox{abort}(t) \leq \theta OPT(\sigma_{\leq t})$ for some time $t > t^{\hbox{start}}$, then a new schedule will be started at a time $\tilde{t}^{\hbox{start}} = \theta \hbox{OPT}(\sigma_{\leq \tilde{t}^{\hbox{start}}}) - 2p_R(\leq \tilde{t}^{\hbox{start}})$.

• If we have $\hbox{abort}(t) > \theta \hbox{OPT}(\sigma_{\leq t})$ for all $t>t^{\hbox{start}}$, then the schedule started at $t^{\hbox{start}}$ is the last schedule and serves all requests from $\sigma$ no later than $(1+\theta/2) \hbox{OPT}(\sigma)$.

Clearly, claim 1 completes the proof since for the last time the server starts a new schedule at a time $t^{\hbox{start}} = \theta \hbox{OPT}(\sigma_{\leq t^{\hbox{start}}}) - 2p_R(\leq t^{\hbox{start}})$ obviously the first case of claim 1 does not apply. Hence, the second case applies and the server serves $\sigma$ in time $(1+\theta/2) \hbox{OPT}(\sigma)$.

Thus, let us prove claim 1. For this purpose, assume that at a time $t^{\hbox{start}} = \theta \hbox{OPT}(\sigma_{\leq t^{\hbox{start}}}) - 2p_R(\leq t^{\hbox{start}})$ the server starts a new schedule. The first case behaves very simple: Suppose that we have $\hbox{abort}(t) \leq \theta OPT(\sigma_{\leq t})$ for some time $t > t^{\hbox{start}}$. By Lemma 3.13 this implies that the server arrives at the origin at a time $t' \leq \theta \hbox{OPT}(\sigma_{\leq t'}) - 2p_R(\leq t')$. Then Lemma 3.12 assures that a new schedule will be started at a time $\tilde{t}^{\hbox{start}} = \theta \hbox{OPT}(\sigma_{\leq \tilde{t}^{\hbox{start}}}) - 2p_R(\leq \tilde{t}^{\hbox{start}})$.

Now let us take a look at the second case and suppose that we have $\hbox{abort}(t) > \theta \hbox{OPT}(\sigma_{\leq t})$ for all $t > t^{\hbox{start}}$. We want to show that indeed the current schedule from $t^{\hbox{start}}$ is the last one and will be served in time $(1+\theta/2) \hbox{OPT}(\sigma)$. By Lemma 3.14 we can make the following assumptions for all requests $(a_i,b_i;t_i) \in \sigma_{>t^{\hbox{start}}}$:

Further, for the completion time of AOR we do not need to consider requests $(a_i,b_i;t_i) \in \sigma_{>t^{\hbox{start}}}$ with $b_i \leq a_i$: If such a request is released while the server is moving upwards to $p_R(\leq t^{\hbox{start}})$, i.e. $t_i \in (t^{\hbox{start}}, t^{\hbox{start}}+p_R(\leq t^{\hbox{start}})]$, then obviously any tour back from $p_R(\leq t^{\hbox{start}})$ to the origin serves it since $b_i \leq a_i \leq p_R(\leq t^{\hbox{start}}) = p^{\hbox{AOR}}(t^{\hbox{start}} + p_R(\leq t^{\hbox{start}}))$ by (6). On the other hand, if such a request is released after the server has been to position $p_R(\leq t^{\hbox{start}})$ at time $t_i \in (t^{\hbox{start}}+p_R(\leq t^{\hbox{start}}), t^{\hbox{start}} + 2p_R(\leq t^{\hbox{start}})]$, then note that the right-hand side of the inequality in (8) is a lower bound for the position of the server. Thus, we have $b_i \leq a_i \leq p^{\hbox{AOR}}(t_i)$ and the request is also served by any route back to the origin. Also, for the requests released before the server reaches $p_R(\leq t^{\hbox{start}})$ after time $t^{\hbox{start}}$, we do not consider requests with $a_i < b_i$ and $p^{\hbox{AOR}}(t_i) \leq a_i$.

These considerations motivate the following definition of the set of relevant requests $\sigma^{up}$ that are released while the server is moving upwards to $p_R(\leq t^{\hbox{start}})$, respectively $\sigma^{down}$ for the relevant requests released after the server visited $p_R(\leq t^{\hbox{start}})$ at time $t^{\hbox{start}} + p_R(\leq t^{\hbox{start}})$:

Once the AOR-server arrives at $p_R(\leq t^{\hbox{start}})$ at time $t^{top} := t^{\hbox{start}} + p_R(\leq t^{\hbox{start}})$, it follows a shortest schedule back to the origin serving unserved requests of length $L^{\ast}(t^{top}, p_R(\leq t^{\hbox{start}}), \sigma_{\leq t^{top}}) = L^{\ast}(t^{top}, p_R(\leq t^{\hbox{start}}), \sigma^{up})$. Because every request $(a_i, b_i; t_i) \in \sigma^{down}$ satisfies $a_i < b_i \leq p_R(\leq t^{\hbox{start}}) - (t_i - t^{top})$ by (8), we obtain from Lemma that the unique optimal tours for $\sigma^{up}$ and $\sigma^{up} \cup \{(a_i,b_i;t_i)\}$ coincide until time $t_i$. Iterating this argument for each request from $\sigma^{down}$ yields that whenever a new request from $\sigma^{down}$ is released, AOR can adapt its route to still be optimal in the sense that it will complete its tour for $\sigma^{up} \cup \sigma^{down}$ in time $t^{top} + L^{\ast}(t^{top}, p_R(\leq t^{\hbox{start}}), \sigma^{up} \cup \sigma^{down})$. Thus, we find for the completion time of the AOR-server

Now, let us take a look at the completion time of OPT. Note that we can assume that $\hbox{OPT}$ serves no request from $\sigma^{up}$ before visiting $p_R(\leq t^{\hbox{start}})$. If $\hbox{OPT}$ does serve a request $(a_j,b_j;t_j) \in \sigma^{up}$ before visiting $p_R(\leq t^{\hbox{start}})$, note that we get $\hbox{OPT}(\sigma) \geq t^{\hbox{start}} + 2p_R(\leq t^{\hbox{start}})$ since the OPT-server picks up the request at $a_j$ after the AOR-server has been there at time $t^{\hbox{start}}+a_j$ and then still needs to go to $p_R(\leq t^{\hbox{start}})$ and back to the origin. Hence, we get

where the last inequality holds if $\theta \geq (1+\sqrt{5})/2 \approx 1.62$. Consequently, we can indeed assume that OPT serves no request from $\sigma^{up}$ or $\sigma^{down}$ before visiting $p_R(\leq t^{\hbox{start}})$. Thus, we have

For the next part of the proof let $\hbox{diff}$ denote the extra time that OPT needs to serve the incoming requests from after $t^{\hbox{start}}$, i.e. $\hbox{diff} := \hbox{OPT}(\sigma_{\leq t_i}) - \hbox{OPT}(\sigma_{\leq t^{\hbox{start}}})$. Also, for better readability, we now write $L^{\ast}$ for $L^{\ast}(t^{top}, p_R(\leq t^{\hbox{start}}), \sigma^{up} \cup \sigma^{down})$ and $p_R$ for $p_R(\leq t^{\hbox{start}})$. Note that $(L^{\ast}-p_R)$ denotes the extra time it takes AOR to serve the incoming requests from after $t^{\hbox{start}}$. First, note that possibly OPT needs more extra time to serve the requests from after $t^{\hbox{start}}$ than AOR. We assume that we even have $\theta \hbox{diff} \geq (L^{\ast} - p_R)$. We then obtain

Thus, we can assume that we have $\theta \hbox{diff} < (L^{\ast}-p_R)$. Here we need two distinguish two cases depending on the value of $(L^{\ast} - p_R)$.

Case 1. Suppose that

In this case OPT needs less extra time to serve the requests released after $t^{\hbox{start}}$ than AOR. This can happend if e.g. OPT was waiting at some point in its schedule for $\sigma_{\leq t^{\hbox{start}}}$ and can now use this time for good to serve requests from after $t^{\hbox{start}}$. Let $\hbox{prepared}$ denote the difference between the extra time it takes to serve the requests from after $t^{\hbox{start}}$ for AOR and OPT, i.e.

Recall $\hbox{OPT}(\sigma) \geq 2p_R + (L^{\ast} - p_R)$ from (10). Together with

Using (11) we get for the ratio of $\hbox{AOR}(\sigma)$ and $\hbox{OPT}(\sigma)$:

Case 2. Suppose that

First, let $t_i$ be the first time after $t^{\hbox{start}}$ where requests are released. Let us assume that $t_i \leq 2 p_R(\leq t^{\hbox{start}})$.

From (9) and (10) we obtain

Now let us assume that $t_i > 2p_R$. Here we also get

    ☐

Lemma 3.11. If $\theta \geq 1+\sqrt{2}/2$ and at time $t_i$ a new rightmost request is released, i.e. $p_R(=t_i) \geq p_R(\leq t_{i-1})$, then the $\hbox{AOR}$-server can $\hbox{abort}$ its current schedule and still be $\theta$-competitive for $\sigma_{\leq t_i}$, i.e. $\hbox{abort}(t_i) \leq \theta \hbox{OPT}(\sigma_{\leq t_i})$.

Proof. First, we consider the case that the AOR-server is located at the origin at time $t_i$. Then, we have $\hbox{abort}(t_i) = t_i + 2p_R(= t_i)$ while $\hbox{OPT}(\sigma_{\leq t_i}) \geq \max(t_i + p_R(= t_i), 2p_R(= t_i))$. For $t_i \leq p_R(= t_i)$ we get

And similarly for $t_i > p_R(= t_i)$ we have

where the last inequality holds since the expression is monotonically decreasing for $t_i \geq p_R(=t_i)$.

Hence, we can assume that AOR is not at the origin at time $t_i$. Let $t^{\hbox{start}}$ be the last point in time before $t_i$ when the $\hbox{AOR}$-server left the origin to visit $p_R(\leq t^{\hbox{start}})$. Also let $\lambda \geq 1$ such that $\lambda p_R(\leq t^{\hbox{start}}) = p_R(=t_i)$. We then have

We now distinguish two cases depending on the value of $\lambda$.

1. For $\lambda \leq 1+\sqrt{2}$ we first of all want to achieve a lower bound for the time $t_i$. Since the server would have waited otherwise, we have

For the current time $t_i \geq t^{\hbox{start}} + p^{\hbox{AOR}}(t_i)$ this implies

Using (13) and $p^{\hbox{AOR}}(t_i) \leq p_R(\leq t^{\hbox{start}})$ in (12) together with simple arguments of monotonicity yields

where the last inequality holds only for $\theta \geq 1+\sqrt{2}/2$.

2. For $\lambda > 1+\sqrt{2}$ we need a different lower bound for $t_i$. As we can assume that $t_i \geq p_R(=t_i)$, we have

Again, plugging (14) in (12) and using monotonicity of well-known functions gets us

    ☐

Lemma 3.12. If $\theta \geq 3/2$ and if the $\hbox{AOR}$-server is waiting while at time $t_i$ new requests arrive, then $\hbox{AOR}$ remains $\theta$-competitive for $\sigma_{\leq t_i}$, i.e. we have $\hbox{abort}(t_i) \leq \theta \hbox{OPT}(\sigma_{\leq t_i})$.

Proof. Recall from the first part of the proof of Lemma 3.11 that $p_R(\leq t_{i-1}) \leq p_R(=t_i)$ implies $\hbox{abort}(t_i) \leq \frac{3}{2} \hbox{OPT}(\sigma_{\leq t_i})$. Hence, assume that $p_R(\leq t_{i-1}) > p_R(=t_i)$. As the server was waiting at the origin up to time $t_i$ with knowing the requests from $\sigma_{\leq t_{i-1}}$ we have $t_i \leq \theta \hbox{OPT}(\sigma_{t_{i-1}}) - 2p_R(\leq t_{i-1})$ which yields

    ☐

Lemma 3.13. If $\theta \geq 1+\sqrt{2}/2$ and at time $t_{i}$ the $\hbox{AOR}$-server is currently aborting the last schedule and moving downwards, i.e. $\hbox{abort}(t_{i-1}) \leq \theta \hbox{OPT}(\sigma_{\leq t_{i-1}})$, then $\hbox{AOR}$ can afford to keep aborting and stay $\theta$-competitive, i.e. $\hbox{abort}(t_{i}) \leq \theta \hbox{OPT}(\sigma_{\leq t_{i}})$.

Proof. Again, we can assume that $p_R(\leq t_{i-1}) > p_R(=t_i)$ since otherwise Lemma 3.11 provides $\hbox{abort}(t_i) \leq \theta \hbox{OPT}(\sigma_{\leq t_i})$ for $\theta \geq 1+\sqrt{2}/2$. Because $\hbox{AOR}$ is moving downwards since time $t_{i-1}$ we have

From this we obtain

    ☐

Lemma 3.14. If $\theta \in [1+\sqrt{2}/2,2]$ and the AOR-server leaves the origin to start a new schedule at time $t^{\hbox{start}}$, then the following statements hold:

1. If requests are released at a time $t_i > t^{\hbox{start}}$ with $p_R(=t_i) \geq \frac{-2\theta^2+3\theta+2}{\theta} p_R(\leq t^{\hbox{start}})$, then $\hbox{abort}(t) \leq \theta \hbox{OPT}(\sigma_{\leq t})$ for some $t>t^{\hbox{start}}$.

2. If requests are released at a time $t_i \geq t^{\hbox{start}}+2p_R(\leq t^{\hbox{start}})$, then $\hbox{abort}(t) \leq \theta \hbox{OPT}(\sigma_{\leq t})$ for some $t>t^{\hbox{start}}$.

3. If requests are released at a time $t_i \geq t^{\hbox{start}}+p_R(\leq t^{\hbox{start}})$ with $p_R(=t_i) \geq p_R(\leq t^{\hbox{start}}) - (t_i - (t^{\hbox{start}}+p_R(\leq t^{\hbox{start}})))$, then $\hbox{abort}(t) \leq \theta \hbox{OPT}(\sigma_{\leq t})$ for some $t>t^{\hbox{start}}$.

Proof. First of all let us assume that $p_R(=t) < p_R(\leq t^{\hbox{start}})$ for all $t>t^{\hbox{start}}$ since otherwise the statements are true by Lemma 3.11 as $\theta \geq 1+\sqrt{2}/2$. Further, for each of the statements we suppose that $\hbox{abort}(t) > \theta \hbox{OPT}(\sigma_{\leq t})$ for all $t \in (t^{\hbox{start}},t_i)$. Now, let us prove each of the three statements separately.

proof of (i): Requests are released at time $t_i > t^{\hbox{start}}$ with $p_R(=t_i) \geq \frac{-2\theta^2+3\theta+2}{\theta} p_R(\leq t^{\hbox{start}})$. Since any tour for $\sigma_{\leq t_i}$ needs to return to the origin in the end, we obtain as a lower bound for the length of the optimal offline solution

As the server was located at the origin at time $t^{\hbox{start}}$ we find for the release time $t_i$ that

Using (16) and (17) we obtain for the ratio of $\hbox{abort}(t_i)$ and $\hbox{OPT}(\sigma_{\leq t_i})$:

proof of (ii): Requests are released at time $t_i \geq t^{\hbox{start}} + 2p_R(\leq t^{\hbox{start}})$. By (i) we can assume that $p_R(\leq t_i), p^{\hbox{AOR}}(t_i) \leq \frac{-2\theta^2+3\theta+2}{\theta} p_R(\leq t^{\hbox{start}})$. Thus, we have

which yields

where the last inequality holds only if $\theta \geq c$ with $c \approx 1.70$ being the largest root of the polynomial $-X^3-2X^2+9/2X+3$.

proof of (iii): Requests are released at time $t_i \geq t^{\hbox{start}}+p_R(\leq t^{\hbox{start}})$ with $p_R(=t_i) \geq p_R(\leq t^{\hbox{start}}) - (t_i - (t^{\hbox{start}}+p_R(\leq t^{\hbox{start}})))$. By (i) we can assume that

for all $t>t^{\hbox{start}}$. Consequently once the server reached position $p_R(\leq t^{\hbox{start}})$ at time $t^{\hbox{start}} + p_R(\leq t^{\hbox{start}})$, it moves to the left at least until position $\frac{-2\theta^2+3\theta+2}{\theta} p_R(\leq t^{\hbox{start}})$ and then does not move to the right of this position anymore. For $t=t_i$ in (18) we get

which is equivalent to

Note that the right hand side of the last inequality is exactly the time it takes for the AOR-server to move to position $\frac{-2\theta^2+3\theta+2}{\theta} p_R(\leq t^{\hbox{start}})$ after having visited $p_R(\leq t^{\hbox{start}})$ at time $t^{\hbox{start}}+p_R(\leq t^{\hbox{start}})$. Hence, we obtain

Further, for the optimal offline solution of $\sigma_{\leq t_i}$, we find that

Using (19) and (20) we now have for the ratio of $\hbox{abort}(t_i)$ and $\hbox{OPT}(\sigma_{\leq t_i})$

Again the last inequality holds only for $\theta \geq c \approx 1.70$.     ☐

Lemma 3.15. Let $t,p_R \geq 0$ and $\sigma = { (a_1,b_1;t_1), ..., (a_n,b_n;t_n) }$ be a set of requests where $a_i < b_i \leq p_R$ and $t_i-(p_R-a_i) \leq t$ for all $i=1,...,n$. Then there is a unique optimal tour for $\sigma$ starting at position $p_R$ at time $t$ of length $L^{\ast}(t,p_R,\sigma)$.

Further, let $(a_{n+1},b_{n+1}; t_{n+1})$ be a request with $a_{n+1} < b_{n+1} \leq p_R - (t_{n+1}-t)$, $t_{n+1} \in [0,t+p_R]$. Then the unique optimal tours for $\sigma$ and $\sigma \cup {(a_{n+1},b_{n+1};t_{n+1})}$ starting at position $p_R$ and at time $t$ coincide until time $t_{n+1}$.

Proof. First of all note that any tour for $\sigma$ starting at $p_R$ at time $t$ must not wait for request releases: As soon as the server reaches a position $a_i$, it can pick up the request $(a_i,b_i;t_i)$ since $t_i-(p_R-a_i) \leq t$ for all $i=1,...,n$. Further, we know that any tour for $\sigma$ that starts at position $p_R$ at time $t$ needs to contain (possibly interrupted) segments where the server moves up from $a_i$ to $b_i$ for all $i \in {1,...,n}$. Let ${[a_1',b_1'], ..., [a_k',b_k']}$ be the set of intervals that is obtained by replacing intersecting intervals from ${[a_1,b_1], ..., [a_n,b_n]}$ with their unions such that

• for all $i \in {1,...,k}$ there is a subset $I \subseteq {1,...,n}$ with $[a_i',b_i'] = \bigcup_{j \in I} [a_j,b_j]$
• and for all $i \in {1,...,k}$, respectively $i \in {1,...,k-1}$, we have $a_i' < b_i'$ and $b_i' < a_{i+1}'$.

Clearly, any tour starting at $p_R$ at time $t$ that serves $\sigma$ needs to move up the intervals $[a_i',b_i']$ for all $i \in {1,...,k}$ at some point in time. Thus, the unique optimal tour of length $L^{\ast}(t,p_R,\sigma)$ is given by

In order to see that the unique optimal tours for $\sigma$ and $\sigma \cup \{(a_{n+1},b_{n+1};t_{n+1})\}$ starting at position $p_R$ and at time $t$ coincide until time $t_{n+1}$, let $a_k',...,a_l'$ be all $a_i'$ with $a_i' \geq b_{n+1}$. The server of the optimal tour for $\sigma \cup \{(a_{n+1},b_{n+1};t_{n+1})\}$, just like the one for the optimal tour for $\sigma$, starts by traversing all the intervals $[a_k',b_k'],...,[a_l',b_l']$ and then moves to the left: The server of the optimal tour for $\sigma \cup \{(a_{n+1},b_{n+1};t_{n+1})\}$ moves towards some $a_i < b_{n+1}$ where $i \in \{1,...,n+1\}$ depends on the exact values of $a_{n+1}$ and $b_{n+1}$ and the server of the optimal tour for $\sigma$ moves towards $a_{l-1}'<b_{n+1}$. Consequently both tours coincide at least until they reach $b_{n+1}$ which is not possible any earlier than $t_{n+1}$ since $b_{n+1} \leq p_R-(t_{n+1}-t)$.     ☐

Literature

1. [Ascheuer] Ascheuer, Norbert and Krumke, Sven Oliver and Rambau, Jörg: Online Dial-a-Ride Problems: Minimizing the Completion Time, 2000, Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, Springer-Verlag, Berlin, Heidelberg, STACS '00
2. [Ausiello] Ausiello, Giorgio and Feuerstein, Esteban and Leonardi, S. and Stougie, L. and Talamo, Maurizio: Algorithms for the On-Line Travelling Salesman, 04-2001, Algorithmica, Vol. 29, pp. 560-581, https://doi.org/10.1007/s004530010071
3. [Birx19] Alexander Birx and Yann Disser and Kevin Schewior: Improved Bounds for Open Online Dial-a-Ride on the Line, 2019, https://arxiv.org/abs/1907.02858
4. [BjeldeDisser17] Bjelde, Antje and Disser, Yann and Hackfeld, Jan and Hansknecht, Christoph and Lipmann, Maarten and Meißner, Julie and Schewior, Kevin and Schlöter, Miriam and Stougie, Leen: Tight Bounds for Online TSP on the Line, 2017, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, USA, SODA '17, Barcelona, Spain
5. [Krumke2002] Sven O. Krumke: Online Optimization: Competitive Analysis and Beyond, 2002, ZIB-Report
6. [MLipmann] M. Lipmann: On-line routing, 2003, Technische Universiteit Eindhoven, Department of Mathematics and Computer Science, https://doi.org/10.6100/IR565209
7. [MRIN] Michiel Blom and S.O. Krumke and Paepe, de, W.E. and L. Stougie: The online-TSP against fair adversaries, 1999, Technische Universiteit Eindhoven, Memorandum COSOR
8. [multi-server] Bonifaci, Vincenzo and Lipmann, Maarten and Stougie, Leen: Online multi-server dial-a-ride problems, 01-2006, Computational Complexity - CC, pp.