مسئله مسیریابی وسایل نقلیه مبتنی بر نظریه بازی با هدف کاهش ریسک حمل کالای ارزشمند

نوع مقاله : علمی - پژوهشی

نویسندگان

1 استادیار، دانشکده مهندسی صنایع، دانشگاه علم و صنعت ایران، تهران، ایران

2 دانشجوی کارشناسی ارشد، دانشکده مهندسی صنایع، دانشگاه علم و صنعت ایران، تهران، ایران

چکیده

در این مقاله رویکردی موثر برای کاهش ریسک مسیریابی وسایل نقلیه همراه با پنجره زمانی جهت حمل کالاهای ارزشمند ارائه می­شود. مدل در نظر گرفته شده برای حمل این نوع کالا دارای دو تابع هدف کمینه سازی مسافت و ریسک است. تابع هدف کاهش ریسک وابسته به مقدار کالای حمل شده، احتمال حمله مسلحانه تروریستی و احتمال موفقیت سرقت است. احتمال حمله تروریستی با استفاده از نظریه بازی­ها و تعیین احتمال انتخاب استراتژی­های مختلف آن  تخمین زده می شود، به نحوی که یک بازی رقابتی دو نفره با جمع صفر میان تروریست و حمل­کننده کالای ارزشمند صورت می­گیرد و نقطه تعادل بازی یک استراتژی ترکیبی از مجموعه استراتژی­های بازیکن است. همچنین با استفاده از رویکردهای موثر تصمیم گیری چند معیاره، احتمال موفقیت ارزیابی شده و برای افزایش امنیت حمل کالای ارزشمند نسبت به تغییر روزانه مسیرهای توزیع کالا اقدام می شود. برای حل این مدل پیشنهادی، یک الگوریتم ژنتیک ترکیبی چند هدفه موثر طراحی می­گردد. کارآیی و اثربخشی الگوریتم روی مسائل آزمایشی استانداد در ادبیات موضوع  مورد بررسی قرار  می‌گیرد که نتایج حاصل شده نشانگر موثر بودن راه حل پیشنهادی است. 

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

A Game Theory Based Vehicle Routing Problem with Risk Minimizing of Valuable Commodity Transportation

نویسندگان [English]

  • Seyed Farid Ghannadpour 1
  • Fatemeh Zandiyehh 2
1 Assistant Professor, Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran
2 MSc. Student, Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran
چکیده [English]

In this paper, an effective approach for risk minimizing vehicle routing with time window for valuable commodities transportation is proposed. The proposed model pursues two objective functions including distance minimization and risk minimization. The risk minimization objective depends on the size of goods transported, the probability of an armed terrorist attack, and the probability of the success of robbery. The probability of a terrorist attack is estimated using game theory approach for different strategies, in such a way that a two-player, zero-sum game is played between the terrorist and the valuable goods carrier. The equilibrium of such a game is a strategy combining set of player's strategies. Moreover, the probability of success is evaluated using multi-criteria decision-making, and in order to increase the security of valuable commodities transportation, distribution routes will change on a daily basis. An effective multi-objective hybrid genetic algorithm is designed to tackle the proposed model. The efficiency and effectiveness of the algorithm are also examined through standard data sets, and the results indicate the effectiveness of the proposed solution algorithm.

کلیدواژه‌ها [English]

  • Hybrid genetic algorithm
  • risk
  • Valuable commodity
  • Vehicle routing problem with time window
  • game theory
