Risk Averse Metaheuristic Hybrid Solution Approach to Vehicle Routing Problem of Hazardous Materials Through the Combination of Game Theory and Tabu Search

Abstract

Because they have become an integral part of our daily lives, large quantities of hazardous materials are produced and transported each year. In most industrial societies, life without hazardous materials has become almost unimaginable. Hazardous materials are defined as substances that, during transportation, have the potential to pose adverse effects or risks to public health, safety, or property due to their quantity or form. In this context, hazardous materials or products include explosives, gases, flammable and oxidizing substances, toxic and infectious materials, as well as radioactive, corrosive substances and their associated hazardous wastes. The safe transportation of hazardous materials is considered a comprehensive and multidimensional issue, influenced by various legal and physical factors, as well as the numerous risks that vehicles may encounter during transit. Increasing environmental awareness of the potential impacts of hazardous material accidents on public health has significantly heightened both academic and institutional interest in this field. This study proposes a risk-averse solution to the hazardous material transportation problem through a model developed by integrating the Tabu Search algorithm with a game theory–based approach. Within the model, the dispatcher aims to minimize the expected loss under the worst possible conditions in the event of a disruption in any link of the distribution network. In this framework, the expected cost determined through Nash equilibrium is evaluated as an effective and practical analytical tool for strategic decision-making in the selection of safe routes for hazardous material transportation.

Keywords

• Transportation of hazardous materials
• Vehicle routing problem
• Game theory
• Tabu search
• Nash-equilibrium

Supporting Institution

Ministery of Turkish National Education

Ethical Statement

“Ethics committee permission is not required for the prepared article” “There is no conflict of interest with any person/institution in the prepared article.”

Thanks

We would like to express our sincere gratitude to the Ministry of National Education for its financial support.

Oyun Teorisi ve Tabu Araması Yoluyla Tehlikeli Maddelerin Araç Rotalama Problemine Risk Kaçınımlı Metasezgisel Hibrit Çözüm Yaklaşımı

Abstract

Günlük yaşamımızın ayrılmaz bir parçası haline gelmelerinin bir sonucu olarak, her yıl büyük miktarlarda tehlikeli madde üretilmekte ve taşınmaktadır. Sanayi toplumlarının çoğunda, tehlikeli maddeler olmadan bir yaşam neredeyse tahayyül edilemez hâle gelmiştir. Tehlikeli maddeler; taşınma sürecinde halk sağlığı, kamu güvenliği ya da taşınmaz mallar üzerinde olumsuz etkiler veya riskler yaratma potansiyeline sahip miktar ve formda bulunan maddeler olarak tanımlanır. Bu bağlamda, tehlikeli maddeler veya ürünler; patlayıcı, gaz hâlinde, yanıcı, oksitleyici, toksik, bulaşıcı, radyoaktif ya da aşındırıcı özellik gösteren maddeler ile bunlara ait tehlikeli atıkları kapsamına almaktadır. Tehlikeli maddelerin güvenli taşınması; sürece etki eden yasal ve fiziksel faktörler ile taşıma araçlarının maruz kalabileceği çeşitli riskler nedeniyle kapsamlı ve çok boyutlu bir sorun alanı olarak değerlendirilmektedir. Tehlikeli madde kazalarının halk sağlığına yönelik olası etkilerine karşı artan çevresel duyarlılık, tehlikeli madde taşımacılığı konusuna yönelik akademik ve kurumsal ilgiyi önemli ölçüde artırmaktadır. Bu makale, oyun teorisi temelli bir yaklaşımla tabu arama algoritmasının entegrasyonu sonucu geliştirilen model üzerinden, tehlikeli madde taşımacılığı problemine yönelik riskten kaçınan bir çözüm önermektedir. Model kapsamında, dağıtım görevlisi, sevkiyat ağındaki herhangi bir bağlantıda problem oluşması durumunda, olası en olumsuz koşullar altında ortaya çıkabilecek beklenen zararı minimize etmeyi hedeflemektedir. Bu çerçevede, Nash dengesi aracılığıyla belirlenen beklenen maliyet fonksiyonu, tehlikeli madde taşımacılığında güvenli güzergâh seçimine yönelik stratejik kararların analizinde etkili ve pratik bir çözüm aracı olarak değerlendirilmektedir.

