A Memory Integrated Artificial Bee Colony Algorithm with Local Search for Vehicle Routing Problem with Backhauls and Time Windows

Article Sidebar

PDF
Published: Jun 7, 2018
Keywords:
Memory integrated artificial bee colony algorithm Vehicle routing problem Backhauls Time windows Local search

Main Article Content

Naritsak Tuntitippawan
Department of Industrial Engineering, Faculty of Engineering, King Mongkut’s University of Technology North Bangkok, Bangkok, Thailand
Krisada Asawarungsaengkul
Department of Industrial Engineering, Faculty of Engineering, King Mongkut’s University of Technology North Bangkok, Bangkok, Thailand

Abstract

The vehicle routing problem is a logistics problem which receives much attentions in logistics management. This paper presents a Memory integrated Artificial Bee Colony Algorithm (MABC) to solve the Vehicle Routing Problem with addition of Backhauls and Time Windows, known as the VRPBTW. In VRPBTW, a homogenous fleet of vehicles are utilized to deliver goods to linehaul customer set and pick up goods from backhaul customer set. Vehicle capacity, sequence of linehaul/backhaul and time windows are the three of major constraints for this problem. The VRPBTW’s objective is to determine the optimal routes with minimum of total distance that satisfies all constraints. The proposed algorithm was tested on Gelinas’s VRPBTW benchmark problems. MABC is developed by adding the memory to Artificial Bee Colony (ABC). The local search algorithms including λ-interchange and 2-opt* are utilized to search for the better solutions. The computational results show that MABC significantly yields the good solutions in terms of total travelling distance. Finally, it can be concluded that the performance of the proposed MABC algorithm is superior to the existing studies in term of quality solution.

Article Details

How to Cite
Tuntitippawan, N., & Asawarungsaengkul, K. (2018). A Memory Integrated Artificial Bee Colony Algorithm with Local Search for Vehicle Routing Problem with Backhauls and Time Windows. Applied Science and Engineering Progress, 11(2), 85–92. Retrieved from https://ph02.tci-thaijo.org/index.php/ijast/article/view/211434
Issue
Vol. 11 No. 2 (2018)
Section
Research Articles

References

[1] W. Meethom and T. Triwong, “A multi-attribute urban metro construction excavated soil transportation decision making model based on integrated fuzzy AHP and integer linear programming,” KMUTNB Int J Appl Sci Technol, vol. 9, no. 3, pp. 153–165, 2016.

[2] S. Kaewploy and S. Sindhuchao. (2017). Solving the location routing problem of the central rubber market by tabu search. KMUTNB Int J Appl Sci Technol [Online]. 10(2), pp. 145–151. Available: http://ojs.kmutnb.ac.th/index.php/ijst/article/ view/806/pdf_111

[3] J. Y. Potvin, C. Duhamel, and F. Guertin, “A genetic algorithm for vehicle routing with backhauling,” Applied Intelligence, vol. 6, pp. 345–355, 1996.

[4] S. R. Thangiah, J. Y. Potvin, and T. Sun, “Heuristic approaches to vehicle routing with backhauls and time windows,” Computers & Operations Research, vol. 23, pp.1043–1057, 1996.

[5] C. Duhamel, J. Y. Potvin, and J. M. Rousseau, “A tabu search heuristic for the vehicle routing problem with backhauls and time windows,” Transportation Science, vol. 31, no. 1, pp. 49–59, 1997.

[6] M. ReimannKarl, K. Doerner, and R. F. Hartl, “Insertion based ants for vehicle routing problems with backhauls and time windows,” in Proceedings of the Third International Workshop, ANTS, Brussels, Belgium, 2002, pp.135–148.

[7] M. M. Solomon, “Algorithms for the vehicle routing and scheduling problems with time windows constraints,” Operations Research, vol. 35, pp. 254–265, 1987.

[8] Y. Zhong and M. H. Cole, “A vehicle routing problem with backhauls and time windows: A guided local search solution,” Transportation Research Part E, vol. 41, pp. 131–144, 2005.

[9] I. Kucukoglu and N. Ozturk, “A differential evolution approach for the vehicle routing problem with backhauls and time windows,” Journal of Advanced Transportation, vol. 48, pp. 942–956, 2014.

[10] I. Kucukoglu and N. Ozturk, “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] N. Tuntitippawan and K. Asawarungsaengkul, “An artificial bee colony algorithm with local search for vehicle routing problem with backhaul and time windows,” KKU Engineering Journal, vol. 43, pp. 404–408, 2016.

[12] S. Gélinas, M. Desrochers, J. Desrosiers, and M. M. Solomon, “A new branching strategy for time constrained routing problems with application to backhauling,” Annals of Operations Research, vol. 61, no. 1, pp. 91–109, 1995.

[13] P. Toth and D. Vigoo, The vehicle routing problem, Philadelphia: Society for Industrial and Applied Mathematics, 2001, pp. 198–199.

[14] W. Y. Szeto, Y. Wu, and S. C. Ho, “An artificial bee colony algorithm for the capacitated vehicle routing problem,” European Journal of Operational Research, vol. 215, no. 1, pp. 126–135, 2011.

[15] K. W. Pang, “An adaptive parallel route construction heuristic for the vehicle routing problem with time windows constraints,” Expert Systems with Applications, vol. 38, pp. 11939–11946, 2011.

[16] I. H. Osman and N. Christofides, “Capacitated clustering problems by hybrid simulated annealing and tabu search,” Internatioal Transactions in Operational Research. vol. 1, no. 3, pp. 317–336, 1994.

[17] J. Y. Potvin, T. Kervahut, B. L. Garcia, and J. M. Rousseau, “A tabu search heuristic for the vehicle routing problem with time windows,” Quebec Centre de Recherche sur les Transports, Universite de Montreal, Technical Report CRT-855, 1993.