Solving the Vehicle Routing Problems with Time Windows Using Hybrid Genetic Algorithm with Push Forward Insertion Heuristic and Local Search Procedure
Article Sidebar
Published:
Jan 28, 2019
Keywords:
hybrid Genetic Algorithm Vehicle Routing Problem with Time Window Meta-heuristic
Main Article Content
Abstract
The Vehicle Routing Problem with Time Windows (VRPTW) is a kind of important variant of VRP with adding time windows constraints to the model. The VRPTW is classified as an NP-hard problem. Hence, the use of exact optimization techniques may be hard to solve these problems in acceptable CPU times, when the problem involves real-world data sets that are very large. To solve this problem, this paper suggests a hybrid genetic algorithm (hybrid GA) combined with Push Forward Insertion Heuristic (PFIH) to make an initial solution instead of traditional GA and three local searches to neighborhood search and improving method. The proposed algorithm was tested on fourteen instances from an online data set in the Solomon`s 56 benchmark problems-selected randomly. The results indicate the good quality of the proposed algorithm.
Article Details
Section
Engineering Research Articles
The articles published are the opinion of the author only. The author is responsible for any legal consequences. That may arise from that article.
References
[1] Y. Kao, M. H. Chen, and Y. T. Huang, “A hybrid algorithm based on ACO and PSO for capacitated vehicle routing problems,” Mathematical Problems in Engineering, vol. 2012, pp. 17, 2012.
[2] J. F. Bard, G. Kontoravdis, and G. Yu, “A branchand-cut procedure for the vehicle routing problem with time windows,” Transportation Science, vol. 36, no. 2, pp. 250–269, 2002.
[3] M. Desrochers, J. Desrosiers, and M. Solomon, “A new optimization algorithm for the vehicle routing problem with time windows,” Operations Research, vol. 40, no. 2, pp. 342–354, 1992.
[4] N. Azi, M. Gendreau, and J.-Y. Potvin, “An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles,” European Journal of Operational Research, vol. 202, no. 3, pp. 756–763, 2010.
[5] W.-C. Chiang and R. A. Russell, “Simulated annealing metaheuristics for the vehicle routing problem with time windows,” Annals of Operations Research, vol. 63, no. 1, pp. 3–27, 1996.
[6] J. F. Cordeau, G. Laporte, and A. Mercier, “A unified tabu search heuristic for vehicle routing problems with time windows,” Journal of the Operational Research Society, vol. 52, no. 8, pp. 928-936, 2001.
[7] É. Taillard, P. Badeau, M. Gendreau, F. Guertin, and J.-Y. Potvin, “A tabu search heuristic for the vehicle routing problem with soft time windows,” Transportation Science, vol. 31, no. 2, pp. 170–186, 1997.
[8] G. Kontoravdis and J.F. Bard, “A GRASP for the vehicle routing problem with time windows, ” ORSA Journal on Computing, vol. 7, no. 1, pp. 10–23, 1995.
[9] G. B. Alvarenga, G. R. Mateus, and G. de Tomi, “A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows,” Computers & Operations Research, vol. 34, no. 6, pp. 1561–1584, 2007.
[10] İ. Küçükoğlu and N. Öztürk, “An advanced hybrid meta-heuristic algorithm for the vehicle routing problem with backhauls and time windows,” Computers & Industrial Engineering, vol. 86, pp. 60–68, 2015.
[11] R. Baños, J. Ortega, C. Gil, A. L. Márquez, and F. de Toro, “A hybrid meta-heuristic for multiobjective vehicle routing problems with time windows,” Computers & Industrial Engineering, vol. 65, no. 2, pp. 286–296, 2013.
[12] E. Jabir, V. V. Panicker, and R. Sridharan, “Design and development of a hybrid ant colonyvariable neighbourhood search algorithm for a multi-depot green vehicle routing problem,” Transportation Research Part D: Transport and Environment, vol. 57, pp. 422–457, 2017.
[13] L. Cui, L. Wang, J. Deng, and J. Zhang, “A new improved quantum evolution algorithm with local search procedure for capacitated vehicle routing problem,” Mathematical Problems in Engineering, vol. 2013, pp. 17, 2013.
[14] M. A. Hannan, M. Akhtar, R. A. Begum, H. Basri, A. Hussain, and E. Scavino, “Capacitated vehiclerouting problem model for scheduled solid waste collection and route optimization using PSO algorithm,” Waste Management, vol. 71, pp. 31–41, 2018.
[15] M. M. Solomon, “Algorithms for the vehicle routing and scheduling problems with time window constraints,” Operations Research, vol. 35, no. 2, pp. 254–265, 1987.
[16] J. H. Holland, Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. London, England: The MIT press, 1992.
[17] H. C. Brandão de Oliveira and G. C. Vasconcelos, “A hybrid search method for the vehicle routing problem with time windows,” Annals of Operations Research, vol. 180, no. 1, pp. 125–144, 2010.
[18] S. R. Thangiah, I.H. Osman, and T. Sun, “Hybrid genetic algorithm simulated annealing and tabu search methods for vehicle routing problem with time windows,” Computer Science Department, U.S.A., Technical Report 27., 1994.
[19] N. Wichapa and P. Khokhajaikiat, “Using the hybrid fuzzy goal programming model and hybrid genetic algorithm to solve a multi-objective location routing problem for infectious waste disposal,” Journal of Industrial Engineering and Management, vol. 10, no. 5, pp. 853–886, 2017.
[20] N. Wichapa and P. Khokhajaikiat, “Solving a multi-objective location routing problem for infectious waste disposal using hybrid goal programming and hybrid genetic algorithm,” International Journal of Industrial Engineering Computations, vol. 9, no. 1, pp. 75–98, 2018.
[21] M. M. Solomon. (2005, Oct.). Best Known Solutions Identified by Heuristics, Northeastern University, Massachusetts, Boston [Online]. Available: http://web.cba.neu.edu/~msolomon/heuristi.htm.
[2] J. F. Bard, G. Kontoravdis, and G. Yu, “A branchand-cut procedure for the vehicle routing problem with time windows,” Transportation Science, vol. 36, no. 2, pp. 250–269, 2002.
[3] M. Desrochers, J. Desrosiers, and M. Solomon, “A new optimization algorithm for the vehicle routing problem with time windows,” Operations Research, vol. 40, no. 2, pp. 342–354, 1992.
[4] N. Azi, M. Gendreau, and J.-Y. Potvin, “An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles,” European Journal of Operational Research, vol. 202, no. 3, pp. 756–763, 2010.
[5] W.-C. Chiang and R. A. Russell, “Simulated annealing metaheuristics for the vehicle routing problem with time windows,” Annals of Operations Research, vol. 63, no. 1, pp. 3–27, 1996.
[6] J. F. Cordeau, G. Laporte, and A. Mercier, “A unified tabu search heuristic for vehicle routing problems with time windows,” Journal of the Operational Research Society, vol. 52, no. 8, pp. 928-936, 2001.
[7] É. Taillard, P. Badeau, M. Gendreau, F. Guertin, and J.-Y. Potvin, “A tabu search heuristic for the vehicle routing problem with soft time windows,” Transportation Science, vol. 31, no. 2, pp. 170–186, 1997.
[8] G. Kontoravdis and J.F. Bard, “A GRASP for the vehicle routing problem with time windows, ” ORSA Journal on Computing, vol. 7, no. 1, pp. 10–23, 1995.
[9] G. B. Alvarenga, G. R. Mateus, and G. de Tomi, “A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows,” Computers & Operations Research, vol. 34, no. 6, pp. 1561–1584, 2007.
[10] İ. Küçükoğlu and N. Öztürk, “An advanced hybrid meta-heuristic algorithm for the vehicle routing problem with backhauls and time windows,” Computers & Industrial Engineering, vol. 86, pp. 60–68, 2015.
[11] R. Baños, J. Ortega, C. Gil, A. L. Márquez, and F. de Toro, “A hybrid meta-heuristic for multiobjective vehicle routing problems with time windows,” Computers & Industrial Engineering, vol. 65, no. 2, pp. 286–296, 2013.
[12] E. Jabir, V. V. Panicker, and R. Sridharan, “Design and development of a hybrid ant colonyvariable neighbourhood search algorithm for a multi-depot green vehicle routing problem,” Transportation Research Part D: Transport and Environment, vol. 57, pp. 422–457, 2017.
[13] L. Cui, L. Wang, J. Deng, and J. Zhang, “A new improved quantum evolution algorithm with local search procedure for capacitated vehicle routing problem,” Mathematical Problems in Engineering, vol. 2013, pp. 17, 2013.
[14] M. A. Hannan, M. Akhtar, R. A. Begum, H. Basri, A. Hussain, and E. Scavino, “Capacitated vehiclerouting problem model for scheduled solid waste collection and route optimization using PSO algorithm,” Waste Management, vol. 71, pp. 31–41, 2018.
[15] M. M. Solomon, “Algorithms for the vehicle routing and scheduling problems with time window constraints,” Operations Research, vol. 35, no. 2, pp. 254–265, 1987.
[16] J. H. Holland, Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. London, England: The MIT press, 1992.
[17] H. C. Brandão de Oliveira and G. C. Vasconcelos, “A hybrid search method for the vehicle routing problem with time windows,” Annals of Operations Research, vol. 180, no. 1, pp. 125–144, 2010.
[18] S. R. Thangiah, I.H. Osman, and T. Sun, “Hybrid genetic algorithm simulated annealing and tabu search methods for vehicle routing problem with time windows,” Computer Science Department, U.S.A., Technical Report 27., 1994.
[19] N. Wichapa and P. Khokhajaikiat, “Using the hybrid fuzzy goal programming model and hybrid genetic algorithm to solve a multi-objective location routing problem for infectious waste disposal,” Journal of Industrial Engineering and Management, vol. 10, no. 5, pp. 853–886, 2017.
[20] N. Wichapa and P. Khokhajaikiat, “Solving a multi-objective location routing problem for infectious waste disposal using hybrid goal programming and hybrid genetic algorithm,” International Journal of Industrial Engineering Computations, vol. 9, no. 1, pp. 75–98, 2018.
[21] M. M. Solomon. (2005, Oct.). Best Known Solutions Identified by Heuristics, Northeastern University, Massachusetts, Boston [Online]. Available: http://web.cba.neu.edu/~msolomon/heuristi.htm.