توسعه مدل ریاضی چندهدفه برای مسأله مسیریابی وسایل نقلیه ناهمگن تحت شرایط بحران

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

نویسندگان

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

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

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

چکیده

مسأله مسیریابی بهینه برای انتقال مجروحین و کمک­رسانی امداد از مسائل مهم و اساسی به هنگام وقوع بحران می­باشد در هنگام وقوع بحران اهمیت دو فاکتور زمان و هزینه برای کمک­رسانی امداد و نجات مجروحین دو چندان می­شود. در  این مقاله هدف یافتن مسیر بهینه­ برای رسیدن از یک مرکز امداد و نجات تا یک مرکز بحران است. مدل ریاضی ارائه شده کمینه­کردن زمان و هزینه را برای دسترسی به مراکز بحران هدف قرار داده است و همچنین مفروضاتی همچون چندانباره­ بودن، چندمسیره­­ بودن، چندسناریو ­بودن، تحویل انشعابی، چندمحصولی، ناهمگنبودن وسایل­نقلیه و پنجره ­زمانی را به صورت همزمان در نظرگرفته است. با توجه به اینکه در مواقع بحرانی مقادیر برخی از پارامترها از قبیل تقاضا و زمان سفر قطعی نیستند، در این مقاله با در نظرگرفتن مفروضات بیان شده و غیرقطعی در نظرگرفتن پارامترهای تقاضا و زمان سفر مسأله مربوطه به مسأله واقعی نزدیکتر شده است. در صورتیکه بیشتر مسائلی که در این زمینه مطرح شده­است مفروضات بیان شده را به صورت همزمان مورد بررسی قرار نداده­اند و پارامترهای ذکرشده (زمان و تقاضا) نیز به صورت قطعی در نظرگرفته شده است. در نهایت برای یافتن جواب­های دقیق باتوجه به چندهدفه بودن مدل و فازی بودن پارامترهای تقاضا و زمان سفر از روش محدودیت اپسیلون در ابعاد کوچک بهره گرفته شده و در ادامه با توجه به NP-Hard بودن مسأله برای حل آن در ابعاد بزرگ از الگوریتم­های فراابتکاری  NSGA-IIو MOHS استفاده شده که بر روی 15 مسأله در اندازه­های مختلف حل شده که نتایج بدست آمده از حل مسائل عددی نشان می­دهد هر دو الگوریتم توانایی بالایی در تولید جواب­های مناسب در زمان مناسب را دارند به طوری که برای حل بزرگترین و پیچیده­ترین مسأله زمانی کمتر از 480 ثانیه صرف شده است که با توجه به NP-Hard بودن، غیرقطعی­ بودن و چند­هدفه ­بودن مدل بسیار مناسب است. 

کلیدواژه‌ها

موضوعات


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

Development of a Multi-Objective Mathematical Model for a Heterogeneous Vehicle Routing Problem under Crisis

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

  • Fariba Farahbakhsh 1
  • Reza Tavakkoli-Moghaddam 2
  • Vahid Reza Ghezavati 3
1 MSc. Grad., School of Industrial Engineering, Azad University, South Tehran Branch, Tehran, Iran
2 Professor, School of Industrial Engineering, University of Tehran, Tehran, Iran
3 Assistant Professor, School of Industrial Engineering, Azad University, South Tehran Branch, Tehran, Iran
چکیده [English]

