Optimization Online


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

Aldair Álvarez (aldair***at***dep.ufscar.br)
Pedro Munari (munari***at***dep.ufscar.br)

Abstract: 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. 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. These results indicate the advantages of using specific algorithms to generate good feasible solutions within an exact method.

Keywords: vehicle routing; multiple deliverymen; hybrid method; branch-price-and-cut; metaheuristics; column generation.

Category 1: Applications -- OR and Management Sciences (Transportation )

Category 2: Combinatorial Optimization (Other )

Citation: Industrial Engineering Department, Federal University of São Carlos, Rodovia Washington Luís - Km 235, CEP: 13565-905, São Carlos-SP, Brazil

Download: [PDF]

Entry Submitted: 06/21/2016
Entry Accepted: 06/21/2016
Entry Last Modified: 12/30/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society