Graph Sparsification for the Vehicle Routing Problem with Time Windows

Christian Doppstadt (), Michael Schneider (), Andreas Stenger (), Bastian Sand (), Daniele Vigo () and Michael Schwind ()
Additional contact information
Christian Doppstadt: Goethe University Frankfurt
Michael Schneider: University of Kaiserslautern
Andreas Stenger: Goethe University Frankfurt
Bastian Sand: University of Kaiserslautern
Daniele Vigo: University of Bologna
Michael Schwind: Goethe University Frankfurt

A chapter in Operations Research Proceedings 2010, 2011, pp 227-232 from Springer

Abstract: Abstract The Vehicle Routing Problem with Time Windows (VRPTW) is one of the most important and widely studied NP-hard combinatorial optimization problems in the operations research literature. The problem calls for the determination of a minimum-cost set of routes for a fleet of identical vehicles with limited capacities to serve a set of customers that have a given demand and an associated time window in which they can be visited. Due to its computational complexity, VRPTW can only be solved by exact methods for instances of moderate size [2]. However, a large number of successful metaheuristic solution methods have been proposed, which are able to produce high-quality solutions for reasonably-sized instances in limited time. For an extensive review, the reader is referred to [5, 3].

Keywords: Time Window; Vehicle Route Problem; Sparse Graph; Problem Graph; Vehicle Route Problem With Time Window (search for similar items in EconPapers)
Date: 2011
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-642-20009-0_36

Ordering information: This item can be ordered from
http://www.springer.com/9783642200090

DOI: 10.1007/978-3-642-20009-0_36

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().