Loading…

An exact hybrid method for the vehicle routing problem with time windows and multiple deliverymen

•We study the vehicle routing problem with time windows and multiple deliverymen.•We propose an exact hybrid method to solve the problem.•A branch-price-and-cut algorithm is combined with two metaheuristic approaches.•Computational results are reported on problem instances from the literature. The v...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2017-07, Vol.83, p.1-12
Main Authors: Alvarez, Aldair, Munari, Pedro
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•We study the vehicle routing problem with time windows and multiple deliverymen.•We propose an exact hybrid method to solve the problem.•A branch-price-and-cut algorithm is combined with two metaheuristic approaches.•Computational results are reported on problem instances from the literature. The vehicle routing problem with time windows and multiple deliverymen (VRPTWMD) is a variant of the vehicle routing problem with time windows in which service times at customers depend on the number of deliverymen assigned to the route that serves them. In particular, a larger number of deliverymen in a route leads to shorter service times. Hence, in addition to the usual routing and scheduling decisions, the crew size for each route is also an endogenous decision. This problem is commonly faced by companies that deliver goods to customers located in busy urban areas, a situation that requires nearby customers to be grouped in advance so that the deliverymen can serve all customers in a group during one vehicle stop. Consequently, service times can be relatively long compared to travel times, which complicates serving all scheduled customers during regular work hours. In this paper, we propose a hybrid method for the VRPTWMD, combining a branch-price-and-cut (BPC) algorithm with two metaheuristic approaches. We present a wide variety of computational results showing that the proposed hybrid approach outperforms the BPC algorithm used as standalone method in terms of both solution quality and running time, in some classes of problem instances from the literature. These results indicate the advantages of using specific algorithms to generate good feasible solutions within an exact method.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2017.02.001