IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v40y2006i2p200-210.html
   My bibliography  Save this article

Online Routing Problems: Value of Advanced Information as Improved Competitive Ratios

Author

Listed:
  • Patrick Jaillet

    (Department of Civil and Environmental Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

  • Michael R. Wagner

    (Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

Abstract

We consider online versions of the traveling salesman problem (TSP) and traveling repairman problem (TRP) where instances are not known in advance. Cities (points) to be visited are revealed over time, while the server is en route serving previously released requests. These problems are known in the literature as the online TSP (TRP, respectively). The corresponding offline problems are the TSP (TRP) with release dates, problems where each point has to be visited at or after a given release date. In the current literature, the assumption is that a request becomes known at the time of its release date. In this paper we introduce the notion of a request’s disclosure date , the time when a city’s location and release date are revealed to the server. In a variety of disclosure date scenarios and metric spaces, we give new online algorithms and quantify the value of this advanced information in the form of improved competitive ratios. We also provide a general result on polynomial-time online algorithms for the online TSP.

Suggested Citation

  • Patrick Jaillet & Michael R. Wagner, 2006. "Online Routing Problems: Value of Advanced Information as Improved Competitive Ratios," Transportation Science, INFORMS, vol. 40(2), pages 200-210, May.
    • Handle: RePEc:inm:ortrsc:v:40:y:2006:i:2:p:200-210
    DOI: 10.1287/trsc.1060.0147
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/trsc.1060.0147
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.1060.0147?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Leslie A. Hall & Andreas S. Schulz & David B. Shmoys & Joel Wein, 1997. "Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms," Mathematics of Operations Research, INFORMS, vol. 22(3), pages 513-544, August.
    2. Michiel Blom & Sven O. Krumke & Willem E. de Paepe & Leen Stougie, 2001. "The Online TSP Against Fair Adversaries," INFORMS Journal on Computing, INFORMS, vol. 13(2), pages 138-148, May.
    3. Harilaos N. Psaraftis & Marius M. Solomon & Thomas L. Magnanti & Tai-Up Kim, 1990. "Routing and Scheduling on a Shoreline with Release Times," Management Science, INFORMS, vol. 36(2), pages 212-223, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Srour, F.J. & Zuidwijk, R.A., 2008. "How Much is Location Information Worth? A Competitive Analysis of the Online Traveling Salesman Problem with Two Disclosure Dates," ERIM Report Series Research in Management ERS-2008-075-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    2. Rolf H. Möhring & Andreas S. Schulz & Frederik Stork & Marc Uetz, 2003. "Solving Project Scheduling Problems by Minimum Cut Computations," Management Science, INFORMS, vol. 49(3), pages 330-350, March.
    3. Büsing, Christina & Goetzmann, Kai-Simon & Matuschke, Jannik & Stiller, Sebastian, 2017. "Reference points and approximation algorithms in multicriteria discrete optimization," European Journal of Operational Research, Elsevier, vol. 260(3), pages 829-840.
    4. Yuanxiao Wu & Xiwen Lu, 0. "Improved algorithms for single vehicle scheduling on tree/cycle networks," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-16.
    5. Martin Skutella & Maxim Sviridenko & Marc Uetz, 2016. "Unrelated Machine Scheduling with Stochastic Processing Times," Mathematics of Operations Research, INFORMS, vol. 41(3), pages 851-864, August.
    6. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    7. Dimitris Fotakis & Jannik Matuschke & Orestis Papadigenopoulos, 2023. "Malleable scheduling beyond identical machines," Journal of Scheduling, Springer, vol. 26(5), pages 425-442, October.
    8. Dengpan Liu & Sumit Sarkar & Chelliah Sriskandarajah, 2010. "Resource Allocation Policies for Personalization in Content Delivery Sites," Information Systems Research, INFORMS, vol. 21(2), pages 227-248, June.
    9. Han Hoogeveen & Petra Schuurman & Gerhard J. Woeginger, 2001. "Non-Approximability Results for Scheduling Problems with Minsum Criteria," INFORMS Journal on Computing, INFORMS, vol. 13(2), pages 157-168, May.
    10. J.M. van den Akker & C.A.J. Hurkens & M.W.P. Savelsbergh, 2000. "Time-Indexed Formulations for Machine Scheduling Problems: Column Generation," INFORMS Journal on Computing, INFORMS, vol. 12(2), pages 111-124, May.
    11. Jin Xu & Natarajan Gautam, 2020. "On competitive analysis for polling systems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 67(6), pages 404-419, September.
    12. Adam Kasperski & Paweł Zieliński, 2019. "Risk-averse single machine scheduling: complexity and approximation," Journal of Scheduling, Springer, vol. 22(5), pages 567-580, October.
    13. Patrick Jaillet & Michael R. Wagner, 2008. "Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses," Operations Research, INFORMS, vol. 56(3), pages 745-757, June.
    14. Bo Chen & Xiaotie Deng & Wenan Zang, 2004. "On-Line Scheduling a Batch Processing System to Minimize Total Weighted Job Completion Time," Journal of Combinatorial Optimization, Springer, vol. 8(1), pages 85-95, March.
    15. Devansh Jalota & Dario Paccagnan & Maximilian Schiffer & Marco Pavone, 2023. "Online Routing Over Parallel Networks: Deterministic Limits and Data-driven Enhancements," INFORMS Journal on Computing, INFORMS, vol. 35(3), pages 560-577, May.
    16. Tjark Vredeveld & Cor Hurkens, 2002. "Experimental Comparison of Approximation Algorithms for Scheduling Unrelated Parallel Machines," INFORMS Journal on Computing, INFORMS, vol. 14(2), pages 175-189, May.
    17. Zhi Pei & Mingzhong Wan & Ziteng Wang, 2020. "A new approximation algorithm for unrelated parallel machine scheduling with release dates," Annals of Operations Research, Springer, vol. 285(1), pages 397-425, February.
    18. Hao Yan & Peihai Liu & Xiwen Lu, 2023. "Vehicle scheduling problems with two agents on a line," Journal of Combinatorial Optimization, Springer, vol. 45(1), pages 1-18, January.
    19. Joseph Leung & Haibing Li & Michael Pinedo, 2008. "Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time," Annals of Operations Research, Springer, vol. 159(1), pages 107-123, March.
    20. Sitters, R.A., 2009. "Efficient algorithms for average completion time scheduling," Serie Research Memoranda 0058, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ortrsc:v:40:y:2006:i:2:p:200-210. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.