مسأله مسیریابی کمان ظرفیتدار با تقاضای فازی به همراه مطالعه موردی

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

نویسندگان

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

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

چکیده

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

کلیدواژه‌ها


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

The Capacitated Arc Routing Problem under Fuzzy Demands with a Case Study

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

  • Mehdi Alinaghian 1
  • Mohammadsaeid Sabbagh 1
  • Erfan Babaee Tirkolaee 2
1
2
چکیده [English]

Waste collection is a highly visible municipal service that involves large expenditures and difficult operational problems, plus it is expensive to operate in terms of investment costs (i.e. vehicles fleet), operational costs (i.e. fuel, maintenances) and making small improvements in this area can lead to huge savings in municipal expenditures. Among the issues raised in this context, changes in the pattern of waste collection in order to explore different, and consequently considering the uncertainty of the data. Study of urban waste collection problem in terms of uncertainty can help managers and decision-makers to make appropriate decisions.
In this paper, The Capacitated Arc Routing Problem under fuzzy demands is described. Due to uncertain nature of demands (waste amount) and the difficulty of determining the real amount, a fuzzy chance constrained programming is designed to model the problem, based on the fuzzy credibility theory. A hybrid genetic algorithm incorporated with a heuristic algorithm, a simulated annealing, a genetic algorithm and a stochastic simulation is developed and proposed to solve the model. The experimental results have shown that the proposed algorithm has appropriate performance in comparison with CPLEX. At the end of paper, a case study in urban waste collection of Isfahan is implemented to determine the optimal policy in uncertain circumstances.

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

  • Capacitated arc routing problem
  • Hybrid genetic algorithm
  • Stochastic simulation
  • Fuzzy credibility theory
  • urban waste collection
-توکلی مقدم،رضا، محمود سلطانی، فرزاد و محمودآبادی، عباس (1392) توسعه مدل ریاضی مسأله مسیریابی حمل و نقل مواد سوختی تحت شرایط فازی مطالعه موردی،" فصلنامه مهندسی حمل و نقل، سال چهارم، شماره سوم، بهار.
-مطیعیان، حمید، سعدی مسگری، محمد، نعیمی، احید (1391) "بهینه سازی مسیر تردد سرویسهای حمل و نقل یک شرکت با استفاده از خوشه بندی و الگوریتم ژنتیک،" فصلنامه مهندسی
حمل و نقل، سال سوم، شماره چهارم، تابستان 
- مهدوی،ایرج، توکلی مقدم، رضا و قاضی زاده هاشمی، سید مصطفی (1388) مسیریابی وسائط نقلیه و تعیین تعداد ماشینهای جمع آوری زباله با استفاده از یک روش فرا ابتکاری- یک مطالعه موردی،" پژوهشنامه حمل و نقل، سال هفتم، شماره اول، بهار.
-Beltrami, E. and Bodin, L. D. )1974( “Networks and vehicle routing for municipal waste collection”, Networks, 4, pp.65-94.
- Bautista, J., Fernández, E. and Pereira, J. (2008) "Solving an urban waste collection problem using ants heuristics", Computers and Operations Research, 35, pp.3020-3033.
-Bing, X. Keizer, M. Bloem hof-Ruwaard, J. and van der Vorst, J. (2014)” Vehicle routing for the eco-efficient collection of household plastic waste”, Waste Management, 34)4(, pp.719–729.
-Chu, F., Labadi, N. and Prins, C. (2005). “Heuristics for the periodic capacitated arc routing problem”, Journal of Intelligent Manufacturing, 16, pp.243-251.
- Filippi, C. and Del Pia, A. (2006) "A variable neighborhood descent algorithm for a real waste collection problem with mobile depots". International Transactions in Operational Research, 13: pp.125–141
-Fischetti, M., Salazar Gonz´alez, J. J. and Toth, P. (1997) “Branch-and-cut algorithm for the symmetric generalized traveling salesman problem”, Operations Research, No. 45, pp. 378-394.
-Ghaffari-Nasab, N., Ahari, S. G. and Ghazanfari, M. (2013) “A hybrid simulated annealing based heuristic for solving the location-routing problem with fuzzy demands”, Scientia Iranica, 20(3), pp.919-930.
-Kaufman, A. (1975) “Introduction to the theory of fuzzy subsets”, Academic Press, New York.
-Hemmelmayr, V., Doerner, K. F., Hartl, R. F. and Rath, S. )2013( “A heuristic solution method for node routing based solid waste collection problems”, Journal of Heuristics, 19)2(, pp.129-156.
-Liu, B. (2004) “Uncertain theory: An introduction to its axiomatic foundations”, Springer, Berlin.
-Li, J., Borenstein, D. and Mirchandani, P. B. (2008) “Truck scheduling for solid waste collection in the city of Porto Alegre, Brazil”, Omega-International Journal of Management Science, 36)6(, pp.1133-1149.
-Markov, I., Varone, S., de Genève, H. E. D. G. and Bierlaire, M. (2014) “Vehicle routing for a complex waste collection problem”, Presented at 14th. Swiss Transport Research Conference, Monte Verita, Ascona, \may 14-16, 2014.
-Mourao, M. C., Nunes, A. C. and Prins, C. (2009) “Heuristic methods for the sectoring arc routing problem”, European Journal of Operational Research, 196(3), pp.856-868.
-Nahmias, S. (1978) ‘‘Fuzzy variables’’, Fuzzy Sets and Systems, 1, pp. 97–110.
-Ogwueleka T. Ch. (2009) “Municipal solid waste characteristics and management in Nigeria”. Iranian Journal of Environmental Health Science and Engineering, 6(3), pp.173-180.
-Polacek, M., Doerner, K., Hartl, R., and Maniezzo, V. (2007). “A variable neighborhood search for the capacitated arc routing problem with intermediate facilities”, Journal of heuristics, NA: NA.
- Simonetto, E. D. O. and Borenstein, D. (2007) “A decision support system for the operational planning of solid waste collection”, Waste Management, 27, pp.1286-1297.
-Zadeh, L.A. (1965) ‘‘Fuzzy sets’’, Information and Control, 8, pp. 338–353.
-Zadeh, L.A. (1975) ‘‘The concept of a linguistic variable and its application to approximate reasoning’’, Information Sciences, 8, pp. 199–251.