Online multi-server dial-a-ride problems

In an online dial-a-ride problem, a crew of servers has to process transportation requests as they arrive in real time. Possible objective functions include minimizing the makespan and minimizing the sum of completion times. We give competitive algorithms and negative results for several online dial-a-ride problems with multiple servers. Surprisingly, in some cases the competitive ratio is dramatically better than that of the corresponding single server problem.