Keywords

• Tehlikeli madde taşımacılığı
• Araç rotalama problemi
• Oyun teorisi
• Tabu arama
• Nash-dengesi.

Supporting Institution

Milli Eğitim Bakanlığı

Ethical Statement

“Hazırlanan makale için etik kurul onayı gerekmemektedir.” “Hazırlanan makalede herhangi bir kişi/kurumla çıkar çatışması bulunmamaktadır.”

Thanks

Milli Eğitim Bakanlığına sağladığı finansal destek dolayısı ile teşekkürlerimizi sunarız

References

1. E. Erkut and V. Verter, “A framework for hazardous materials transport risk assessment,” Risk Anal., vol. 15, no. 5, pp. 589–609, 1995.
2. R. A. Sivakumar, R. Batta, and M. H. Karwan, “A multiple route conditional risk model for transporting hazardous materials,” INFOR, vol. 33, no. 1, pp. 20–33, 1995.
3. H. D. Sherali, L. D. Brizendine, T. S. Glickman, and S. Subramanian, “Low probability–high consequence considerations in routing hazardous material shipment,” Transp. Sci., vol. 31, no. 3, pp. 237–251, 1997.
4. E. Erkut and A. Ingolfsson, “Catastrophe avoidance models for hazardous materials route planning,” Transp. Sci., vol. 34, no. 2, pp. 165–179, 2000.
5. J. K. Lenstra and A. H. G. Kan, “Complexity of vehicle routing and scheduling problems,” Networks, vol. 11, pp. 221–227, 1981.
6. G. Laporte, “Exact algorithms for travelling salesman problem and the vehicle routing problems,” Les Cah. GERAD, Tech. Rep. G-98-37, 1998.
7. G. Laporte, M. Gendreau, J. Y. Potvin, and F. Semet, “Classical and modern heuristics for vehicle routing problem,” Les Cah. GERAD, Tech. Rep. G-99-21, 1999.
8. G. Clarke and J. Wright, “Scheduling of vehicles from a central depot to a number of delivery points,” Oper. Res., vol. 12, pp. 568–581, 1964.

