A GA based meta-heuristic for capacitated vehicle routing problem with simultaneous pick-up and deliveries

Official URL: http://risc01.sabanciuniv.edu/record=b1083693 (Table of Contents)

In this study, we focus on the theoretical framework of a decision model for a real world problem. The problem reveals itself as simultaneous distribution of commodities and recollection of empty packages the same size as the initial state with a single depot and a fleet of uniform vehicles with limited capacities. Resembling instances pile a profound literature under the category of "pick-up and delivery problems with backhauls" and "rural postman problem." To solve the arousing NP-hard problem we use genetic algorithm approach. Computational efficiency and a good solution performance are sought. We have studied the wide literature of the vehicle routing problems, classified and briefly introduced the previous asserted algorithms, which provide considerably high quality solutions. We have developed a genetic algorithm based meta-heuristic on a linear IP model proposed by Dethloff (2001) and conducted tests to come up with a robust heusritic producing results with a reasonable quality. The models we studied were mainly taken from the machine scheduling literature and adapted to handle our problem. Our research has revealed that no resembling problem has ever been proposed to be solved using the genetic algorithms approach. Thus, this work is a first in its field. The improvement algorithm is found to be considerably good performing while the random keys method failed to produce reasonable solutions. We have tested our algorithm on two benchmark problems introduced by Min (1989) and Dethloff (2001). The latter is composed of 40 problem instances generated. We have performed parameter tests to tune our algorithm and shown that our algorithm produced the best ever solution for the first problem and considerably good solutions for the second one.