Premium
A branch‐and‐price algorithm for the vehicle routing problem with time windows on a road network
Author(s) -
Ben Ticha Hamza,
Absi Nabil,
Feillet Dominique,
Quilliot Alain,
Van Woensel Tom
Publication year - 2019
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21852
Subject(s) - multigraph , vehicle routing problem , computer science , graph , path (computing) , scheme (mathematics) , shortest path problem , routing (electronic design automation) , graph theory , mathematical optimization , algorithm , theoretical computer science , mathematics , computer network , mathematical analysis , combinatorics
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.