Title: COG: a composite genetic algorithm with local search methods to solve a mixed vehicle routing problem with backhauls

Authors: S.P. Anbuudayasankar, K. Ganesh, Tzong-Ru Lee, K. Mohandas

Addresses: Mechanical Engineering Department, Amrita School of Engineering, Amrita University, Ettimadai, Coimbatore 641105, India. ' Manufacturing Industry Solutions Unit, Tata Consultancy Services Limited, Vikhroli West, Mumbai 400079, India. ' Department of Marketing, National Chung-Hsing University, Taiwan, ROC. ' Mechanical Engineering Department, Amrita School of Engineering, Amrita University, Ettimadai, Coimbatore 641105, India

Abstract: This paper considers a variant of the Vehicle Routing Problem (VRP) called Mixed Vehicle Routing Problem with Backhauls (MVRPB), an extension of the Vehicle Routing Problem with Backhauls (VRPB). This problem involves two sets of customers, called line-haul and backhaul customers. The demand of each line-haul customer is served by a single depot with a set of homogeneous capacitated vehicles. Apart from this, some amount of load needs to be picked up from the backhaul customers and should be taken back to the depot. The visit sequence of vehicles for line-haul and backhaul customers is mixed. The application of the MVRPB for the public healthcare system is explained. The MVRPB is a well-known, proven Non-deterministic Polynomial (NP)-hard problem. Various heuristic algorithms are proposed to solve the MVRPB to obtain approximate solutions. In this paper, we propose a composite Genetic Algorithm (GA) combined with different local search methods to solve the MVRPB. This is the first research paper for the application of metaheuristics with local search methods to solve the MVRPB. Extensive computational investigation for the MVRPB instances shows the efficacy of the proposed algorithm.

Keywords: mixed vehicle routing problem; backhauls; MVRPB; genetic algorithms; GAs; local search; public healthcare systems; metaheuristics.

DOI: 10.1504/IJSOM.2009.025117

International Journal of Services and Operations Management, 2009 Vol.5 No.5, pp.617 - 636

Published online: 13 May 2009 *

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