Arcs–states models for the vehicle routing problem with time windows and related problems

Arcs–states models for the vehicle routing problem with time windows and related problems

0.00 Avg rating0 Votes
Article ID: iaor20081787
Country: United Kingdom
Volume: 34
Issue: 4
Start Page Number: 1061
End Page Number: 1084
Publication Date: Apr 2007
Journal: Computers and Operations Research
Authors: ,
Keywords: programming: branch and bound
Abstract:

This paper presents several Arcs–States models that can be applied to numerous vehicle routing problems, one of which is the well-known vehicle routing problem with capacities and time windows. In these models, the variables correspond to the states (i.e. the resource quantities) of the vehicles when they travel through an arc. The LP relaxation of the problem provides a lower bound that can be embedded in a branch and bound algorithm that solves the problem exactly. However, for the pseudo-polynomial number of variables and constraints of our models, column and row generations have to be used. Generally, in a branch and bound algorithm, the lower bound needs to be very efficient to minimize the size of the branch and bound trees as far as possible. One of the models we present, the time-only, relies on a relaxation of the Arcs–States model where a resource is removed from the states in the variables. Although the quality of the bounds decreases, the global resolution time is greatly improved, as illustrated on instances of Solomon's benchmark.

Reviews

Required fields are marked *. Your email address will not be published.