Time-dependent vehicle routing problem with path flexibility

Y. Huang, L. Zhao, T. van Woensel, J.-P. Gross

Research output: Contribution to journalArticleAcademicpeer-review

48 Citations (Scopus)
5 Downloads (Pure)

Abstract

Conventionally, vehicle routing problems are defined on a network in which the customer locations and arcs are given. Typically, these arcs somehow represent the distances or expected travel time derived from the underlying road network. When executed, the quality of the solutions obtained from the vehicle routing problem depends largely on the quality of the road network representation. This paper explicitly considers path selection in the road network as an integrated decision in the time-dependent vehicle routing problem, denoted as path flexibility (PF). This means that any arc between two customer nodes has multiple corresponding paths in the road network (geographical graph). Hence, the decisions to make are involving not only the routing decision but also the path selection decision depending upon the departure time at the customers and the congestion levels in the relevant road network. The corresponding routing problem is a time-dependent vehicle routing problem with path flexibility (TDVRP–PF). We formulate the TDVRP–PF models under deterministic and stochastic traffic conditions. We derive important insights, relationships, and solution structures. Based on a representative testbed of instances (inspired on the road network of Beijing), significant savings are obtained in terms of cost and fuel consumption, by explicitly considering path flexibility. Having both path flexibility and time-dependent travel time seems to be a good representation of a wide range of stochasticity and dynamics in the travel time, and path flexibility serves as a natural recourse under stochastic conditions. Exploiting this observation, we employ a Route-Path approximation method generating near-optimal solutions for the TDVRP–PF under stochastic traffic conditions.
Original languageEnglish
Pages (from-to)169-175
Number of pages27
JournalTransportation Research. Part B: Methodological
Volume95
DOIs
Publication statusPublished - Jan 2017

Fingerprint

Vehicle routing
flexibility
road network
Travel time
customer
travel
Testbeds
Fuel consumption
traffic
time
recourse
savings
Costs

Cite this

@article{c7fd61e6b3a64ba29c41efc4cf2256b9,
title = "Time-dependent vehicle routing problem with path flexibility",
abstract = "Conventionally, vehicle routing problems are defined on a network in which the customer locations and arcs are given. Typically, these arcs somehow represent the distances or expected travel time derived from the underlying road network. When executed, the quality of the solutions obtained from the vehicle routing problem depends largely on the quality of the road network representation. This paper explicitly considers path selection in the road network as an integrated decision in the time-dependent vehicle routing problem, denoted as path flexibility (PF). This means that any arc between two customer nodes has multiple corresponding paths in the road network (geographical graph). Hence, the decisions to make are involving not only the routing decision but also the path selection decision depending upon the departure time at the customers and the congestion levels in the relevant road network. The corresponding routing problem is a time-dependent vehicle routing problem with path flexibility (TDVRP–PF). We formulate the TDVRP–PF models under deterministic and stochastic traffic conditions. We derive important insights, relationships, and solution structures. Based on a representative testbed of instances (inspired on the road network of Beijing), significant savings are obtained in terms of cost and fuel consumption, by explicitly considering path flexibility. Having both path flexibility and time-dependent travel time seems to be a good representation of a wide range of stochasticity and dynamics in the travel time, and path flexibility serves as a natural recourse under stochastic conditions. Exploiting this observation, we employ a Route-Path approximation method generating near-optimal solutions for the TDVRP–PF under stochastic traffic conditions.",
author = "Y. Huang and L. Zhao and {van Woensel}, T. and J.-P. Gross",
year = "2017",
month = "1",
doi = "10.1016/j.trb.2016.10.013",
language = "English",
volume = "95",
pages = "169--175",
journal = "Transportation Research. Part B: Methodological",
issn = "0191-2615",
publisher = "Elsevier",

}

Time-dependent vehicle routing problem with path flexibility. / Huang, Y.; Zhao, L.; van Woensel, T.; Gross, J.-P.

In: Transportation Research. Part B: Methodological, Vol. 95, 01.2017, p. 169-175.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Time-dependent vehicle routing problem with path flexibility

AU - Huang, Y.

AU - Zhao, L.

AU - van Woensel, T.

AU - Gross, J.-P.

PY - 2017/1

Y1 - 2017/1

N2 - Conventionally, vehicle routing problems are defined on a network in which the customer locations and arcs are given. Typically, these arcs somehow represent the distances or expected travel time derived from the underlying road network. When executed, the quality of the solutions obtained from the vehicle routing problem depends largely on the quality of the road network representation. This paper explicitly considers path selection in the road network as an integrated decision in the time-dependent vehicle routing problem, denoted as path flexibility (PF). This means that any arc between two customer nodes has multiple corresponding paths in the road network (geographical graph). Hence, the decisions to make are involving not only the routing decision but also the path selection decision depending upon the departure time at the customers and the congestion levels in the relevant road network. The corresponding routing problem is a time-dependent vehicle routing problem with path flexibility (TDVRP–PF). We formulate the TDVRP–PF models under deterministic and stochastic traffic conditions. We derive important insights, relationships, and solution structures. Based on a representative testbed of instances (inspired on the road network of Beijing), significant savings are obtained in terms of cost and fuel consumption, by explicitly considering path flexibility. Having both path flexibility and time-dependent travel time seems to be a good representation of a wide range of stochasticity and dynamics in the travel time, and path flexibility serves as a natural recourse under stochastic conditions. Exploiting this observation, we employ a Route-Path approximation method generating near-optimal solutions for the TDVRP–PF under stochastic traffic conditions.

AB - Conventionally, vehicle routing problems are defined on a network in which the customer locations and arcs are given. Typically, these arcs somehow represent the distances or expected travel time derived from the underlying road network. When executed, the quality of the solutions obtained from the vehicle routing problem depends largely on the quality of the road network representation. This paper explicitly considers path selection in the road network as an integrated decision in the time-dependent vehicle routing problem, denoted as path flexibility (PF). This means that any arc between two customer nodes has multiple corresponding paths in the road network (geographical graph). Hence, the decisions to make are involving not only the routing decision but also the path selection decision depending upon the departure time at the customers and the congestion levels in the relevant road network. The corresponding routing problem is a time-dependent vehicle routing problem with path flexibility (TDVRP–PF). We formulate the TDVRP–PF models under deterministic and stochastic traffic conditions. We derive important insights, relationships, and solution structures. Based on a representative testbed of instances (inspired on the road network of Beijing), significant savings are obtained in terms of cost and fuel consumption, by explicitly considering path flexibility. Having both path flexibility and time-dependent travel time seems to be a good representation of a wide range of stochasticity and dynamics in the travel time, and path flexibility serves as a natural recourse under stochastic conditions. Exploiting this observation, we employ a Route-Path approximation method generating near-optimal solutions for the TDVRP–PF under stochastic traffic conditions.

U2 - 10.1016/j.trb.2016.10.013

DO - 10.1016/j.trb.2016.10.013

M3 - Article

VL - 95

SP - 169

EP - 175

JO - Transportation Research. Part B: Methodological

JF - Transportation Research. Part B: Methodological

SN - 0191-2615

ER -