Modified Ant Colony Optimization with Route Elimination and Pheromone Reset for Multiple Pickup and Multiple Delivery Vehicle Routing Problem with Time Window

Chiabwoot Ratanavilisagul

doi:10.20965/jaciii.2022.p0959

single-jc.php

« previous

JACIII Vol.26 No.6 pp. 959-964

doi: 10.20965/jaciii.2022.p0959

(2022)

Paper:

Views over last 60 days: 342

Modified Ant Colony Optimization with Route Elimination and Pheromone Reset for Multiple Pickup and Multiple Delivery Vehicle Routing Problem with Time Window

Chiabwoot Ratanavilisagul

Department of Computer and Information Science of Applied Science, King Mongkut’s University of Technology North Bangkok
1518 Pracharat 1 Road, Wong Sawang Subdistrict, Bang Sue District, Bangkok 10800, Thailand

Received:

January 7, 2022

Accepted:

July 1, 2022

Published:

November 20, 2022

Keywords:

vehicle routing problem, ant colony optimization, optimization, local optimum

Abstract

The vehicle routing problem (VRP) has many applications in goods distribution and goods transportation. Today, many companies have requirements for VRP with multiple pickup and multiple delivery within due time. This problem is called multiple pickup and multiple delivery vehicle routing problem with time window (PDPTW). PDPTW has many constraints and ant colony optimization (ACO) has been used to solve it although ACO creates too many infeasible routes. Moreover, it often gets trapped in local optimum. To solve these problems, this paper proposed an improved ACO by using the route elimination technique and the pheromone reset technique. The ACO with route elimination technique, it has proven to solve the PDPTW problem with increased performance. The proposed technique was tested on datasets from the Li & Lim’s PDPTW benchmark problems and provided more satisfactory results compared to other ACO techniques.

Cite this article as:

C. Ratanavilisagul, “Modified Ant Colony Optimization with Route Elimination and Pheromone Reset for Multiple Pickup and Multiple Delivery Vehicle Routing Problem with Time Window,” J. Adv. Comput. Intell. Intell. Inform., Vol.26 No.6, pp. 959-964, 2022.

Data files:

References

