Optimization Online


The robust vehicle routing problem with time windows

Agostinho Agra(aagra***at***ua.pt)
Marielle Christiansen(marielle.christiansen***at***iot.ntnu.no)
Rosa Figueiredo(rosa.figueiredo***at***ua.pt)
Lars M. Hvattum(lars.m.hvattum***at***iot.ntnu.no)
Michael Poss(mjposs***at***gmail.com)
Cristina Requejo(crequejo***at***ua.pt)

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 di erent robust approach. The fi rst 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 signi cantly 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 signi cantly faster than the solutions times of a layered formulation recently proposed for the problem.

Keywords: robust optimization; uncertainty polytope; vehicle routing problem; time windows; dynamic programming.

Category 1: Robust Optimization

Category 2: Applications -- OR and Management Sciences (Transportation )

Citation: Accepted in Computers & OR

Download: [PDF]

Entry Submitted: 10/02/2012
Entry Accepted: 10/02/2012
Entry Last Modified: 10/02/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society