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

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

نویسندگان

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

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

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

چکیده

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

کلیدواژه‌ها

موضوعات


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

Solving a Vehicle Routing Problem Considering Customers’ Satisfaction and Energy Consumption by a Bee Algorithm

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

  • Farhad Salehian 1
  • Reza Tavakkoli-Moghaddam 2
  • Narges Norouzi 3
1 Ph.D. Student, School of Industrial Engineering, University of Tehran, Tehran, Iran
2 Professor, School of Industrial Engineering, University of Tehran, Tehran, Iran
3 PhD. Grad., School of Industrial Engineering, University of Tehran, Tehran, Iran
چکیده [English]

In this paper, a new method is presented for a vehicle routing problem (VRP) with reducing the fuel consumption and maximizing customers’ satisfaction. To reduce the hazardous effects of transportation like land usage, resource and energy consumption, air pollution, global warming, damage to ecosystems and human health, researchers developed optimization models like vehicle routing problem (VRP) and its variants. Generally, the amount of pollution emitted by a vehicle over an arc  depends on many factors like vehicle load, travel speed, travel distance, road slop and etc. Vehicle load has a major effect among other factors on amount of emissions and influences the route selection. On the other hand, this paper considers customers’ satisfaction via considering earliest and latest service time in customer nodes. It is proven that VRPs belong to the category of NP-Hard problems thus due to the complexity of VRP with exact methods in large-scale problems, a meta-heuristic method based on bee algorithm (BA) is proposed. Furthermore, to show the efficiency of the proposed BA, a number of test problems in small and large sizes are solved. Finally, the obtained results are evaluated with the results obtained by GAMS and PSO algorithm.

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

  • Bee algorithm؛ vehicle routing problem
  • reducing fuel consumption
  • customers’ satisfaction
