A HYBRID GENETIC ALGORITHM IMPLEMENTATION FOR VEHICLE ROUTING PROBLEM WITH TIME WINDOWS

Muhammad Faisal Ibrahim(1*), Ilyas Masudin(2), Thomy Eko Saputro(3),

(1) Universitas Muhammadiyah Malang
(2) Universitas Muhammadiyah Malang
(3) Universitas Muhammadiyah Malang
(*) Corresponding Author
DOI: https://doi.org/10.23917/jiti.v14i2.985

Abstract

This article is related to approach development in order to determine the most appropriate route for bottled water delivery from warehouse to retail from particular boundaries such as a limit on number of vehicle, vehicle capacity, and time windows to each retail. A mathematical model of VRPTW is adopted to solve the problem. Malang is one of the drinking water production centers in Indonesia, definitely it will be difficult for the company to determine the optimal delivery route with the existing restrictions. In this research hybrid genetic algorithm is use to determine the route shipping companies with the Java programming language. After analyzing the results obtained show that the results of the implementation of hybrid genetic algorithm is better than the company actual route. Moreover, authors also analyze the effect the number of iterations for the computation time, and the influence the number of iterations for the fitness value or violation. This algorithm can be applied for the routing and the result obtained is an optimal solution

Keywords

VRPTW, Hybrid Algorithm Genetics, Fitness

Full Text:

PDF

References

Astuti, S. 2012. Aplikasi Algoritma Genetika Hibrida pada Vehicle Routing Problem with Time Windows. Undergraduate Thesis. Mathematics Dept., Universitas Indonesia.

Baker, B.M., & Ayechew, M.A. 2003. “A genetic algorithm for the vehicle routing problem”. Computers & Operations Research, Vol. 30 (5), pp. 787-800.

Berger, J.; Barkaoui, M. 2003. “A Hybrid Genetic Algorithm for the Capacitated Vehicle Routing Problem”. Journal of Genetic and Evolutionary Computation. Vol. 2723, pp.: 646-656.

Bräysy, O. 2001. Genetic algorithms for the vehicle routing problem with time windows. Arpakannus, Vol. (1), Special issue, pp. 33-38.

De Backer, B.; Furnon, V. 1999. “Local Search in Constraint Programming: Experiments with Tabu Search on the Vehicle Routing Problem”. in Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization. Editor by S. Voss, S. Martello, I. Osman and C. Roucairol, US: Springer, pp: 63-76.

De Jong, K. A. 1975. An Analysis of The Behavior of A Class of Genetic Adaptive Systems. Doctoral dissertation. University of Michigan Ann Arbor, USA.

Fenghe, J.; Yaping, F. 2010. “Hybrid genetic algorithm for vehicle routing problem with time windows”. in Management and Service Science (MASS), 2010 International Conference on (pp. 1-4). IEEE.

Ghiani, G.; Laporte, G.; Musmanno, R. 2004. Introduction to Logistics Systems Planning and Control. Chichester, England: J. Wiley.

Ghoseiri, K.; Ghannadpour, S.F. 2010. "Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm." Applied Soft Computing, Vol. 10 (4), pp: 1096-1107.

Golberg, D. E. 1989. Genetic Algorithms in Search, Optimization, and Machine Learning. Massachusetts: Addion Wesley Publ. Co.

Golden, B. L.; Wasil, E.A. 1987. “Computerized vehicle routing in the soft drink industry”. Journal Operation Research, Vol. 35 (1), pp. 6 – 17.

Halse, K. 1992. Modeling and Solving Complex Vehicle Routing Problems. PhD Thesis. Institute of Mathematical Statistics and Operation Research (IMSOR), Technical University of Denmark.

Han, S.; Tabata, Y. 2002. “A hybrid genetic algorithm for the vehicle routing problem with controlling lethal gene”. Asia Pacific Management Review, Vol. 7 (3), pp. 405-425.

Holland, J. H. 1975. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press.

Jianjun, L.; Jian, L. 2009. “A modified particle swarm optimization for practical engineering optimization”. in Proceeding of Fifth International Conference Natural Computation, 2009( ICNC'09), Vol. 3, pp. 177 – 180. IEEE.

Joshi, S.; Kaur, S. 2015. "Nearest neighbor insertion algorithm for solving capacitated vehicle routing problem". in Computing for Sustainable Global Development (INDIACom), 2nd International Conference, pp.86 – 88.

Kallehauge, B. 2007. “Formulations and exact algorithms for the vehicle routing problem with time windows”. Computers & Operations Research, Vol 34, pp. 2307–2330.

Man, K.F.; Tang, K.S.; Kwong, S. 2012. Genetic Algorithms: Concepts and Designs. Springer Science & Business Media.

Mitchell, M. 1998. An Introduction to Genetic Algorithms. MIT Press.

Mühlenbein, H.; Schlierkamp-Voosen, D. 1993. "Predictive models for the breeder genetic algorithm i. continuous parameter optimization". Evolutionary Computation, Vol. 1 (1), pp. 25 – 49.

Tan, K.C.; Lee, L.H.; Zhu, Q.L.; Ou, K. 2001. “Heuristic methods for vehicle routing problem with time windows”. Artificial intelligence in Engineering, Vol. 15(3), pp. 281-295.

Thangiah, S.R.; Osman, I.H.; Sun, T. 1994. Hybrid Genetic Algorithm, Simulated Annealing and Tabu Search Methods for Vehicle Routing Problems with Time Windows. Technical Report CpSc-TR-94-27, 69. Computer Science Department, Slippery Rock University.

Xiang-yang, L. I. 2004. “Genetic algorithm for VRP”. Computer Engineering and Design, Vol. 31(5), pp. 271 – 276.

Zhang, Y.; Liu, J.; Duan, F.; Ren, J. 2007. “Genetic algorithm in vehicle routing problem”. in Intelligent Information Hiding and Multimedia Signal Processing, 2007 (IIHMSP 2007). Third International Conference on (Vol. 2, pp. 578-581). IEEE.

Article Metrics

Abstract view(s): 1033 time(s)
PDF: 609 time(s)

Refbacks

  • There are currently no refbacks.