9. B. E. Gillet and L. R. Miller, “A heuristic algorithm for the vehicle dispatch problem,” Oper. Res., vol. 22, pp. 340–349, 1974.
10. M. L. Fisher and R. Jaikumar, “A generalized assignment heuristic for vehicle routing,” Networks, vol. 11, pp. 109–124, 1981.
11. I. H. Osman, “Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem,” Ann. Oper. Res., vol. 41, pp. 421–451, 1993.
12. G. Barbarosoglu and D. Ozgur, “A tabu search algorithm for the vehicle routing problem,” Comput. Oper. Res., vol. 26, pp. 255–270, 1999.
13. P. Toth and D. Vigo, “Granular tabu search and its applications to the vehicle routing problem,” Working Paper, DEIS, Univ. Bologna, 1998.
14. J. L. Blanton and R. L. Wainwright, “Multiple vehicle routing problem with time and capacity constraints using genetic algorithm,” in Proc. 5th Int. Conf. Genet. Algorithms, San Mateo, CA, USA: Morgan Kaufmann, 1993, pp. 452–459.
15. A. Kheiri, A. J. Dragomir, D. Mueller, J. J. Gromicho, C. C. Jagtenberg, and J. J. van Hoorn, “Tackling a VRP challenge to redistribute scarce equipment within the time windows using metaheuristic algorithms,” EURO J. Transp. Logist., vol. 8, pp. 561–595, 2019.
16. S. B. Vieira, M. G. Ribeiro, and L. Bahiense, “Metaheuristics with variable diversity control and neighbourhood search for the heterogeneous site-dependent multi-depot multi-trip periodic vehicle routing problem,” Comput. Oper. Res., vol. 153, Art. no. 106189, 2023.
17. M. Tadaros, A. Migdalas, N. Hassan Quttineh, and T. Larsson, “Evaluating metaheuristic solution quality for a hierarchical vehicle routing problem by strong lower bounding,” Oper. Res. Perspect., vol. 14, Art. no. 100332, 2025.
18. R. Elshaer and H. Awad, “A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants,” Comput. Ind. Eng., vol. 140, Art. no. 106242, Feb. 2020.
19. S. Kirkpatrick, C. D. Gelatt, and P. M. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, pp. 671–680, 1983.
20. A. Colorni, M. Dorigo, and V. Maniezzo, “Distributed optimization by ant colonies,” in Proc. Eur. Conf. Artif. Life, F. Varela and P. Bourgine, Eds. Amsterdam, The Netherlands: Elsevier, 1991.
21. F. Glover, “Future paths for integer programming and links to artificial intelligence,” Comput. Oper. Res., vol. 13, no. 5, pp. 533–549, 1986.
22. M. Kumari, P. K. De, K. Chaudhuri, and P. Narang, “Utilizing a hybrid metaheuristic algorithm to solve capacitated vehicle routing problem,” Results Control Optim., vol. 13, Art. no. 100292, Dec. 2023.
23. K. Niyomphon and W. Nakkiew, “Application of metaheuristics for multi-trip capacitated vehicle routing problem with time window,” Prod. Eng. Arch., vol. 30, no. 3, Sep. 2024.
24. M. K. Zuhanda, Hartono, S. A. R. S. Hasibuan, and Y. Y. Napitupulu, “An exact and metaheuristic optimization framework for solving vehicle routing problems with shipment consolidation using population-based and swarm intelligence,” Decis. Anal. J., vol. 13, Art. no. 100517, Dec. 2024.
25. M. J. C. S. Reis, “An adaptive hybrid metaheuristic for solving the vehicle routing problem with time windows under uncertainty,” Comput. Mater. Continua, vol. 85, no. 2, pp. 3023–3039, Sep. 2025.
26. J. A. G. Willard, “Vehicle routing using r-optimal tabu search,” M.S. thesis, The Management School, Imperial College, London, U.K., 1989.
27. V. M. Pureza and P. M. Franca, “Vehicle routing problem via tabu search metaheuristic,” Tech. Rep. CRT-347, Centre for Research on Transportation, Montreal, Canada, 1991.
28. M. Gendreau, G. Laporte, and J. Y. Potvin, “Metaheuristics for vehicle routing problem,” Les Cah. GERAD, Tech. Rep. G-98-52, 1999.
29. J. F. Nash, “Non-cooperative games,” Ann. Math., vol. 54, pp. 286–295, 1951.
30. O. J. Chen, M. Ben-Akiva, and E. Moshe, “Game theoretic formulations of interaction between dynamic traffic control and dynamic traffic assignment,” Transp. Res. Rec., no. 1617, pp. 179–188, 1998.
31. M. G. H. Bell, “A game theoretic approach to measuring the performance reliability of transport networks,” Transp. Res., Part B, vol. 34, pp. 533–546, 2000.
32. M. G. H. Bell and C. Cassir, “Risk-averse user equilibrium traffic assignment: An application of game theory,” Transp. Res., Part B, vol. 36, no. 8, pp. 671–681, 2002.
33. Y. Caseau and F. Laburthe, “Heuristics for large constraint vehicle routing problems,” J. Heuristics, vol. 5, pp. 281–303, 1999.
34. M. G. H. Bell and Y. Iida, Transportation Network Analysis. Chichester, U.K.: John Wiley & Sons, 1997.