To fill or not to fill
- 15 July 2011
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 7 (3), 1-16
- https://doi.org/10.1145/1978782.1978791
Abstract
In this article we study several routing problems that generalize shortest paths and the traveling salesman problem. We consider a more general model that incorporates the actual cost in terms of gas prices. We have a vehicle with a given tank capacity. We assume that at each vertex gas may be purchased at a certain price. The objective is to find the cheapest route to go from s to t , or the cheapest tour visiting a given set of locations. We show that the problem of finding a cheapest plan to go from s to t can be solved in polynomial time. For most other versions, however, the problem is NP-complete and we develop polynomial-time approximation algorithms for these versions.Keywords
Funding Information
- Division of Computing and Communication Foundations (CCF-0430650CCF-0728839)
This publication has 11 references indexed in Scilit:
- Approximations for minimum and min-max vehicle routing problemsJournal of Algorithms, 2006
- Approximation algorithms for deadline-TSP and vehicle routing with time-windowsPublished by Association for Computing Machinery (ACM) ,2004
- Algorithms for Capacitated Vehicle RoutingSIAM Journal on Computing, 2001
- Resource-constrained geometric network optimizationPublished by Association for Computing Machinery (ACM) ,1998
- New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting SalesmenSIAM Journal on Computing, 1998
- On the Distance Constrained Vehicle Routing ProblemOperations Research, 1992
- The orienteering problemNaval Research Logistics (NRL), 1987
- The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization.Journal of the Operational Research Society, 1986
- Bounds and Heuristics for Capacitated Routing ProblemsMathematics of Operations Research, 1985
- Approximation Algorithms for Some Routing ProblemsSIAM Journal on Computing, 1978