On-line single-server dial-a-ride problems

ABSTRACT

In this paper results on the dial-a-ride problem with a single server are presented. Requests for rides consist of two points in a metric space, a source and a destination. A ride has to be made by the server from the source to the destination. The server travels at unit speed in the metric space and the objective is to minimize some function of the delivery times at the destinations. We study this problem in the natural on-line setting. Calls for rides come in while the server is traveling. This models, e.g. the taxi problem, or, if the server has capacity more than a minibus or courier service problem. For the version of this problem in which the server has infinite capacity having as objective minimization of the time the last destination is served, we design an algorithm that has competitive ratio 2. We also show that this is best possible, since no algorithm can have competitive ratio better than 2 independent of the capacity of the server. Besides, we give a simple 2.5-competitive algorithm for the case with finite capacity. Then we study the on-line problem with objective minimization of the sum of completion times of the rides. We prove a lower bound on the competitive ration of any algorithm of 1 + 2 for a server with any capacity and of 3 for a server has infinite capacity and the metric space is the real line. The algorithm has competitive ration 15. Copyright 2001 Elsevier Science B.V.

REFERENCES

• 1: N. Ascheuer, M. Groetschel, N. Kamin, J. Rambau, Combinatorial online optimization in practice, preprint SC 98-07, Konrad-Zuse-Zentrum für Informationstechnik, Berlin, 1998.
• 2: N. Ascheuer, S.O. Krumke, J.Rambau, Competitive scheduling of elevators, preprint SC 93-34, Konrad-Zuse-Zentrum für Informationstechnik, Berlin, 1998.
• 3: Mikhail J. Atallah , S. Rao Kosaraju, Efficient solutions to some transportation problems with applications to minimizing robot arm travel, SIAM Journal on Computing, v.17 n.5, p.849-869, October 1988 [doi>10.1137/0217053]
• 4: G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie, M. Talamo, Algorithms for the on-line traveling salesman, Algorithmica, to appear.
• 5: Ricardo A. Baeza-Yates , Joseph C. Culberson , Gregory J. E. Rawlins, Searching in the plane, Information and Computation, v.106 n.2, p.234-252, Oct. 1993 [doi>10.1006/inco.1993.1054]
• 6: Avrim Blum , Prasad Chalasani , Don Coppersmith , Bill Pulleyblank , Prabhakar Raghavan , Madhu Sudan, The minimum latency problem, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.163-171, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195125]
• 7: L.D. Bodin, B.L. Golden, A. Assad, M.O. Ball, Routing and scheduling of vehicles and crews: the state of the art, Comput. Oper. Res. 10 (1983) 63-211.
• 8: Moses Charikar , Balaji Raghavachari, The Finite Capacity Dial-A-Ride Problem, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.458, November 08-11, 1998
• 9: E. Feuerstein, M. Seleson, A. Strejilevich de Loma, On-line multi-threaded dial a ride problems, manuscript, 1999.
• 10: Greg N. Frederickson , D. J. Guan, Preemptive ensemble motion planning on a tree, SIAM Journal on Computing, v.21 n.6, p.1130-1152, Dec. 1992 [doi>10.1137/0221066]
• 11: Greg N. Frederickson , D. J. Guan, Nonpreemptive ensemble motion planning on a tree, Journal of Algorithms, v.15 n.1, p.29-60, July 1993 [doi>10.1006/jagm.1993.1029]
• 12: G.N. Frederickson, M.S. Hecht, C.E. Kim, Approximation algorithms for some routing problems, SIAM J. Comput. 7 (1978) 178-193.
• 13: D. J. Guan, Routing a vehicle of capacity greater than one, Discrete Applied Mathematics, v.81 n.1-3, p.41-57, Jan. 15, 1998 [doi>10.1016/S0166-218X(97)00074-7]
• 14: R.M. Karp, Two combinatorial problems associated with external sorting, Combinatorial Algorithms, Courant Computer Science Symp., Algorithmics Press, New York, 1972, pp. 17-29.
• 15: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, Sequencing and scheduling: algorithms and complexity, in: Handbooks in Operations Research and Management Science, Vol. 4, Elsevier Science Publishers, Amsterdam, 1993 (Chapter 9).
• 16: J.K. Lenstra, W.E. de Paepe, J. Sgall, R.A. Sitters, L. Stougie, Classification of dial-a-ride problems, Manuscript.
• 17: W.E. de Paepe, Computer-aided complexity classification of dial-a-ride problems, M.Sc. Thesis, University of Amsterdam, 1998.
• 18: Cynthia A. Phillips , Clifford Stein , Joel Wein, Scheduling Jobs that Arrive Over Time (Extended Abstract), Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.86-97, August 16-18, 1995
• 19: M.W.P. Savelsbergh, M. Sol, The general pickup and delivery problem, Transportation Sci. 29 (1995) 17-29.
• 20: David B. Shmoys , Joel Wein , David P. Williamson, Scheduling Parallel Machines On-line, SIAM Journal on Computing, v.24 n.6, p.1313-1331, Dec. 1995 [doi>10.1137/S0097539793248317]
• 21: A. Vestjens, On-line machine scheduling, Ph.D. Thesis, Department of Mathematics and Computing Science, Eindhoven University of Technology, Eindhoven, 1997.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Algorithms, Theory, Verification

Keywords:
competitive analysis, dial-a-ride, on-line optimization