[1] G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem,” Management Science, Vol.6, No.1, pp. 80-91, 1959.
[2] P. Toth and D. Vigo, “The Vehicle Routing Problem,” 1st ed., Society for Industrial and Applied Mathematics, pp. 385-386, 2002.
[3] H. Min, “The multiple vehicle routing problem with simultaneous delivery and pick-up points,” Transportation Research Part A: General, Vol.23, No.5, pp. 377-386, 1989.
[4] B. Wang, “Research on the Vehicle Routing Problem with Simultaneous Pick-up and Delivery with Time Windows,” Proc. of the RSU Int. Research Conf., pp. 1885-1892, 2020.
[5] Z.-G. Wang and G.-J. Li, “Research on Vehicle Routing Problem with Pick-Up and Delivery Based on Genetic Algorithm,” Computer Engineering and Application, Vol.1, pp. 208-211, 2006.
[6] K. Kamsopa, K. Sethanan, T. Jamrus, and L. Czwajda, “Hybrid Genetic Algorithm for Multi-Period Vehicle Routing Problem with Mixed Pickup and Delivery with Time Window, Heterogeneous Fleet, Duration Time and Rest Area,” Eng. J., Vol.25, No.10, pp. 71-86, 2021.
[7] M. F. Ibrahim, M. M. Putri, D. Farista, and D. Utama, “An Improved Genetic Algorithm for Vehicle Routing Problem Pick-Up and Delivery with Time Windows,” Jurnal Teknik Industri., Vol.22, No.1, pp. 1-17, 2021.
[8] 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,” Proc. of the Int. Conf. on Advanced Science and Technology, pp. 1-7, 2020.
[9] K.-S. Hung, S.-F. Su, and Z.-J. Lee, “Improving Ant Colony Optimization Algorithms for Solving Traveling Salesman Problems,” J. Adv. Comput. Intell. Intell. Inform., Vol.11, No.4, pp. 433-442, 2007.
[10] Y. Chenxiao, S. Zuiyi, and L. Pengfei, “Route Optimization of Aquatic Product Transportation Based on an Improved Ant Colony Algorithm,” J. Adv. Comput. Intell. Intell. Inform., Vol.24, No.4, pp. 488-493, 2020.
[11] Z. Huizhen, Z. Qinwan, M. Liang, Z. Ziying, and L. Yun, “A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows,” Information Sciences, Vol.490, pp. 166-190, 2019.
[12] E. H.-C. Lu, Y.-W. Yang, and Z. L.-T. Su, “Ant Colony Optimization solutions for logistic route planning with pick-up and delivery,” Proc. of the 2016 IEEE Int. Conf. on Systems, Man, and Cybernetics, pp. 808-813, 2016.
[13] B. Catay, “Ant Colony Optimization and Its Application to the Vehicle Routing Problem with Pickups and Deliveries,” R. Chiong and S. Dhakal (Eds.), “Natural Intelligence for Scheduling, Planning and Packing Problems: Studies in Computational Intelligence,” pp. 219-244, Springer, 2009.
[14] M. Sayyah, H. Larki, and M. Yousefikhoshbakht, “Solving the Vehicle Routing Problem with Simultaneous Pickup and Delivery by an Effective Ant Colony Optimization,” J. of Industrial Engineering and Management Studies, Vol.3, No.1, pp. 15-38, 2016.
[15] P. K. N. Phan and T. P. L. Nguyen, “Ant Colony Optimization for Multiple Pickup and Multiple Delivery Vehicle Routing Problem with Time Window and Heterogeneous Fleets,” Logistics, Vol.5, No.2, pp. 5-28, 2021.
[16] B. Bullnheimer, R. F. Hartl, and C. Strauss, “An improved ant system algorithm for the vehicle routing problem,” Annals of Operations Research, Vol.89, pp. 319-328, 1999.
[17] B. Yu, Z. Z. Yang, and B. Z. Yao, “An improved ant colony optimization for vehicle routing problem,” European J. of Operational Research, Vol.196, No.1, pp. 171-176, 2009.
[18] A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed Optimization by Ant Colonies,” Proc. of the European Conf. on Artificial Life, pp. 134-142, 1991.
[19] M. Dorigo and L. M. Gambardella, “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Trans. on Evolutionary Computation, Vol.1, pp. 53-66, 1997.
[20] V. Selvi and R. Umarani, “Comparative Analysis of Ant Colony and Particle Swarm Optimization Techniques,” Int. J. of Computer Applications, Vol.5, pp. 1-6, 2010.
[21] M. Dorigo and L. M. Gambardella, “A Study of Some Properties of Ant-Q,” Proc. of the 44th Int. Conf. on Parallel Problem Solving from Nature, pp. 656-665, 1996.
[22] Li & Lim benchmark, https://www.sintef.no/projectweb/top/pdptw/li-lim-benchmark [accessed March 3, 2022].
[23] C. Ratanavilisagul, “Modified ant colony optimization with updating pheromone by leader and re-initialization pheromone for travelling salesman problem,” Int. Conf. on engineering, applied sciences, and technology, pp. 1-4, 2018.
[24] C. Ratanavilisagul and B. Kruatrachue, “A Modified Particle Swarm Optimization With Mutation and Reposition,” Int. J. of Innovative Computing, Information and Control, Vol.10, pp. 2127-2142, 2014.

This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[1] [1] G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem,” Management Science, Vol.6, No.1, pp. 80-91, 1959.

[2] [2] P. Toth and D. Vigo, “The Vehicle Routing Problem,” 1st ed., Society for Industrial and Applied Mathematics, pp. 385-386, 2002.

[3] [3] H. Min, “The multiple vehicle routing problem with simultaneous delivery and pick-up points,” Transportation Research Part A: General, Vol.23, No.5, pp. 377-386, 1989.

[4] [4] B. Wang, “Research on the Vehicle Routing Problem with Simultaneous Pick-up and Delivery with Time Windows,” Proc. of the RSU Int. Research Conf., pp. 1885-1892, 2020.

[5] [5] Z.-G. Wang and G.-J. Li, “Research on Vehicle Routing Problem with Pick-Up and Delivery Based on Genetic Algorithm,” Computer Engineering and Application, Vol.1, pp. 208-211, 2006.

[6] [6] K. Kamsopa, K. Sethanan, T. Jamrus, and L. Czwajda, “Hybrid Genetic Algorithm for Multi-Period Vehicle Routing Problem with Mixed Pickup and Delivery with Time Window, Heterogeneous Fleet, Duration Time and Rest Area,” Eng. J., Vol.25, No.10, pp. 71-86, 2021.

