An Improved Genetic Algorithm for Vehicle Routing Problem Pick-up and Delivery with Time Windows
DOI:
https://doi.org/10.22219/JTIUMM.Vol22.No1.1-17Keywords:
VRPPDTW, Routing, Pickup and Delivery, Time Windows, Genetic AlgorithmAbstract
Vehicle Routing Problem (VRP) has many applications in real systems, especially in distribution and transportation. The optimal determination of vehicle routes impacts increasing economic interests. This research aims to find the optimal solution in Vehicle Routing Problem Pick-up and Delivery with Time Windows (VRPPDTW). Targets of this problem included reducing distance travel and penalties. Three penalties that were considered are a capacity penalty, opening time capacity, and closing time capacity. An improved genetic algorithm was developed and used to determine the vehicle route. There were one main depot and 42 customers. This research raised the problem of a shipping and logistics company. Analysis of the results showed that the proposed route obtained from improved genetic algorithms (GA) was better than the existing route and previous algorithm. Besides, this research was carried out an analysis on the effect of the number of iterations on distance traveled, the number of penalties, and the fitness value. This algorithm could be applied in VRPPDTW and produces an optimal solution.
Downloads
References
V. N. Coelho, A. Grasas, H. Ramalhinho, I. M. Coelho, M. J. F. Souza, and R. C. Cruz, "An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints," European Journal of Operational Research, vol. 250, pp. 367-376, 2016/04/16/ 2016. https://doi.org/10.1016/j.ejor.2015.09.047.
D. M. Utama, D. S. Widodo, M. F. Ibrahim, and S. K. Dewi, "A New Hybrid Butterfly Optimization Algorithm for Green Vehicle Routing Problem," Journal of Advanced Transportation, vol. 2020, p. 8834502, 2020/12/22 2020. https://doi.org/10.1155/2020/8834502.
D. M. Utama, S. K. Dewi, A. Wahid, and I. Santoso, "The vehicle routing problem for perishable goods: A systematic review," Cogent Engineering, vol. 7, p. 1816148, 2020/01/01 2020. https://doi.org/10.1080/23311916.2020.1816148.
F. Arnold and K. Sörensen, "What makes a VRP solution good? The generation of problem-specific knowledge for heuristics," Computers & Operations Research, vol. 106, pp. 280-288, 2019/06/01/ 2019. https://doi.org/10.1016/j.cor.2018.02.007.
P. Sitek, J. Wikarek, K. Rutczyńska-Wdowiak, G. Bocewicz, and Z. Banaszak, "Optimization of capacitated vehicle routing problem with alternative delivery, pick-up and time windows: A modified hybrid approach," Neurocomputing, vol. 423, pp. 670-678, 2021/01/29/ 2021. https://doi.org/10.1016/j.neucom.2020.02.126.
S. K. Dewi and D. M. Utama, "A New Hybrid Whale Optimization Algorithm for Green Vehicle Routing Problem," Systems Science & Control Engineering, vol. 9, pp. 61-72, 2021/01/01 2021. https://doi.org/10.1080/21642583.2020.1863276.
C. K. Y. Lin, "A cooperative strategy for a vehicle routing problem with pick-up and delivery time windows," Computers & Industrial Engineering, vol. 55, pp. 766-782, 2008/11/01/ 2008. https://doi.org/10.1016/j.cie.2008.03.001.
M. Mahmoudi and X. Zhou, "Finding optimal solutions for vehicle routing problem with pick-up and delivery services with time windows: A dynamic programming approach based on state–space–time network representations," Transportation Research Part B: Methodological, vol. 89, pp. 19-42, 2016/07/01/ 2016. https://doi.org/10.1016/j.trb.2016.03.009.
M. F. Ibrahim, F. R. Nurhakiki, D. M. Utama, and A. A. Rizaki, "Optimised Genetic Algorithm Crossover and Mutation Stage for Vehicle Routing Problem Pick-Up and Delivery with Time Windows," IOP Conference Series: Materials Science and Engineering, vol. 1071, p. 012025, 2021/02/01 2021. https://doi.org/10.1088/1757-899x/1071/1/012025.
R. Elshaer and H. Awad, "A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants," Computers & Industrial Engineering, vol. 140, p. 106242, 2020/02/01/ 2020. https://doi.org/10.1016/j.cie.2019.106242.
J. Protopopova and S. Kulik, "Educational Intelligent System Using Genetic Algorithm," Procedia Computer Science, vol. 169, pp. 168-172, 2020/01/01/ 2020. https://doi.org/10.1016/j.procs.2020.02.130.
S. Karakatič, "Optimizing nonlinear charging times of electric vehicle routing with genetic algorithm," Expert Systems with Applications, vol. 164, p. 114039, 2021/02/01/ 2021. https://doi.org/10.1016/j.eswa.2020.114039.
M. F. Ibrahim, I. Masudin, and T. Saputro, "A Hybrid Genetic Algorithm Implementation For Vehicle Routing Problem With Time Windows," Jurnal Ilmiah Teknik Industri, vol. 14, pp. 196-204, 01/01 2015. https://doi.org/10.23917/jiti.v14i2.985.
M. A. Mohammed, M. K. Abd Ghani, R. I. Hamed, S. A. Mostafa, M. S. Ahmad, and D. A. Ibrahim, "Solving vehicle routing problem by using improved genetic algorithm for optimal solution," Journal of Computational Science, vol. 21, pp. 255-262, 2017/07/01/ 2017. https://doi.org/10.1016/j.jocs.2017.04.003.
W. Ho, G. T. S. Ho, P. Ji, and H. C. W. Lau, "A hybrid genetic algorithm for the multi-depot vehicle routing problem," Engineering Applications of Artificial Intelligence, vol. 21, pp. 548-557, 2008/06/01/ 2008. https://doi.org/10.1016/j.engappai.2007.06.001.
P. R. de Oliveira da Costa, S. Mauceri, P. Carroll, and F. Pallonetto, "A Genetic Algorithm for a Green Vehicle Routing Problem," Electronic Notes in Discrete Mathematics, vol. 64, pp. 65-74, 2018/02/01/ 2018. https://doi.org/10.1016/j.endm.2018.01.008.
H. Nazif and L. S. Lee, "Optimised crossover genetic algorithm for capacitated vehicle routing problem," Applied Mathematical Modelling, vol. 36, pp. 2110-2117, 2012/05/01/ 2012. https://doi.org/10.1016/j.apm.2011.08.010.
R. Saxena, M. Jain, K. Malhotra, and K. D. Vasa, "An Optimized OpenMP-Based Genetic Algorithm Solution to Vehicle Routing Problem," in Smart Computing Paradigms: New Progresses and Challenges, Singapore, 2020, pp. 237-245. https://doi.org/10.1007/978-981-13-9680-9_20.
T. Visutarrom and T. Chiang, "An Evolutionary Algorithm with Heuristic Longest Cycle Crossover for Solving the Capacitated Vehicle Routing Problem," in 2019 IEEE Congress on Evolutionary Computation (CEC), 2019, pp. 673-680. https://doi.org/10.1109/CEC.2019.8789946.
S. Liu, W. Huang, and H. Ma, "An effective genetic algorithm for the fleet size and mix vehicle routing problems," Transportation Research Part E: Logistics and Transportation Review, vol. 45, pp. 434-445, 2009/05/01/ 2009. https://doi.org/10.1016/j.tre.2008.10.003.
L. Escobar-Falcón, D. Álvarez-Martínez, J. Wilmer-Escobar, and M. Granada-Echeverri, "A specialized genetic algorithm for the fuel consumption heterogeneous fleet vehicle routing problem with bidimensional packing constraints," International Journal of Industrial Engineering Computations, vol. 12, pp. 191-204, 2021. https://doi.org/10.5267/j.ijiec.2020.11.003.
Y. Marinakis and M. Marinaki, "A hybrid genetic – Particle Swarm Optimization Algorithm for the vehicle routing problem," Expert Systems with Applications, vol. 37, pp. 1446-1455, 2010/03/01/ 2010. https://doi.org/10.1016/j.eswa.2009.06.085.
C.-B. Cheng and K.-P. Wang, "Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm," Expert Systems with Applications, vol. 36, pp. 7758-7763, 2009/05/01/ 2009. https://doi.org/10.1016/j.eswa.2008.09.001.
K. Ghoseiri and S. F. Ghannadpour, "Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm," Applied Soft Computing, vol. 10, pp. 1096-1107, 2010/09/01/ 2010. https://doi.org/10.1016/j.asoc.2010.04.001.
T. Vidal, T. G. Crainic, M. Gendreau, and C. Prins, "A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows," Computers & Operations Research, vol. 40, pp. 475-489, 2013/01/01/ 2013. https://doi.org/10.1016/j.cor.2012.07.018.
Z. Ursani, D. Essam, D. Cornforth, and R. Stocker, "Localized genetic algorithm for vehicle routing problem with time windows," Applied Soft Computing, vol. 11, pp. 5375-5390, 2011/12/01/ 2011. https://doi.org/10.1016/j.asoc.2011.05.021.
J. H. Holland, Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence: University of Michigan Press, 1975.
P. Toth and D. Vigo, The vehicle routing problem: SIAM, 2002.
D. Whitley, T. Starkweather, and C. Bogart, "Genetic algorithms and neural networks: optimizing connections and connectivity," Parallel Computing, vol. 14, pp. 347-361, 1990/08/01/ 1990. https://doi.org/10.1016/0167-8191(90)90086-O.
J. L. Sponsler, "Genetic algorithms applied to the scheduling of the hubble space telescope," Telematics and Informatics, vol. 6, pp. 181-190, 1989/01/01/ 1989. https://doi.org/10.1016/S0736-5853(89)80015-2.
F. J. Marin, F. J. Gonzalez, and F. Sandoval, "The Routing Problem in Traffic Control Using Genetic Algorithms," IFAC Proceedings Volumes, vol. 27, pp. 187-191, 1994/06/01/ 1994. https://doi.org/10.1016/S1474-6670(17)46107-6.
R. Liu and Z. Jiang, "A hybrid large-neighborhood search algorithm for the cumulative capacitated vehicle routing problem with time-window constraints," Applied Soft Computing, vol. 80, pp. 18-30, 2019/07/01/ 2019. https://doi.org/10.1016/j.asoc.2019.03.008.
K. Sethanan and T. Jamrus, "Hybrid differential evolution algorithm and genetic operator for multi-trip vehicle routing problem with backhauls and heterogeneous fleet in the beverage logistics industry," Computers & Industrial Engineering, vol. 146, p. 106571, 2020/08/01/ 2020. https://doi.org/10.1016/j.cie.2020.106571.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2021 Muhammad Faisal Ibrahim, M.M Putri, D Farista, Dana Marsetiya Utama
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
