AN INTRODUCTION OF GENETIC ALGORITHM FOR IMPROVING A VEHICLE ROUTING PROBLEM IN A BAKERY COMPANY

Bell  Tunjongsirigul; Navee  Chiadamrong

Authors

Bell Tunjongsirigul Logistics and Supply Chain Systems Engineering, Sirindhorn International Institute of Technology, Thammasat University, Pathum-Thani, Thailand.
Navee Chiadamrong Logistics and Supply Chain Systems Engineering, Sirindhorn International Institute of Technology, Thammasat University, Pathum-Thani, Thailand.

Keywords:

Single depot, vehicle routing problem, genetic algorithm, nearest neighbor heuristic

Abstract

The aim of the study is to apply a Genetic Algorithm (GA) to solve a Vehicle Routing Problem (VRP)for a specific bakery company. This VRP application consists of 1 depot with 32 customers in 6 delivery zones. In the study, the GA is chosen to solve this vehicle routing problem as compared with an existing method currently used by the company, which resembles to the Nearest Neighbor Heuristic(NN). The result of the comparison shows that the proposed GA performs better than the existing heuristic method. In addition, a comparison between different time constraints for vehicles to return to the depot is made to suggest to the company a suitable duration of its delivery time if the company decides to speed up and limit its delivery time in the future.

References

Baker, B.M. and Ayechew, M.A. (2003). A genetic algorithm for the vehicle routing problem.Computers & Operations Research, 30:787-800.

Bell, J.E. and McMullen, P.R. (2004). Ant colony optimization techniques for the vehicle routing problem. Advanced Engineering Informatics,18:41-48.

Braysy, O. and Gendreau, M. (2005). Vehicle routing problem with time windows. Transportation Science, 39:119-139.

Chidananda, G. and Krishna, G. (1979). The condensed nearest neighbor rule using the concept of mutual nearest neighborhood. IEEE Transactions on Information Theory, 25(4):488-490.

Dantzig, G.B. and Ramser, J.H. (1959). The truck dispatching problem. Management Science,6(1):80-91.

de Oliveira, H.C.B., Vasconcelos, G.C. and Alvarenga,G.B. (2006). A multi-start simulated annealing algorithm for the vehicle routing problem with time windows. Proceedings of the Ninth Brazilian Symposium on Neural Networks (SBRN’06).27 October, 23:137-142.

Gambardella, L.M., Taillard, E. and Agazzi, G. (1999).MACS VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows, New Ideas in Optimization, McGraw Hill Ltd., Maidenhead, UK.

Ghoseiri, K. and Ghannadpour, S.F. (2010). Multiobjectivevehicle routing problem with time windows using goal programming and genetic algorithm. Applied Soft Computing, 10:1096-1107.

Holland, J.H. (1975). Adaptive in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, MI.

Jeon, G., Leep, H.R. and Shim, J.Y. (2007). A vehicle routing problem solved by using a hybrid genetic algorithm. Computers and Industrial Engineering,53:680-692.

Jigang, W., Predrag, N., and Leon, N.C. (2007).Improving nearest neighbor rule with a simple adaptive distance measure. Pattern Recognition Letters, 28:207-213.

Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem.Computers and Operations Research, 31:1985-2002.

Poon, P.W. and Carter, J.N. (1995). Genetic algorithm crossover operators for ordering applications.Computers Operations Research, 22(1):135-147.

Su, C.T. (1998). Locations and vehicle routing designs of physical distribution systems. Production Planning & Control, 9(7):650-659.

Taillard, E. (1993). Parallel iterative search methods for vehicle routing problems. Networks, 23:661-673.

Toth, P. and Vigo, D. (2002). The Vehicle Routing Problem.SIAM Monographs Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia, USA.

Zhou, C.Y. and Chen, Y.Q. (2006). Improving nearest neighbor classification with cam weighted distance. Pattern Recognition, 39:635-645.