رویکرد استوار سناریو محور برای مساله مسیریابی وسایط نقلیه تحت شرایط رقابتی با استفاده از الگوریتم تکامل تفاضلی بهبودیافته

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

نویسندگان

1 دانشجوی دوره دکتری، گروه مهندسی صنایع‌، واحد علوم و تحقیقات تهران، دانشگاه آزاد اسلامی، تهران، ایران

2 استاد، دانشکده مهندسی صنایع، پردیس دانشکدههای فنی، دانشگاه تهران، ایران

3 دانشیار، دانشکده مهندسی صنایع و سیستم‌ها، دانشگاه صنعتی اصفهان، اصفهان، ایران

4 استادیار‌، دانشگاه آزاد اسلامی، واحد علوم و تحقیقات تهران، گروه مهندسی صنایع، تهران، ایران

چکیده

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

کلیدواژه‌ها

موضوعات


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

Robust optimization approach in a competitive vehicle routing problem in an uncertain condition by using improved differential evolution

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

  • Alireza Salamat-Bakhsh 1
  • Reza Tavakkoli-Moghaddam 2
  • Mehdi Alinaghian 3
  • Ismail Najafi 4
1 Science and Research Branch, Islamic Azad University
2 Professor, School of Industrial Engineering, College of Engineering, University of Tehran
3 Isfahan University of Technology
4 Science and Research Branch, Islamic Azad University
چکیده [English]

A vehicle routing problem (VRP) is an important issue that has attracted great attention of researchers in recent years. This paper presents a competitive VRP to get short routes with the maximum sale by providing suitable services to customers before delivering the goods to other competitive distributors. To distribute the goods with a short lifetime, in which customers need a special device for keeping them, the arriving time to customers effects on a number of sales, in which classical VRPs are unable to calculate these kinds of assumptions. According to the real world, the arriving time of the competitors is uncertain because of customer demands, traffic, weather conditions, etc. A scenario-based approach is used to handle the uncertainty of the arriving time of rivals. The purpose of this paper is to solve this problem by optimizing the sale of products to customers before delivering the products to other competitor distributors in an uncertain condition by robust optimization. To evaluate the performance of the presented model, the improved differential evolution (IDE) algorithm is used. The related results in small and medium-sized problems are compared with the result obtained by an exact solution method. Additionally, in order to evaluate the performance of the proposed IDE algorithm, a few sample tests in large sizes are solved and their results are compared with other two differential evolution algorithms. The results show that the proposed IDE algorithm has a suitable accuracy and performance for solving the presented model.

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

  • vehicle routing problem
  • Uncertainty
  • robust optimization
  • Competitive environment
  • Differential evolution algorithm