-توکلی مقدم ، رضا، محمود سلطانی، فرزاد و محمودآبادی، عباس (1392) "توسعه مدل ریاضی مسأله مسیریابی حمل ونقل مواد سوختی تحت شرایط فازی - مطالعه موردی"، فصلنامه مهندسی حمل و نقل، دوره 4، شماره 3، صفحه 209-220.
-Ahn, K. and Rakha, H. (2008) “The effects of route choice decisions on vehicle energy consumption and emissions”. Transportation Research: Part D, Vol. 13, No. 3, pp.151–167.
-Banks, A., Vincent, J. and  Anyakoha, C. (2008) “A review of particle swarm optimization. Part II: Hybridization, combinatorial, multi-criteria and constrained optimization, and indicative applications”, Natural Computing, Vol. 7, No. 1, pp. 109–124.
-Bowyer, D. P., Akcelik, R. and Biggs, D. C. (1985) “Guide to fuel consumption analysis for urban traffic management”, Australian Road Research Board Transport Research.
-Clarke, C. and Wright, J. Q. (1994) “Scheduling of vehicle from a central depot to a number of delivery points”, Operations Research, Vol. 12, No. 4, pp. 568-581
-Dantzig, G. and Ramser, J. H. (1959) “The truck dispatching problem”, Management Science, Vol. 6, No. 1, pp. 80-91.
-Ho, S. C. and Haugland, D. (2004) "A tabu search heuristic for the vehicle routing problem with time windows and split deliveries", Computers and Operations Research, Vol. 31, No. 12, pp.1947–1964.
-Kara, I., Kara, B.Y. and Yetis, M. K. (2007) “Energy minimizing vehicle routing problem”,  In: A. Dress, Y. Xu, and B. Zhu (Eds.), Combinatorial Optimization and Applications, Lecture Notes in Computer Science, (4616, pp. 62–71). Berlin/Heidelberg: Springer.
-Kennedy, J. and Eberhart, R. C. (1995) "Particle swarm optimization", IEEE International Conference on Neural Networks, Perth, Australia, pp.1942–1948.
-Kuo, Y. (2010) “Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem”, Computers and Industrial Engineering, Vol. 59, No. 1, pp. 157–165.
-Laport, G., Mercure, H. and Nobert, Y. (1992) “A branch and bound algorithm for a class of asymmetrical vehicle routing problems”, Journal of Operational Research Society, Vol. 43, No. 5, pp. 469-481
-Lenstra, J. K. and Rinnooy Kan, A.H.G. (1981) "Complexity of vehicle and scheduling problem", Networks, Vol.11, No. 2, pp. 221-227.
-Maden, W., Eglese, R.W. and Black, D. (2010) “Vehicle routing and scheduling with time varying data: a case study”, Journal of the Operational Research Society, Vol. 61, No. 3, pp. 515–522.
-Norouzi, N., Sadegh-Amalnick, M. and Tavakkoli-Moghaddam, R. (2017) “Modified particle swarm optimization in a time-dependent vehicle routing problem: minimizing fuel consumption”, Optimization Letters, Vol. 11, No. 1, pp.121-134.
-Ohnishi, H. (2008) “Greenhouse gas reduction strategies in the transport sector: Preliminary Report”, Tech. Rep., OECD/ITF Joint Transport Research Centre Working Group on GHG Reduction Strategies in the Transport Sector, OECD/ITF, Paris. <http://www.internationaltransportforum.org/Pub/pdf/08GHG.pdf> (accessed 11.02.11).
-Palmer, A. (2007) “The development of an integrated routing and carbon dioxide emissions model for goods vehicles”, Ph.D. Dissertation, Cranfield University, School of Management.
Pham,  D. T., Ghanbarzadeh, A., Koc, E., Otri, S., Rahim, S. and Zaidi, M.  (2005) “The bees algorithm”, Technical Note, Manufacturing Engineering Centre, Cardiff University, UK.
-Pham, D.T., Ghanbarzadeh, A., Koc, E., Otri, S., Rahim, S. and Zaidi, M. (2006) “The bees algorithm - A novel tool for complex optimization problems”, Proceedings of IPROM, Conference, pp. 454-461.
-Poli, R., Kennedy, J. and Blackwell, T. (2007) “Particle swarm optimization, An overview”, Swarm Intelligence. Vol. 1, No. 1, pp. 33–57.
-Potvin, J. Y. and Bengio, S. (1994) "A genetic approach to the vehicle routing problem with time windows", publication CRT-953, Centre de Recherche sur les Transports, University of Montreal.
-Pradenas, L., Oportus, B. and Parada, V. (2013) “Mitigation of greenhouse gas emissions in vehicle routing problems with backhauling”, Expert Systems with Applications, Vol. 40, No. 8, pp.  2985–2991.
-Reimann, M., Stummer, M. and Doerner, K. (2002) "A savings based ant system for the vehicle routing problem", W.B. Langdon, et al. (Eds.) Kaufmann, M. (GECCO 2002) Proceedings of the Genetic and Evolutionary Computation Conference, San Francisco.
-Sahin, B., Yilmaz, H., Ust, Y., Guneri, A. F. and Gulsun, B. (2009) “An approach for analysing transportation costs and a case study”, European Journal of Operational Research, Vol. 193, No. 1, pp. 1–11.
-Ubeda S., Arcelus, F. J. and Faulin, J. (2011) “Green logistics at Eroski: A case study”, International Journal of Production Economics, Vol. 13, No. 1, pp. 44–51.
-Urquhart, N., Scott, C. and Hart, E. (2010) “Using an evolutionary algorithm to discover low CO tours within a travelling salesman problem”, Proceedings of the 2010 International Conference on Applications of Evolutionary Computation, pp. 421–430
-Xiao, Y., Zhao, Q., Kaku, I. and Xu, Y. (2012) “Development of a fuel consumption optimization model for the capacitated vehicle routing problem”, Computers and Operations Research, Vol. 39, No. 7, 1419–1431.