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

2 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

Fingerprint

Vehicle routing
Pickups
Travel time

Keywords

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

Cite this

Ben Ticha, Hamza ; Absi, Nabil ; Feillet, Dominique ; Quilliot, Alain ; van Woensel, Tom. / A branch-and-price algorithm for the vehicle routing problem with time windows on a road network. In: Networks. 2019 ; Vol. 73, No. 4. pp. 401-417.
@article{6cb3030c8ce94211a72f14ff90f258bd,
title = "A branch-and-price algorithm for the vehicle routing problem with time windows on a road network",
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.",
keywords = "branch-and-price, multigraph, road-network graph, vehicle routing problems",
author = "{Ben Ticha}, Hamza and Nabil Absi and Dominique Feillet and Alain Quilliot and {van Woensel}, Tom",
year = "2019",
month = "5",
day = "7",
doi = "10.1002/net.21852",
language = "English",
volume = "73",
pages = "401--417",
journal = "Networks",
issn = "0028-3045",
publisher = "Wiley-Liss Inc.",
number = "4",

}

A branch-and-price algorithm for the vehicle routing problem with time windows on a road network. / Ben Ticha, Hamza (Corresponding author); Absi, Nabil; Feillet, Dominique; Quilliot, Alain; van Woensel, Tom.

In: Networks, Vol. 73, No. 4, 07.05.2019, p. 401-417.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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

AU - Ben Ticha, Hamza

AU - Absi, Nabil

AU - Feillet, Dominique

AU - Quilliot, Alain

AU - van Woensel, Tom

PY - 2019/5/7

Y1 - 2019/5/7

N2 - 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.

AB - 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.

KW - branch-and-price

KW - multigraph

KW - road-network graph

KW - vehicle routing problems

UR - http://www.scopus.com/inward/record.url?scp=85053458114&partnerID=8YFLogxK

U2 - 10.1002/net.21852

DO - 10.1002/net.21852

M3 - Article

AN - SCOPUS:85053458114

VL - 73

SP - 401

EP - 417

JO - Networks

JF - Networks

SN - 0028-3045

IS - 4

ER -