A branch-and-price algorithm for the vehicle routing problem with time windows on a road network

Hamza Ben Ticha (Corresponding author), Nabil Absi, Dominique Feillet, Alain Quilliot, Tom van Woensel

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)

Abstract

Vehicle routing problems (VRP) concern the pickup and/or the delivery of goods from/to customers with vehicles. In the literature, most approaches consider the road network implicitly. Specifically, so-called customer-based graphs are used where nodes represent customers (plus the depot) and arcs represent best paths between customers. This model can affect solution quality when several attributes are defined on road segments (like travel time and distance). To handle that, two approaches are proposed in the literature. The road network can be represented using a multigraph that extends the customer-based graph and where an arc is introduced for every efficient path between two nodes. Alternatively, the problem can be solved on a graph that mimics the original road network. In this paper, we investigate the latter approach. We consider the VRP with time windows (VRPTW) and we develop a branch-and-price scheme. An extensive computational study based on several types of instances is conducted in order to evaluate this approach compared to the multigraph-based approach. As far as we know, our branch-and-price scheme is the first exact method for the VRPTW with the road-network model. Also, our computational study provides the first comparison between the two models: multigraph and road-network.

Original languageEnglish
Pages (from-to)401-417
Number of pages17
JournalNetworks
Volume73
Issue number4
DOIs
Publication statusPublished - 7 May 2019

Keywords

  • branch-and-price
  • multigraph
  • road-network graph
  • vehicle routing problems

Fingerprint Dive into the research topics of 'A branch-and-price algorithm for the vehicle routing problem with time windows on a road network'. Together they form a unique fingerprint.

  • Cite this