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

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

6 Citaten (Scopus)

Samenvatting

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.

Originele taal-2Engels
Pagina's (van-tot)401-417
Aantal pagina's17
TijdschriftNetworks
Volume73
Nummer van het tijdschrift4
DOI's
StatusGepubliceerd - 7 mei 2019

Vingerafdruk Duik in de onderzoeksthema's van 'A branch-and-price algorithm for the vehicle routing problem with time windows on a road network'. Samen vormen ze een unieke vingerafdruk.

Citeer dit