The robust vehicle routing problem with time windows

The robust vehicle routing problem with time windows

0.00 Avg rating0 Votes
Article ID: iaor20127936
Volume: 40
Issue: 3
Start Page Number: 856
End Page Number: 866
Publication Date: Mar 2013
Journal: Computers and Operations Research
Authors: , , , , ,
Keywords: combinatorial optimization, transportation: water
Abstract:

This paper addresses the robust vehicle routing problem with time windows. We are motivated by a problem that arises in maritime transportation where delays are frequent and should be taken into account. Our model only allows routes that are feasible for all values of the travel times in a predetermined uncertainty polytope, which yields a robust optimization problem. We propose two new formulations for the robust problem, each based on a different robust approach. The first formulation extends the well‐known resource inequalities formulation by employing adjustable robust optimization. We propose two techniques, which, using the structure of the problem, allow to reduce significantly the number of extreme points of the uncertainty polytope. The second formulation generalizes a path inequalities formulation to the uncertain context. The uncertainty appears implicitly in this formulation, so that we develop a new cutting plane technique for robust combinatorial optimization problems with complicated constraints. In particular, efficient separation procedures are discussed. We compare the two formulations on a test bed composed of maritime transportation instances. These results show that the solution times are similar for both formulations while being significantly faster than the solutions times of a layered formulation recently proposed for the problem.

Reviews

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