-  سلامت بخش، علی‌رضا، توکلی مقدم، رضا و نوروزی، نرگس (1395) ”مسأله مسیریابی وسایل نقلیه باز با در نظر گرفتن رضایت ‌رانندگان: الگوریتم تکاملی چند هدفه بر مبنای تجزیه“ فصل‌نامه مهندسی حمل و نقل، سال هفتم،  شماره سوم‌، بهار 1395، ص 449-462.
-  Alinaghian, M., Ghazanfari, M., Salamatbakhsh, A. and Norouzi, N. (2012) “A new competitive approach on multi-objective periodic vehicle routing problem”, International Journal of Applied Operations Research, Vol. 1, pp. 33-41.
-  Archetti, C., Savelsbergh, M. and Speranza, M. (2016) “Vehicle routing problem with occasional drivers”, European Journal of Operational Research, Vol. 254, pp. 472–480.
-  Bahri, O., Ben Amor, N. and Talbi, E. G. (2016) “Robust routes for the fuzzy multi-objective vehicle routing problem”, Proc. of the 8th IFAC Conference on Manufacturing Modeling, Management and Control, pp.769-774.
-  Bazgan, C. and Aissi, H. (2009) “Min-max and min-max regret versions of combinatorial optimization problems: A survey”, Journal of Operational Research, Vol. 197, pp. 427-438.
-  Cordeau, J. F., Gendreau, M. and Laporte, G. (1997) “A tabu search heuristic for periodic and multi-depot vehicle routing problems”, Networks, An International Journal, Vol. 30,  pp. 105-119.
-  Das, S. and Suganthan, P. N. (2011) “Differential evolution: A survey of the state-of-the-art”, IEEE Transaction on Evolutionary Computation, Vol. 15, pp. 4-31.
-  Dantzig, G. and Ramser, J. H. (1959) “The truck dispatching problem”, Management Science, Vol. 6, pp. 80-91.
-  Erera, A. L., Morales, J. C. and Savelsbergh, M. (2010) “The vehicle routing problem with stochastic demand and duration constraints”, Transportation Science, Vol. 44, pp. 474–49.
-  Gounaris, C. E., Wiseman, W. and Floudas, C. A. (2013) “The robust capacitated vehicle routing problem under demand uncertainty”, Journal of Operations Research, Vol. 61, pp. 677–693.
-  Golden, B., Raghavan, S. and Wasil, E. A. (2008) “The vehicle routing problem: latest advances and new challenges”, Operations Research/Computer Science Interfaces Series, Vol. 43. Boston: Springer.
-  Goodson, J. C., Ohlmann, J. W. and Thomas, B. (2012) “Cyclic -order neighborhoods with application to the vehicle routing problem with stochastic demand”, European Journal of Operational Research, Vol. 2172, pp. 312–323.
-  Kasperski, A. and Kule, M. (2009) “Choosing robust solutions in discrete optimization problems with fuzzy costs”, Journal of Fuzzy Sets and Systems, Vol. 160, pp. 384-395.
-  Kos, C. and Karaoglan, I. (2016) “The green vehicle routing problem: A heuristic based exact solution approach”, Applied Soft Computing, Vol. 39, pp. 154–164.
-  Kunnapapdeelert, S. and Kachitvichyanukul, V. (2013) “Differential evolution algorithm for generalized multi depot vehicle routing problem with pickup and delivery requests.”  In:Lin Y. K., Tsao Y. C., Lin, S.W. (Eds.) Proceedings of the Institute of Industrial Engineers Asian Conference 2013. Springer, Singapore.
-  Lenstra, J. K. and Rinnooy, Kan, A. H. G. (1981) “Complexity of vehicle and scheduling problem”, Networks, Vol. 11, pp. 221-227.
-  Leung, S. C. H. and Chan S. S. W. (2009) “A goal programming model for aggregate production planning with resource utilization constraint”, Computers & Industrial Engineering, Vol. 56, pp. 1053-1064.
-  List, B. F., Wood, B. and Nozick, L. K. (2003) “Robust optimization for fleet planning under uncertainty”, Transportation Research Part E: Logistics and Transportation Review, Vol. 39, pp. 209–227.
-  L´opez Cruz, I. L., , Willigenburg, van L.G., and Van Straten, G. (2005) “Efficient differential evolution algorithms for multimodal optimal control problems”, Applied Soft Computing, Vol. 3, pp. 97-122.
-  Mulvey, J. M., Vanderbei, R. J. and Zenios, S. A. (1995) “Robust optimization of large-scale systems”, Operations Research, Vol. 43, pp. 264–281.
-  Norouzi, N., Sadegh-Amalnick, M. and Tavakoli-Moghadam, R. (2015) “A time-dependent vehicle routing problem developed by improved simulated annealing”, Proceedings of Romanian Academy - Series A, Vol. 16, pp. 458–465.
-  Norouzi, N., Tavakkoli-Moghaddam, R., Gazanfari, M., Alinaghian, M. and Salamatbakhsh, A.  (2012) “A new multi-objective competitive open vehicle routing problem solved by particle swarm optimization”, Journal of Manufacturing Systems, Vol. 12, pp. 609-633.
-  Novoa, C. and Storer, R. (2009) “An approximate dynamic programming approach for the vehicle routing problem with stochastic demands”, ‌European Journal of Operational Research, Vol. 196, pp. 509–515.
-  Pan, F. and Nagi, R. (2010) “Robust supply chain design under uncertain demand in agile manufacturing”, Computers and Operations Research, Vol. 37, pp. 668-683.
-  Price, K.V., Storn, R. M. and Lampinen, J. A. (2005) “Differential evolution: A practical approach to global optimization”, Natural Computing Series, Springer.
-  Qin, A. K. and Suganthan, P. N. (2005) “Self-adaptive differential evolution algorithm for Numerical Optimization.” In: Proceedings of the IEEE Congress on Evolutionary Computation, vol. 2, pp. 1785–1791.
-  Solano-Charris, E., Prins, C. and Santos, A. (2014) “Heuristic approaches for the robust vehicle routing problem”, Combinatorial Optimization, Vol. 8596, pp. 384-395.
-  Storn, R. and Price, K. (1997) “Differential evolution – A simple and efficient heuristic for global optimization over continuous spaces”, Journal of Global Optimization, Vol. 4, pp. 359-431.
-  Sungur, I., Ordonez, F. and Dessouky, M. (2008) “A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty”, IIE Transactions, Vol. 40, pp. 509–523.
-  Tavakkoli-Moghaddam, R., Gazanfari, M., Alinaghian, M., Salamatbakhsh, A. and Norouzi, N. (2011) “A new mathematical model for a competitive vehicle routing problem with time windows solved by simulated annealing”, Journal of Manufacturing Systems, Vol. 30, pp. 83-92.
Yu, C. S. and Li H. L. (2000) “A robust optimization model for stochastic logistic problems”, International Journal of Production Economics, Vol. 64, pp. 385-397.