- توکلی مقدم، رضا، علینقیان، مهدی، نوروزی، نرگس و سلامت بخش، علیرضا (1390) "حل یک مدل جدید برای مسئله مسیریابی وسائط نقلیه با در نظر گرفتن ایمنی حمل و نقل"، فصلنامه مهندسی حمل و نقل، دوره دوم، شماره 3، بهار ، ص. 223-237
- ذوالفقاری،  الف و کرکه آبادی، ز. (1392) "مسیریابی هوشمند اکیپ های امدادی با استفاده ازالگوریتم تئوری بازیها نمونمه موردی: شهر سمنان"،  فصلنامه علمی-پژوهشی مهندسی حمل و نقل، دوره پنجم، شماره اول، ص. 19-32.​
-  Ackerman, G. A., Zhuang, J. and Weerasuriya, S. (2017) "Cross‐Milieu Terrorist Collaboration: Using Game Theory to Assess the Risk of a Novel Threat", Risk Analysis, Vol. 37, No. 2, pp. 342-371.
- Androutsopoulos, K. N. and Zografos, K. G. (2012) "A bi-objective time-dependent vehicle routing and scheduling problem for hazardous materials distribution", EURO Journal on Transportation and Logistics, Vol. 1, No. 1-2, pp. 157-183.
- Asimit, V. and Boonen, T. J. (2018) "Insurance with multiple insurers: A game-theoretic approach", European Journal of Operational Research, Vol. 267, No. 2, pp. 778-790.
- Beheshti Nia, M. A. and Ghasemi, A. (2017) "A multi-objective and integrated model for supply chain scheduling optimization in a multi-site manufacturing system", Engineering Optimization, Vol. 50, No. 1, pp. 1-19.
- Beheshti Nia, M. A., Ghasemi, A. and Farokhnia, M. (2018) "Supply chain scheduling and routing in multi-site manufacturing system (case study: a drug manufacturing company)", Journal of Modelling in Management, Vol. 13, pp. 27-49.
- Bodford, J. E. and Kwan, V. S. (2018) "A game theoretical approach to hacktivism: is attack likelihood a product of risks and payoffs", Cyberpsychology, Behavior and Social Networking, Vol. 21, No. 2, pp. 73-77
- Bodin, L., Assad, A., Ball, M. and Golden, B. (1983) "Routing and scheduling of vehicles and crews", Computers and Operations Research, Vol. 10, No. 2, pp. 63-211.
- Borumand, A. and Beheshti Nia, M. A. (2018) "A developed genetic algorithm for solving the multi-objective supply chain scheduling problem", Kybernetes, Vol. 47, No. 7, pp.  1401-1419. https://doi.org/10.1108/K-07-2017-0275
- Bozkaya, B., Salman, F. S. and Telciler, K. (2017) "An adaptive and diversified vehicle routing approach to reducing the security risk of cash‐in‐transit operations", Networks, Vol. 69, No. 3, pp. 256-269.
- Bula, G. A., Gonzalez, F. A., Prodhon, C., Afsar, H. M. and Velasco, N. M. (2016) "Mixed Integer Linear Programming Model for Vehicle Routing Problem for Hazardous Materials Transportation", IFAC-PapersOnLine, Vol. 49, No. 12, pp. 538-543.
- Bula, G. A., Prodhon, C., Gonzalez, F. A., Afsar, H. M. and Velasco, N. (2017) "Variable neighborhood search to solve the vehicle routing problem for hazardous materials transportation", Journal of Hazardous Materials, Vol. 324, No. 44, pp. 472-480.
- Chen, Y., Cowling, P., Polack, F., Remde, S. and Mourdjis, P. (2017) "Dynamic optimisation of preventative and corrective maintenance schedules for a large scale urban drainage system", European Journal of Operational Research, Vol. 257, No. 2, pp. 494-510.
- Cox Jr, L. A. T. (2009) "Game theory and risk analysis", Risk Analysis, Vol. 29, No. 8, pp. 1062-1068.
- Du, J., Li, X., Yu, L., Dan, R. and Zhou, J. (2017) "Multi-depot vehicle routing problem for hazardous   materials   transportation:   A    fuzzy bilevel programming", Information Sciences, Vol. 399, pp. 201-218.
- Ghannadpour, S. F., Noori, S., Tavakkoli-Moghaddam, R. and Ghoseiri, K. (2014) "A multi-objective dynamic vehicle routing problem with fuzzy time windows: Model, solution and application", Applied Soft Computing, Vol. 14, pp. 504-527.
- Ghoseiri, K. and Ghannadpour, S. F. (2010) "Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm', Applied Soft Computing, Vol. 10, No. 4, pp. 1096-1107.
- Hafezalkotob, A., Mahmoudi, R., Hajisami, E. and Wee, H. M. (2018) "Wholesale-retail pricing strategies under market risk and uncertain demand in supply chain using evolutionary game theory", Kybernetes,  https://doi.org/10.1108/K-02-2017-0053
- Holland, J. H. (1975) "Adaptation in natural and artificial systems. An introductory analysis with application to biology, control, and artificial intelligence", Ann Arbor, MI: University of Michigan Press, pp. 439-444.
- Hu, H., Guo, S., Ma, H., Li, J. and Li, X. (2017) "A credibilistic mixed integer programming model for time-dependent hazardous materials vehicle routing problem", Journal of Uncertain Systems, Vol. 11, No. 3, pp. 163-175.
- Kahfi, A. and Tavakkoli-Moghaddam, R. (2016) "Solving a multi-depot vehicle routing problem based on reduction risk by a multi-objective bat algorithm", Quarterly Journal of Transportation Engineering, Vol. 6, No. 3, pp. 507-522. (in Persian).
- Kazantzi,  V., Kazantzis, N. and Gerogiannis, V. C.  (2011)  "Risk   informed   optimization   of    hazardous material multi-periodic transportation model", Journal of Loss Prevention in the Process Industries, Vol. 24, No. 6, pp. 773-767.
- Laporte, G., Mesa, J. A. and Perea, F. (2010) "A game theoretic framework for the robust railway transit network design problem", Transportation Research Part B: Methodological, Vol. 44, No. 4, pp. 447-459.
- Liu, H. and Song, Y. (2014) "Dealing with vehicle routing problem under multi-objective using improved genetic algorithm", The 26th Chinese Control and Decision Conference, Changsha: 31 May-2 June 2014.
- Parsafard, M., Esmaeel, A., Masoud, K., Mohammadreza, N. and Li, X. (2015) "Practical approach for finding optimum routes for fuel delivery trucks in large cities", Transportation Research Record: Journal of the Transportation Research Board, Vol. 2478, pp. 66-74.
- Pradhananga, R., Taniguchi, E. and Yamada, T. (2010) "Ant colony system based routing and scheduling for hazardous material transportation", Procedia-Social and Behavioral Sciences, Vol. 2, No. 3, pp. 6097-6108.
- Pradhananga, R., Taniguchi, E., Yamada, T. and Qureshi, A. G. (2014a) "Bi-objective decision support system for routing and scheduling of hazardous materials", Socio-Economic Planning Sciences, Vol. 48, No. 2, pp. 135-148.
- Pradhananga, R., Taniguchi, E., Yamada, T. and Qureshi, A. G. (2014b) "Environmental analysis of Pareto optimal routes in hazardous material transportation", Procedia-Social and Behavioral Sciences, Vol. 125, pp. 506-517.
- Qi, Y., Hou, Z., Li, H., Huang, J. and Li, X. (2015) "A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows", Computers and Operations Research, Vol. 62, pp. 61-77.
- Reil, S., Bortfeldt, A. and Mönch, L. (2018) "Heuristics for vehicle routing problems with backhauls, time windows and 3D loading constraints", European Journal of Operational Research, Vol. 266, No. 3, pp. 877-894.
- Reilly, A., Nozick, L., Xu, N., and Jones, D. (2012) "Game theory-based identification of facility use restrictions for the movement of hazardous    materials    under   terrorist    threat",
Transportation Research Part E: Logistics and Transportation Review, Vol. 48, No. 1, pp. 115-131.
- Salani, M., Duyckaerts, G., and Swartz, P. G. (2010) "Ambush avoidance in vehicle routing for valuable delivery", Journal of Transportation Security, Vol. 3, No. 1, pp. 41-55.
- Saleh, M., Soeanu, A., Ray, S., Debbabi, M., Berger, J. and Boukhtouta, A. (2012) "Mechanism design for decentralized vehicle routing problem", Proceedings of the 27th Annual ACM Symposium on Applied Computing, Trento: 26 - 30 March 2012.
- Schneider, M., Schwahn, F. and Vigo, D. (2017) "Designing granular solution methods for routing problems with time windows", European Journal of Operational Research, Vol. 263, No. 2, pp. 493-509.
- Sharafi, A., and Bashiri, M. (2016). "Green Vehicle Routing Problem with Safety and Social Concerns", Journal of Optimization in Industrial Engineering, Vol. 10, No. 21, pp. 93-100.
- Solomon, M. M. (1987). "Algorithms for the vehicle routing and scheduling problems with time window constraints", Operations research, Vol. 35, No. 2, pp.  254-265.
- Talarico, L., Reniers, G., Sörensen, K., and Springael, J. (2015). "MISTRAL: A game-theoretical model to allocate security measures in a multi-modal chemical transportation network with adaptive adversaries", Reliability Engineering and System Safety, Vol. 138, pp. 105-114.
- Talarico, L., Sörensen, K., and Springael, J. (2015a). "A biobjective decision model to increase security and reduce travel costs in the cash‐in‐transit sector", International Transactions in Operational Research, Vol. 24, No. 1-2, pp. 59-76.
- Talarico, L., Sörensen, K. and Springael, J. (2015b) "Metaheuristics for the risk-constrained cash-in-transit vehicle routing problem", European Journal of Operational Research, Vol. 244, No. 2, pp. 457-470.
- Talarico, L., Springael, J., Sörensen, K. and Talarico, F. (2017) "A large neighbourhood metaheuristic for the risk-constrained cash-in-transit vehicle routing problem", Computers and Operations Research, Vol. 78, pp. 547-556.
- Tarantilis, C. D. and Kiranoudis, C. T. (2001)"Using the vehicle routing problem for the transportation of hazardous materials", Operational Research, Vol. 1, No. 1, pp. 67-78.
- Ticha, H. B., Absi, N., Feillet, D. and Quilliot, A. (2017) "Empirical analysis for the VRPTW with a multigraph representation for the road network", Computers and Operations Research, Vol. 88, pp. 103-116.
- Toumazis, I. and Kwon, C. (2015)"Worst-case conditional value-at-risk minimization for hazardous materials transportation", Transportation Science, Vol. 50, No. 4, pp. 1174-1187.
- Valenzuela, P., Lima, D. A. and Granville, S. (2018) "A risk-constrained Energy Reallocation Mechanism for renewable sources with a Marginal Benefit approach", Electric Power Systems Research, Vol. 158, pp. 297-305.
- Vincent, F. Y., Jewpanya, P., Ting, C.-J. and Redi, A. P. (2017) "Two-level particle swarm optimization for the multi-modal team orienteering problem with time windows", Applied Soft Computing, Vol. 61, pp. 1022-1040.
- Wu, C.-K. (2018) "A game theory approach for assessing risk value and deploying search-and-rescue resources after devastating tsunamis", Environmental Research, Vol. 162, pp. 18-26.
- Yan, S., Wang, S.-S. and Wu, M.-W. (2012) "A model with a solution algorithm for the cash transportation vehicle routing and scheduling problem", Computers and Industrial Engineering, Vol. 63, No. 2, pp. 464-473.
- Yuan, W., Wang, J., Li, J., Yan, B. and Wu, J. (2018) "Two-stage heuristic algorithm for a new  model  of  hazardous material multi-depotvehicle routing problem", UK Workshop on Computational Intelligence, Vol. 650, pp. 362-366.
- Zegordi, S. H., Abadi, I. K. and Beheshti Nia, M. (2010) "A novel genetic algorithm for solving production and transportation scheduling in a two-stage supply chain", Computers and Industrial Engineering, Vol. 58, pp. 373-381.
- Zegordi, S. H. and Beheshti Nia, M. A. (2009) "Integrating production and transportation scheduling in a two-stage supply chain considering order assignment", The International Journal of Advanced Manufacturing Technology, Vol. 44, pp. 928-939.
- Zheng, B. (2010) "Multi-objective vehicle routing problem in hazardous material transportation", ICLEM 2010: Logistics For Sustained Economic Development: Infrastructure, Information, Integration, Vol. 387, pp. 3139-3145.
- Zibaei, S., Hafezalkotob, A. and Ghashami, S. S. (2016) "Cooperative vehicle routing problem: an opportunity for cost saving", Journal of Industrial Engineering International, Vol. 12, No. 3, pp. 271-286.