Title: Solving vehicle routing problems with asymmetric costs and heterogeneous fleets

Authors: Rosa Herrero; Alejandro Rodríguez; José Cáceres-Cruz; Angel A. Juan

Addresses: Telecommunications and Systems Engineering Department, Autonomous University of Barcelona, Edifici Q, 08193 Bellaterra, Cerdanyola del Vallès, Spain ' Departamento de Organización de Empresas, Universitat Politècnica de València, Pza. Ferrándiz i Carbonell 2, 03801 Alcoi, Spain ' Computer Science Department, IN3-Open University of Catalonia, Roc Boronat, 117 – 08018 Barcelona, Spain ' Computer Science Department, IN3-Open University of Catalonia, Roc Boronat, 117 – 08018 Barcelona, Spain

Abstract: The vehicle routing problem (VRP) is a flourishing research area with clear applications to real-life distribution companies. However, most VRP-related academic articles assume the existence of a homogeneous fleet of vehicles and/or a symmetric cost matrix. These assumptions are not always reasonable in real-life scenarios. To contribute in closing this gap between theory and practice, we propose a hybrid methodology for solving the asymmetric and heterogeneous vehicle routing problem (AHVRP). In our approach, we consider: 1) different types of vehicle loading capacities (heterogeneous fleets); 2) asymmetric distance-based costs. The proposed approach combines a randomised version of a well-known savings heuristic with several local searches specifically adapted to deal with the asymmetric nature of costs. A computational experiment allows us to discuss the efficiency of our approach and also to analyse how routing costs vary when slight departures from the homogeneous fleet assumption are considered.

Keywords: vehicle routing problem; VRP; heterogeneous fleets; asymmetric costs; randomised algorithms; vehicle loading capacities; distance-based costs; routing costs.

DOI: 10.1504/IJAOM.2014.059620

International Journal of Advanced Operations Management, 2014 Vol.6 No.1, pp.58 - 80

Received: 16 Mar 2013
Accepted: 29 Jun 2013
Published online: 02 Jul 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article