An iterative re-optimization framework for the dynamic vehicle routing problem with roaming delivery locations

Özbaygın, Gizem and Savelsbergh, Martin (2019) An iterative re-optimization framework for the dynamic vehicle routing problem with roaming delivery locations. Transportation Research Part B: Methodological, 128 . pp. 207-235. ISSN 0191-2615 (Print) 1879-2367 (Online)

This is the latest version of this item.

Full text not available from this repository. (Request a copy)

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 methodology 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.
Item Type: Article
Uncontrolled Keywords: Branch-and-price; Dynamic vehicle routing; Iterative re-optimization; Roaming delivery locations
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: Gizem Özbaygın
Date Deposited: 25 Jul 2023 22:38
Last Modified: 25 Jul 2023 22:38
URI: https://research.sabanciuniv.edu/id/eprint/46269

Available Versions of this Item

Actions (login required)

View Item
View Item