skip to main content
10.1145/1007352.1007385acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article

Approximation algorithms for deadline-TSP and vehicle routing with time-windows

Published: 13 June 2004 Publication History

Abstract

Given a metric space G on n nodes, with a start node r and deadlines D(v) for each vertex v, we consider the Deadline-TSP problem of finding a path starting at r that visits as many nodes as possible by their deadlines. We also consider the more general Vehicle Routing with Time-Windows problem, in which each node v also has a release-time R(v) and the goal is to visit as many nodes as possible within their "time-windows" [R(v),D(v)]. No good approximations were known previously for these problems on general metric spaces. We give an O(logn) approximation algorithm for Deadline-TSP, and extend this algorithm to an O(log2n) approximation for the Time-Window problem. We also give a bicriteria approximation algorithm for both problems: Given an ε>0, our algorithm produces a (1/ε) approximation, while exceeding the deadlines by a factor of 1+ε. We use as a subroutine for these results a constant-factor approximation that we develop for a generalization of the orienteering problem in which both the start and the end nodes of the path are fixed. In the process, we give a 3-approximation to the orienteering problem, improving on the previously best known 4-approximation of [6].

References

[1]
Bibliography on vehicle routing, http://people. freenet. de/Emden-Weinert/VRP. html.]]
[2]
A. Allahverdi, J. Gupta, and T. Aldowaisan. A review of scheduling research involving setup considerations. Omega, Int. Journal of Management Science 27:219--239, 1999.]]
[3]
E. M. Arkin, J. S. B. Mitchell, and G. Narasimhan. Resource-constrained geometric network optimization. In Symposium on Computational Geometry pages 307--316, 1998.]]
[4]
B. Awerbuch, Y. Azar, A. Blum, and S. Vempala. Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. Siam J. Computing 28(1):254--262, 1999.]]
[5]
R. Bar-Yehuda, G. Even, and S. Shahar. On approximating a geometric prize-collecting traveling salesman. In Proceedings of the European Symposium on Algorithms 2003.]]
[6]
A. Blum, S. Chawla, D. Karger, T. Lane, A. Meyerson, and M. Minkoff. Approximation algorithms for orienteering and discounted-reward tsp. In Proceedings of the 44th Foundations of Computer Science 2003.]]
[7]
J. Brun and P. Downey. Complexity of task sequencing with deadlines, set-up times and changeover costs. SIAM Journal on Computing 7(4):393--404, 1978.]]
[8]
C. Chekuri and A. Kumar. Maximum coverage problem with group budget constraints and applications, Manuscript, 2004.]]
[9]
M. Desrochers, J. Desrosiers, and M. Solomon. A new optimization algorithm for the vehicle routing problem with time windows. Operations Research 40:342--354, 1992.]]
[10]
M. Desrochers, J. Lenstra, M. Savelsbergh, and F. Soumis. Vehicle routing with time windows: optimization and appr ximation. In B. L. Golden, A. A. Assad (eds. ). Vehicle Routing: Methods and Studies, North-Holland, Amsterdam pages 65--84, 1988.]]
[11]
B. Golden, L. Levy, and R. Vohra. The orienteering problem. Naval Research Logistics 34:307--318, 1987.]]
[12]
M. Gravel, W. Price, and C. Gagn. Scheduling jobs in a alcan aluminium factory using a genetic algorithm. International Journal of Production Research 38(13):3031--3041, 2000.]]
[13]
C. Jordan. A two-phase genetic algorithm to solve variants of the batch sequencing problem. International Journal of Production Research (UK) 36(3):745--760, 1998.]]
[14]
M. Kantor and M. Rosenwein. The orienteering problem with time windows. Journal of the Operational Research Society 43:629--635,1992.]]
[15]
Y. Karun and H. Nagamochi. A 2-approximation algorithm for the multi-vehicle scheduling problem on a path with release and handling times. In Proceedings of the European Symposium on Algorithms pages 218--229, 2001.]]
[16]
A. Kolen, A. R. Kan, and H. Trienekens. Vehicle routing with time windows. Operations Research 35:266--273, 1987.]]
[17]
M. Savelsbergh. Local search for routing problems with time windows. Annals of Operations Research 4: 285--305, 1985.]]
[18]
K. Tan, L. Lee, and K. Zhu. Heuristic methods for vehicle routing problem with time windows. In Proceedings of the 6th AI and Math 2000.]]
[19]
S. Thangiah. Vehicle Routing with Time Windows using Genetic Algorithms, Application Handbook of Genetic Algorithms: New Frontiers, Volume II. Lance Chambers (Ed. ) CRC Press, 1995.]]
[20]
S. R. Thangiah, I. H. Osman, R. Vinayagamoorthy, and T. Sun. Algorithms for the vehicle routing problems with time deadlines. American Journal of Mathematical and Management Sciences 13(3&4):323--355, 1993.]]
[21]
J. Tsitsiklis. Special cases of traveling salesman and repairman problems with time windows. Networks 22: 263--282, 1992.]]
[22]
J. Wisner and S. Siferd. A survey of u. s. manufacturing practices in make-to-order machine shops. Production and Inventory Management Journal 1:1--7, 1995.]]
[23]
W. Yang and C. Liao. Survey of scheduling research involving setup times. International Journal of Systems Science 30(2): 143--155, 1999.]]

