12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > Pricing routines for vehicle routing with time ...
View graph of relations

Download

« Back

Pricing routines for vehicle routing with time windows on road networks

Research output: Working paper

Published

Publication date2014
Place of publicationLancaster University
PublisherThe Department of Management Science
Number of pages20
Original languageEnglish

Publication series

NameLancaster University Management School Working Paper Series
No.2
Volume2014

Abstract

Several very effective exact algorithms have been developed for vehicle routing problems with time windows. Unfortunately, most of these algorithms cannot be applied to instances that are defined on road networks, because they implicitly assume that the cheapest path between two customers is equal to the quickest path. Garaix and coauthors proposed to tackle this issue by first storing alternative paths in an auxiliary multi-graph, and then using that multi-graph within a branch-and-price algorithm. We show that, if one works with the original road network rather than the multi-graph, then one can solve the pricing subproblem more quickly, in both theory and practice.

Bibliographic note

It has been submitted to "Computers & Operations Research".