The Generalized Consistent Vehicle Routing Problem

Attila A. Kovacs (), Bruce L. Golden (), Richard F. Hartl () and Sophie N. Parragh ()
Additional contact information
Attila A. Kovacs: Department of Business Administration, University of Vienna, A-1090 Vienna, Austria
Bruce L. Golden: Robert H. Smith School of Business, University of Maryland, College Park, Maryland 20742
Richard F. Hartl: Department of Business Administration, University of Vienna, A-1090 Vienna, Austria
Sophie N. Parragh: Department of Business Administration, University of Vienna, A-1090 Vienna, Austria

Transportation Science, 2015, vol. 49, issue 4, 796-816

Abstract: The consistent vehicle routing problem (ConVRP) takes customer satisfaction into account by assigning one driver to a customer and by bounding the variation in the arrival times over a given planning horizon. These requirements may be too restrictive in some applications. In the generalized ConVRP (GenConVRP), each customer is visited by a limited number of drivers and the variation in the arrival times is penalized in the objective function. The vehicle departure times may be adjusted to obtain stable arrival times. Additionally, customers are associated with AM/PM time windows. In contrast to previous work on the ConVRP, we do not use the template concept to generate routing plans. Our approach is based on a flexible large neighborhood search that is applied to the entire solution. Several destroy and repair heuristics have been designed to remove customers from the routes and to reinsert them at better positions. Arrival time consistency is improved by a simple 2-opt operator that reverses parts of particular routes.A computational study is performed on ConVRP benchmark instances and on new instances generated for the generalized problem. The proposed algorithm performs well on different variants of the ConVRP. It outperforms template-based approaches in terms of travel cost and time consistency. For the GenConVRP, we experiment with different input parameters and examine the trade-off between travel cost and customer satisfaction. Remarkable cost savings can be obtained by allowing more than one driver per customer.

Keywords: vehicle routing; periodic distribution problems; large neighborhood search; metaheuristics (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (35)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2014.0529 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:49:y:2015:i:4:p:796-816

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().