Title: CLASH: a heuristic to solve vehicle routing problems with delivery, pick-up and time windows

Authors: K. Ganesh, T.T. Narendran

Addresses: Supply Chain Management, Lakshmi Machine Works Limited, Perianaickenpalayam, Coimbatore 641020, India. ' Department of Management Studies, Indian Institute of Technology Madras, Chennai 600036, India

Abstract: This paper presents a multistage heuristic to solve a vehicle routing problem with delivery, pick-up and time windows that is applicable to the public healthcare system. Blood banks constitute a vital part of public healthcare services. Their logistics include blood procurement, processing, cross-matching, storage, distribution, recycling, pricing, quality control and outdating. This paper seeks to study the operational decision-making in the distribution of blood. The problem is considered with the condition that pick-up should occur last. We propose a methodology that exploits the inherent features of the problem. Prior to a meta-heuristic search, we form clusters of nodes, determine the route to be followed within a cluster and assign vehicles to routes in a feasible manner. Using this as input, we develop a genetic algorithm with innovative operators for crossover and mutation and conduct a rapid search to find a near-optimal solution. Computational results show that the new heuristic can solve problems effectively. Some of the results are better than the best solutions that have appeared in the literature.

Keywords: logistics; vehicle routing; time windows; clustering; genetic algorithms; delivery; pick-up; public healthcare; operations management; operational decision making; blood banks; blood distribution.

DOI: 10.1504/IJSOM.2007.013466

International Journal of Services and Operations Management, 2007 Vol.3 No.4, pp.460 - 477

Published online: 30 Apr 2007 *

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