Optimization Online


An Iterative Re-optimization Framework for the Dynamic Vehicle Routing Problem with Roaming Delivery Locations

Gizem Ozbaygin(ozbaygin***at***sabanciuniv.edu)
Martin Savelsbergh(martin.savelsbergh***at***isye.gatech.edu)

Abstract: Branch-and-price has established itself as an effective solution methodology for a wide variety of planning problems. We investigate its potential as a solution method- ology for solving operational problems. Specifically, we explore its potential in the context of a dynamic variant of the vehicle routing problem with roaming delivery locations, in which customer itineraries may change during the execution of a planned delivery schedule, which, in turn, may cause the planned delivery schedule to become suboptimal or even infeasible. We propose an iterative solution framework in which an active delivery schedule is re-optimized whenever a customer itinerary update is revealed. We use a branch-and-price algorithm for solving the planning problem (to obtain an initial delivery schedule) as well as the re-optimization problems (to obtain modified delivery schedules). As the re-optimization problems are solved during the execution of the (active) delivery schedule, it is critical to produce solutions quickly. This is accomplished by re-using, suitably modified, columns generated during preceding branch-and-price solves. The results of our computational experiments demonstrate the viability of using branch-and-price for solving operational problems and the benefit (necessity) of re-using information from previous solves.

Keywords: Iterative re-optimization, branch-and-price, dynamic vehicle routing, roaming delivery locations

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

Category 2: Network Optimization

Citation: Ozbaygin, G., and Savelsbergh, M. An Iterative Re-optimization Framework for the Dynamic Vehicle Routing Problem with Roaming Delivery Locations

Download: [PDF]

Entry Submitted: 08/28/2018
Entry Accepted: 08/29/2018
Entry Last Modified: 08/28/2018

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