The Vehicle Rescheduling Problem

Remy Spliet, Adriana Gabor and Rommert Dekker

No EI 2009-43, Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute

Abstract: The capacitated vehicle routing problem is to find a routing schedule describing the order in which geographically dispersed customers are visited to satisfy demand by supplying goods stored at the depot, such that the traveling costs are minimized. In many practical applications, a long term routing schedule has to be made for operational purposes, often based on average demand estimates. When demand substantially differs, constructing a new schedule is beneficial. The vehicle rescheduling problem is to find a new schedule that not only minimizes the total traveling costs but also minimizes the costs of deviating from the original schedule. In this paper two mathematical programming formulations of the rescheduling problem are presented as well as two heuristic methods, a two-phase heuristic and a modified savings heuristic. Computational and analytical results show that for sufficiently high deviation costs, the two-phase heuristic generates a schedule that is on average close to optimal or even guaranteed optimal, for all considered problem instances. The modified savings heuristic generates schedules of constant quality, however the two-phase heuristic produces schedules that are on average closer to the optimum.

Keywords: operational planning; vehicle rescheduling problem; vehicle routing (search for similar items in EconPapers)
Date: 2009-11-26
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://repub.eur.nl/pub/17350/EI2009-43.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ems:eureir:17350

Access Statistics for this paper

More papers in Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute Contact information at EDIRC.
Bibliographic data for series maintained by RePub ( this e-mail address is bad, please contact ).