The optimal routing for transferring the wounded and relief assistance is a major problem in the event of a crisis. At this time the importance of two factors, namely time and money, in order to help and rescue the injured is doubled. This paper aims to find the most optimal route from a rescue center to the crisis center. The presented mathematical model aims to minimize the time and cost of accessing a crisis center. We also consider some assumptions, such as multiple storages, multiple paths, multiple scenarios, split delivery, multiple products, heterogeneity of the vehicles and time. Given that the values of some parameters, such as demand and time of the travel are uncertain, in which we state them in respect to the former mentioned assumptions. Considering these parameters uncertain makes them closer to the real problem. Most of the issues raised in this field have not considered all assumptions at the same time and they have considered the mentioned parameters (time and demand) as definitive. Finally, in order to find accurate answers regarding to multiple objectives of the model and different phases of parameters (i.e., time and demand), we use ε-constraint method in small-scale problems. Then because this problem is NP-hard, two meta-heuristic algorithms, namely MOHS and NSGA-II, are used to solve 15 issues large-scale problems. The results numerically show that both algorithms have high potential in producing good solutions at the right time and they are used to solve the largest and most complex issue in less than 480 seconds. This model is very suitable and uncertain with multiple objectives. 

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

  • Vehicles routing
  • Crisis
  • Relief Logistics
  • harmony search
-­ Berkoune, D., Renaud, J., Rekik, M., Ruiz, A., (2012) "Transportation in disaster response operations", Socio-Economic Planning Sciences, Vol. 46, PP. 23-32.
- Bozorgi, A., Jabalameli, M.S., (2011)" A multi objective robust stochastic programming model for disaster relief logistics under uncertainty", Production Economics VoL.35, pp. 905-933.
- Chen, HK., Chou, HW., Hsueh, C.F., (2008) "Dynamic vehicle routing for relief logistics in natural disasters", Source: Vehicle Routing Problem, Book edited by: Tonci Caric and Hrvoje Gold, pp. 142.
 
- Dantzig, G.B., Ramser, J.H., (1959) "the truck dispatching problem", management science, Vol.6, No.1, pp.80-91.
- Deb, K., pratap, A., Agrwal, s., Meyarivan, T., (2002) "A fast and elitist multi objective genetic algorithm: NSGA-II", IEEE Transaction on Evolutionary Computation, Vol.6, NO.2, pp. 182-197.
- Geem, Z.W., Kim J.H, Loganathan G.V., (2001) "A new heuristic optimization algorithm: harmony search", Simulations, vol. 76, pp. 60–68.
- Haimes, Y.Y., Lasdon, L.S., Wismer, D.A., (1971) "On a bicriterion formulation of the problems of integrated system identification and system optimization", IEEE Transactions on system, vol. 1, pp. 296–297.
- Hamedi, M., Haghani, A., (2012) "Reliable transportation of humanitarian supplies in disaster response", Social and Behavioral Sciences, vol. 54, pp.1205–1219.
- Jiménez, M., Arenas, M., Bilbao, A., Rodríguez, V., (2007) "Linear programming with fuzzy parameters - An interactive method resolution", European Journal of Operational Research, vol. 177, PP.1599-1609.
- Michael, H., Karen, R., SmilowitzaB., (2013) "A continuous approximation approach for assessment routing in disaster relief", Transportation Research Part B: Methodological, Vol. 50, pp. 20-41.
- Najafi, M., Eshghi, K.(2013) "A multi-objective robust optimization model for logistics planning in the earthquake response phase", Transportation Research Part E: Logistics and Transportation Review, Vol. 49, pp. 217–249.
- Nasiri, M., Shishehgar, S., (2014) "Disaster Routing by considering heterogeneous vehicles and reliability of routes using an MADM approach", Uncertain Supply Chain Management, Vol. 2, pp. 137-150.
- Talarico, L., Haijun, W., Sorensen, K., (2014) "Ambulance routing for disaster response with patient groups", Computers and Operations Research, Vol. 56, pp. 120-133.
- Talebian Sharif, M., Salari, M., (2015) "A GRASP algorithm for a humanitarian relief transportation problem", Engineering Applications of Artificial Intelligence, vol. 41, pp. 259–269.
-  Zheng, Yn-Jun., Chen, Sheng-Yong., Ling, Hai-Feng., (2015)" Evolutionary optimization for disaster relief operations: A survey", Soft Computing, vol. 27, pp. 553-566.