A column generation algorithm for the vehicle routing problem with soft time windows

Liberatore, Federico and Righini, Giovanni and Salani, Matteo (2011) A column generation algorithm for the vehicle routing problem with soft time windows. 4OR, 9 (1). pp. 49-82. ISSN 1614-2411

Text pub01_4OR_ExactVRPSTW_LiberatoreRighiniSalani.pdf Restricted to Registered users only Download (548kB)

Abstract

The Vehicle Routing Problem with Time Windows consists of computing a minimum cost set of routes for a fleet of vehicles of limited capacity visiting a given set of customers with known demand, with the additional constraint that each customer must be visited in a specified time window. We consider the case in which time window constraints are relaxed into “soft” constraints, that is penalty terms are added to the solution cost whenever a vehicle serves a customer outside of his time window. We present a branch-and-price algorithm which is the first exact optimization algorithm for this problem.

Item Type:	Scientific journal article, Newspaper article or Magazine article
Uncontrolled Keywords:	Vehicle routing problem;Soft time windows;Column generation;Branch-and-price;Combinatorial optimization
Subjects:	Mathematical sciences > Operational research
Department/unit:	Dipartimento tecnologie innovative > Istituto Dalle Molle di studi sull’intelligenza artificiale USI-SUPSI
Depositing User:	Matteo Salani
Date Deposited:	13 Mar 2014 14:38
Last Modified:	23 May 2016 13:14
URI:	http://repository.supsi.ch/id/eprint/3928

Actions (login required)

View Item