[7] [7] M. F. Ibrahim, M. M. Putri, D. Farista, and D. Utama, “An Improved Genetic Algorithm for Vehicle Routing Problem Pick-Up and Delivery with Time Windows,” Jurnal Teknik Industri., Vol.22, No.1, pp. 1-17, 2021.

[8] [8] 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,” Proc. of the Int. Conf. on Advanced Science and Technology, pp. 1-7, 2020.

[9] [9] K.-S. Hung, S.-F. Su, and Z.-J. Lee, “Improving Ant Colony Optimization Algorithms for Solving Traveling Salesman Problems,” J. Adv. Comput. Intell. Intell. Inform., Vol.11, No.4, pp. 433-442, 2007.

[10] [10] Y. Chenxiao, S. Zuiyi, and L. Pengfei, “Route Optimization of Aquatic Product Transportation Based on an Improved Ant Colony Algorithm,” J. Adv. Comput. Intell. Intell. Inform., Vol.24, No.4, pp. 488-493, 2020.

[11] [11] Z. Huizhen, Z. Qinwan, M. Liang, Z. Ziying, and L. Yun, “A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows,” Information Sciences, Vol.490, pp. 166-190, 2019.

[12] [12] E. H.-C. Lu, Y.-W. Yang, and Z. L.-T. Su, “Ant Colony Optimization solutions for logistic route planning with pick-up and delivery,” Proc. of the 2016 IEEE Int. Conf. on Systems, Man, and Cybernetics, pp. 808-813, 2016.

[13] [13] B. Catay, “Ant Colony Optimization and Its Application to the Vehicle Routing Problem with Pickups and Deliveries,” R. Chiong and S. Dhakal (Eds.), “Natural Intelligence for Scheduling, Planning and Packing Problems: Studies in Computational Intelligence,” pp. 219-244, Springer, 2009.

[14] [14] M. Sayyah, H. Larki, and M. Yousefikhoshbakht, “Solving the Vehicle Routing Problem with Simultaneous Pickup and Delivery by an Effective Ant Colony Optimization,” J. of Industrial Engineering and Management Studies, Vol.3, No.1, pp. 15-38, 2016.

[15] [15] P. K. N. Phan and T. P. L. Nguyen, “Ant Colony Optimization for Multiple Pickup and Multiple Delivery Vehicle Routing Problem with Time Window and Heterogeneous Fleets,” Logistics, Vol.5, No.2, pp. 5-28, 2021.

[16] [16] B. Bullnheimer, R. F. Hartl, and C. Strauss, “An improved ant system algorithm for the vehicle routing problem,” Annals of Operations Research, Vol.89, pp. 319-328, 1999.

[17] [17] B. Yu, Z. Z. Yang, and B. Z. Yao, “An improved ant colony optimization for vehicle routing problem,” European J. of Operational Research, Vol.196, No.1, pp. 171-176, 2009.

[18] [18] A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed Optimization by Ant Colonies,” Proc. of the European Conf. on Artificial Life, pp. 134-142, 1991.

[19] [19] M. Dorigo and L. M. Gambardella, “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Trans. on Evolutionary Computation, Vol.1, pp. 53-66, 1997.

[20] [20] V. Selvi and R. Umarani, “Comparative Analysis of Ant Colony and Particle Swarm Optimization Techniques,” Int. J. of Computer Applications, Vol.5, pp. 1-6, 2010.

[21] [21] M. Dorigo and L. M. Gambardella, “A Study of Some Properties of Ant-Q,” Proc. of the 44th Int. Conf. on Parallel Problem Solving from Nature, pp. 656-665, 1996.

[22] [22] Li & Lim benchmark, https://www.sintef.no/projectweb/top/pdptw/li-lim-benchmark [accessed March 3, 2022].

[23] [23] C. Ratanavilisagul, “Modified ant colony optimization with updating pheromone by leader and re-initialization pheromone for travelling salesman problem,” Int. Conf. on engineering, applied sciences, and technology, pp. 1-4, 2018.

[24] [24] C. Ratanavilisagul and B. Kruatrachue, “A Modified Particle Swarm Optimization With Mutation and Reposition,” Int. J. of Innovative Computing, Information and Control, Vol.10, pp. 2127-2142, 2014.