A template‐based adaptive large neighborhood search for the consistent vehicle routing problem

Journal Article


The importance of customer satisfaction was identified by many industries as a key factor of competitive advantage. So, for companies in the small package shipping industry, it can be reasonable to increase the service quality even at the expense of transportation cost to gain customer loyalty. These companies noticed that customer satisfaction can be increased by providing consistent service in the form of visiting customers with the same driver at approximately the same time of the day over a certain time period. Motivated by this real‐world problem, the consistent vehicle routing problem (ConVRP) combines traditional vehicle routing constraints with the requirements for service consistency. This article presents a fast solution method called template‐based adaptive large neighborhood search for the described problem. Compared to state‐of‐the‐art heuristics, the developed algorithm is highly competitive on the available benchmark instances. Additionally, new test instances are provided. These seem to be more challenging due to the variation of different model parameters and consequently help to identify interesting effects. Finally, a relaxed variant of the original ConVRP is presented. In this variant, the departure times from the depot can be delayed to adjust the service times of the customers. Experiments show that allowing later departure times considerably improves the solution quality under tight consistency requirements. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(1), 60–81 2014

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.