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
Case
ABORT
open
closed
general
uncapacitated ()
3
2.5
general
preemptive
3
2.5
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
Case
ABORT-AND-WAIT
open
closed
general
uncapacitated ()
2.4142
2.5
general
preemptive
2.4142
2.5
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 which was given for general metric spaces by Ascheuer with .
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 with a distinguished origin and a set of requests .
Each request is of the form where are the source and destination of the request, respectively, and 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 we denote all unserved requests released up to time t. Similarly by or we denote all requests released at time , respectively at one of the times for .
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 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 we denote the completion time of the optimal (offline) solution for which knows all requests in advance.
Similarly for an online algorithm ALG, we denote by 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 -competitive if for all possible sets of requests we have
The competitive ratio of ALG is the infimum over all for which ALG is -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 , resp. , to denote the length of a shortest possible closed, respectively open, schedule for starting at time and position .
Note that in the closed case for all we have
In particular, we have .
The same properties hold for 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.
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 , current server-position output: closed tour serving
shortest-possible tour back to the origin unloading every currently carried request at its respective source or delivering it to its destination
open/closed tour of length , resp. , starting at the origin and serving
return:
Lemma 3.1.In the preemptive setting, suppose at time the server is located empty at the origin while all requests are located at their respective sources.
If the server follows a schedule after until time , then the inverse schedule of length which returns to the origin in the same way that has moved out, i.e. for all
can return every request carried at time at its respective source.
Proof.
Clearly, if is followed after time , then the server ends at .
Now suppose that at time the server is carrying requests.
Let be the corresponding times when each of the k requests was picked up at its respective source ().
At time the server is at position 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 -competitive for preemptive open online Dial-a-Ride and the ratio is tight.
Proof.
Let be the last release time from . Further, let denote the last time the server is located empty at the origin before and let be the first release time after .
At time the server aborts its current schedule and returns to the origin by a schedule . By Lemma 3.1 we know the inverse tour of how the server moved after allows to return to the origin and unload every at carried request at its respective source in time .
Thus we have 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 . Consider with some small .
Right before ABORT is able to serve at time the server aborts its schedule to return to the origin to only get back to position 1. This yields a total completion time of while we have . Thus, the ratio can be made arbitrarily close to by choosing sufficiently small.
☐
Theorem 3.3.
Algorithm ABORT is -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 -competitive for preemptive closed online Dial-a-Ride and the ratio is tight.
Proof.
Again, let be the last release time from , let denote the last time the server is located empty at the origin before and let be the first release time after .
At time the server aborts its current schedule and returns to the origin by a schedule .
We distinguish two cases now.
If , then at going back to the origin in the same way as the server has moved out at allows to unload all currently carried requests at their respective sources in time by Lemma 3.1.
Thus we have
If , then we have since completing the tour for obviously delivers every request carried at time 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 . Consider with some small .
Right before ABORT is able to serve at time the server aborts its schedule to only return to the origin and then move up to and return to again. This yields a total completion time of while we have . Thus, the ratio can be made arbitrarily close to by choosing sufficiently small.
☐
Theorem 3.5.
Algorithm ABORT is -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 -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 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 , current server-position output: closed tour serving
shortest-possible tour back to the origin unloading every currently carried request at its respective source
closed tour of length starting at the origin and serving
return:
Theorem 3.6.Algorithm ABORT-AND-WAIT is -competitive for preemptive closed online Dial-a-Ride.
Proof.
Let be the last release time of requests from .
Possibly, after the AAW-server is able to return empty to the origin before time . In this case, the server waits at the origin until time and then starts a schedule for . This yields
Hence, we can assume that the AAW-server is not able to return empty to the origin before time . In particular, the server is not already located at the origin being empty at time .
Let be the last point in time before when the AAW-server left the origin while not carrying any requests. Further, let be the first time after when a request from is released.
Note that at time the server starts a shortest possible tour 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 -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 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 or the halfline better competitive ratios than 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 for some instead of before starting a new schedule yields no better competitive ratio than even on the halfline .
Consider the following TSP-instance on :
First, a request is presented.
For , we present as a second request for some small right before the AAW-server serves . In this case, we have for small enough .
For , we present as a second request . In this case, we have and for small enough yielding a competitive ratio of at least for .
3.2.2 AAW for open online Dial-a-Ride
In this section I present a -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 , current server-position output: open tour serving
shortest-possible tour back to the origin unloading every currently carried request at its respective source
open tour of length starting at the origin and serving
return:
Theorem 3.9.
Algorithm ABORT-AND-WAIT is -competitive for preemptive open online Dial-a-Ride.
Proof.
Let be the last release time from . 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 , then AAW is -competitive. In such a case the server waits until at the origin before starting a new open schedule for 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 .
To show this, suppose that the server is not empty at the origin at time .
Now let be the last time before when the AAW-server was empty at the origin and let be the first release time after .
We distinguish two cases depending on the value of .
If , then the AAW-server has just served all requests from at time and must not unload any requests. Thus, the server returns from a position not further away from the origin than in time at most
where the first inequality holds only if .
If , then the AAW-server might still carry requests at time . Taking the same route back to the origin as the one started at time allows to return all carried requests and arrive at in time
where the second-last inequality uses .
☐
3.3 Algorithm: ABORT-OR-REPLAN (AOR)
3.3.1 AOR for closed online Dial-a-Ride on the halfline ()
In this section we present a -competitive algorithm AOR for Closed Online Dial-a-Ride for the case that the metric space is with the usual distance function for and that the server has infinte capacity .
Note that if the metric space we are operating on is the halfline and the server has infinte capacity , 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 that are not served if the AOR-server returns to the origin from its current position by
By we denote the rightmost position of all requests released at time , 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 -competitive until time to start a single tour for the rightmost position.
Here 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 -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 -competitive. In particual, it can happend that while going up to the current rightmost position, new requests denoted by are released that do not allow an abortion while staying -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 . We will see that in this case AOR is -competitive.
Theorem 3.10.For algorithm is -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 , then one of the two cases apply:
If we have for some time , then a new schedule will be started at a time .
If we have for all , then the schedule started at is the last schedule and serves all requests from no later than .
Clearly, claim 1 completes the proof since for the last time the server starts a new schedule at a time obviously the first case of claim 1 does not apply. Hence, the second case applies and the server serves in time .
Thus, let us prove claim 1.
For this purpose, assume that at a time the server starts a new schedule.
The first case behaves very simple: Suppose that we have for some time . By Lemma 3.13 this implies that the server arrives at the origin at a time . Then Lemma 3.12 assures that a new schedule will be started at a time .
Now let us take a look at the second case and suppose that we have for all . We want to show that indeed the current schedule from is the last one and will be served in time .
By Lemma 3.14 we can make the following assumptions for all requests :
Further, for the completion time of AOR we do not need to consider requests with :
If such a request is released while the server is moving upwards to , i.e. , then obviously any tour back from to the origin serves it since by (6).
On the other hand, if such a request is released after the server has been to position at time , 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 and the request is also served by any route back to the origin.
Also, for the requests released before the server reaches after time , we do not consider requests with and .
These considerations motivate the following definition of the set of relevant requests that are released while the server is moving upwards to , respectively for the relevant requests released after the server visited at time :
Once the AOR-server arrives at at time , it follows a shortest schedule back to the origin serving unserved requests of length .
Because every request satisfies by (8), we obtain from Lemma that the unique optimal tours for and coincide until time .
Iterating this argument for each request from yields that whenever a new request from is released, AOR can adapt its route to still be optimal in the sense that it will complete its tour for in time .
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 serves no request from before visiting . If does serve a request before visiting , note that we get since the OPT-server picks up the request at after the AOR-server has been there at time and then still needs to go to and back to the origin.
Hence, we get
where the last inequality holds if .
Consequently, we can indeed assume that OPT serves no request from or before visiting .
Thus, we have
For the next part of the proof let denote the extra time that OPT needs to serve the incoming requests from after , i.e. . Also, for better readability, we now write for and for .
Note that denotes the extra time it takes AOR to serve the incoming requests from after .
First, note that possibly OPT needs more extra time to serve the requests from after than AOR. We assume that we even have .
We then obtain
Thus, we can assume that we have . Here we need two distinguish two cases depending on the value of .
Case 1.
Suppose that
In this case OPT needs less extra time to serve the requests released after than AOR. This can happend if e.g. OPT was waiting at some point in its schedule for and can now use this time for good to serve requests from after . Let denote the difference between the extra time it takes to serve the requests from after for AOR and OPT, i.e.
Recall from (10).
Together with
Using (11) we get for the ratio of and :
Case 2.
Suppose that
First, let be the first time after where requests are released. Let us assume that .
From (9) and (10) we obtain
Now let us assume that .
Here we also get
☐
Lemma 3.11.If and at time a new rightmost request is released, i.e. , then the -server can its current schedule and still be -competitive for , i.e. .
Proof.
First, we consider the case that the AOR-server is located at the origin at time . Then, we have while .
For we get
And similarly for we have
where the last inequality holds since the expression is monotonically decreasing for .
Hence, we can assume that AOR is not at the origin at time . Let be the last point in time before when the -server left the origin to visit .
Also let such that . We then have
We now distinguish two cases depending on the value of .
For we first of all want to achieve a lower bound for the time . Since the server would have waited otherwise, we have
For the current time this implies
Using (13) and in (12) together with simple arguments of monotonicity yields
where the last inequality holds only for .
For we need a different lower bound for . As we can assume that , we have
Again, plugging (14) in (12) and using monotonicity of well-known functions gets us
☐
Lemma 3.12.If and if the -server is waiting while at time new requests arrive, then remains -competitive for , i.e. we have .
Proof.
Recall from the first part of the proof of Lemma 3.11 that implies .
Hence, assume that . As the server was waiting at the origin up to time with knowing the requests from we have which yields
☐
Lemma 3.13.If and at time the -server is currently aborting the last schedule and moving downwards, i.e. , then can afford to keep aborting and stay -competitive, i.e. .
Proof.
Again, we can assume that since otherwise Lemma 3.11 provides for .
Because is moving downwards since time we have
From this we obtain
☐
Lemma 3.14.If and the AOR-server leaves the origin to start a new schedule at time , then the following statements hold:
If requests are released at a time with , then for some .
If requests are released at a time , then for some .
If requests are released at a time with , then for some .
Proof.
First of all let us assume that for all since otherwise the statements are true by Lemma 3.11 as .
Further, for each of the statements we suppose that for all .
Now, let us prove each of the three statements separately.
proof of (i): Requests are released at time with . Since any tour for 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 we find for the release time that
Using (16) and (17) we obtain for the ratio of and :
proof of (ii): Requests are released at time . By (i) we can assume that .
Thus, we have
which yields
where the last inequality holds only if with being the largest root of the polynomial .
proof of (iii): Requests are released at time with .
By (i) we can assume that
for all . Consequently once the server reached position at time , it moves to the left at least until position and then does not move to the right of this position anymore.
For 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 after having visited at time . Hence, we obtain
Further, for the optimal offline solution of , we find that
Using (19) and (20) we now have for the ratio of and
Again the last inequality holds only for .
☐
Lemma 3.15.Let and be a set of requests where and for all .
Then there is a unique optimal tour for starting at position at time of length .
Further, let be a request with , .
Then the unique optimal tours for and starting at position and at time coincide until time .
Proof.
First of all note that any tour for starting at at time must not wait for request releases: As soon as the server reaches a position , it can pick up the request since for all .
Further, we know that any tour for that starts at position at time needs to contain (possibly interrupted) segments where the server moves up from to for all .
Let be the set of intervals that is obtained by replacing intersecting intervals from with their unions such that
for all there is a subset with
and for all , respectively , we have and .
Clearly, any tour starting at at time that serves needs to move up the intervals for all at some point in time. Thus, the unique optimal tour of length is given by
In order to see that the unique optimal tours for and starting at position and at time coincide until time , let be all with .
The server of the optimal tour for , just like the one for the optimal tour for , starts by traversing all the intervals and then moves to the left:
The server of the optimal tour for moves towards some where depends on the exact values of and and
the server of the optimal tour for moves towards . Consequently both tours coincide at least until they reach which is not possible any earlier than since .
☐
Literature
[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
[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
[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
[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
[Krumke2002] Sven O. Krumke: Online Optimization: Competitive Analysis and Beyond, 2002, ZIB-Report
[MLipmann] M. Lipmann: On-line routing, 2003, Technische Universiteit Eindhoven, Department of Mathematics and Computer Science, https://doi.org/10.6100/IR565209
[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
[multi-server] Bonifaci, Vincenzo and Lipmann, Maarten and Stougie, Leen: Online multi-server dial-a-ride problems, 01-2006, Computational Complexity - CC, pp.