Cited By

View all
  • (2025)Unmanned Aerial Vehicle-Enabled Aerial Radio Environment Map Construction: A Multi-Stage Approach to Data Sampling and Path PlanningDrones10.3390/drones90200819:2(81)Online publication date: 21-Jan-2025
  • (2025)Budget-Constrained Digital Twin Synchronization and Its Application on Fidelity-Aware Queries in Edge ComputingIEEE Transactions on Mobile Computing10.1109/TMC.2024.345535724:1(165-182)Online publication date: Jan-2025
  • (2025)Orienteering (with Time Windows) on Restricted Graph ClassesSOFSEM 2025: Theory and Practice of Computer Science10.1007/978-3-031-82670-2_12(151-165)Online publication date: 7-Feb-2025
  • Show More Cited By

Index Terms

  1. Approximation algorithms for deadline-TSP and vehicle routing with time-windows

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing
    June 2004
    660 pages
    ISBN:1581138520
    DOI:10.1145/1007352
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 13 June 2004

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. approximation algorithms
    2. orienteering
    3. traveling salesman problem
    4. vehicle routing

    Qualifiers

    • Article

    Conference

    STOC04
    Sponsor:
    STOC04: Symposium of Theory of Computing 2004
    June 13 - 16, 2004
    IL, Chicago, USA

    Acceptance Rates

    Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

    Upcoming Conference

    STOC '25
    57th Annual ACM Symposium on Theory of Computing (STOC 2025)
    June 23 - 27, 2025
    Prague , Czech Republic

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)92
    • Downloads (Last 6 weeks)6
    Reflects downloads up to 13 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2025)Unmanned Aerial Vehicle-Enabled Aerial Radio Environment Map Construction: A Multi-Stage Approach to Data Sampling and Path PlanningDrones10.3390/drones90200819:2(81)Online publication date: 21-Jan-2025
    • (2025)Budget-Constrained Digital Twin Synchronization and Its Application on Fidelity-Aware Queries in Edge ComputingIEEE Transactions on Mobile Computing10.1109/TMC.2024.345535724:1(165-182)Online publication date: Jan-2025
    • (2025)Orienteering (with Time Windows) on Restricted Graph ClassesSOFSEM 2025: Theory and Practice of Computer Science10.1007/978-3-031-82670-2_12(151-165)Online publication date: 7-Feb-2025
    • (2024)Towards Maximizing Coverage of Targets for WRSNs by Multiple Chargers SchedulingIEEE Transactions on Mobile Computing10.1109/TMC.2024.336905423:10(9959-9970)Online publication date: Oct-2024
    • (2024)CSCT: Charging Scheduling for Maximizing Coverage of Targets in WRSNsIEEE Transactions on Computational Social Systems10.1109/TCSS.2022.316978011:3(3049-3059)Online publication date: Jun-2024
    • (2024)Collect Spatiotemporally Correlated Data in IoT Networks With an Energy-Constrained UAVIEEE Internet of Things Journal10.1109/JIOT.2024.337029511:11(20486-20498)Online publication date: 1-Jun-2024
    • (2024)A two-stage budget-feasible mechanism for mobile crowdsensing based on maximum user revenue routingFuture Generation Computer Systems10.1016/j.future.2024.06.059161:C(201-213)Online publication date: 1-Dec-2024
    • (2024)Vehicle routing with time-dependent travel times: Theory, practice, and benchmarksDiscrete Optimization10.1016/j.disopt.2024.10084853(100848)Online publication date: Aug-2024
    • (2023)A Data-driven Approach to Improve Artisans' Productivity in Distributed Supply ChainsSSRN Electronic Journal10.2139/ssrn.4531090Online publication date: 2023
    • (2023)Data Collection Maximization in IoT-Sensor Networks via an Energy-Constrained UAVIEEE Transactions on Mobile Computing10.1109/TMC.2021.308497222:1(159-174)Online publication date: 1-Jan-2023
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media