A Pricing Algorithm for the Vehicle Routing Problem with Soft Time Windows

Federico Liberatore (), Giovanni Righini () and Matteo Salani ()
Additional contact information
Federico Liberatore: Università degli Studi di Milano
Giovanni Righini: Università degli Studi di Milano
Matteo Salani: École Politechnique Fédérale de Lausanne

Chapter 13 in Innovations in Distribution Logistics, 2009, pp 251-266 from Springer

Abstract: Summary The Vehicle Routing Problem with Soft Time Windows consists in computing a minimum cost set of routes for a fleet of vehicles of limited capacity that must visit a given set of customers with known demand, with the additional feature that each customer expresses a preference about the time at which the visit should occur. If a vehicle serves the customer out of its specified time window, an additional cost is incurred. Here we consider the case with penalties linearly depending on the time windows violation. We present an exact optimization algorithm for the pricing problem which arises when the vehicle routing problem with soft time windows is solved by column generation. The algorithm exploits bi-directional and bounded dynamic programming with decremental state space relaxation.

Keywords: Column Generation; Dynamic Programming Algorithm; Piecewise Linear Function; Vehicle Route Problem; Price Problem (search for similar items in EconPapers)
Date: 2009
References: Add references at CitEc
Citations:

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:lnechp:978-3-540-92944-4_13

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

DOI: 10.1007/978-3-540-92944-4_13

Access Statistics for this chapter

More chapters in Lecture Notes in Economics and Mathematical Systems from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().