Solving the multi-trip vehicle routing problem with time windows in urban waste management using grey wolf optimization algorithm

Document Type : Industry Article

Authors

1 Department of Industrial Engineering, Mazandaran University of Science & Technology, Babol, Iran

2 Department of Industrial Engineering, Mazandaran University of Science and Technology

3 Department of Industrial Engineering, Amirkabir University of Technology

Abstract

One of the most important issues of concern to human societies in recent years is urban waste management that is one of the main requirements of each city, and without any notice of it, it can be problematic for it and even residents of the surrounding villages. Urban areas generate the highest amount of waste and consequently, they need an efficient system for collecting and disposing of waste where its determination and stabilization is very difficult and costly. In this regard, this paper examines the multi-trip vehicle routing problem with time windows specific to the urban waste collection, with the goal is to minimize the total cost including routing costs, the earliness and lateness penalty cost for violating the service time windows and the usage costs of vehicles. To solve the problem in practical dimensions, grey wolf optimization (GWO) algorithm is developed where its performance is tested compared to CPLEX solver of GAMS and simulated annealing (SA) algorithm. The obtained results demonstrate that the proposed GWO have an acceptable performance to generate high-quality solutions. Finally, to study the behavior of the objective function versus the real-world demand parameter changes, a sensitivity analysis is performed on this parameter and the optimal management policy is analyzed.ed.

Keywords

Main Subjects

References

[1] علینقیان، مهدی، صباغ، محمدسعید، بابایی تیرکلایی، عرفان، "مسأله مسیریابی کمان ظرفیتدار با تقاضای فازی به همراه مطالعه موردی"، فصلنامه علمی - پژوهشی مهندسی حمل و نقل، دوره 7، شماره 2، زمستان 1394، صفحه 277-296.
[2] Dantzig, G. B., and Ramser, J. H, “The truck dispatching problem”, Management science, Vol. 6, No. 1, 1959, pp. 80-91.‏
[3] De Bruecker, P., Beliën, J., De Boeck, L., De Jaeger, S., and Demeulemeester, E, “A model enhancement approach for optimizing the integrated shift scheduling and vehicle routing problem in waste collection”, European Journal of Operational Research, Vol. 22, No. 1, 2018, pp. 278-290.‏
[4] Tirkolaee, E. B., Goli, A., Bakhsi, M., and Mahdavi, I, “A robust multi-trip vehicle routing problem of perishable products with intermediate depots and time windows”, Numerical Algebra, Control and Optimization, Vol. 7, No. 4, 2017, pp. 417-433.‏
[5] Dong, W., Zhou, K., Qi, H., He, C., and Zhang, J, “A tissue P system based evolutionary algorithm for multi-objective VRPTW”, Swarm and evolutionary computation, Vol. 39, 2018, pp. 310-322.
[6] Beltrami, E. and Bodin, L. D, “Networks and Vehicle Routing for Municipal Waste Collection”, Networks, Vol. 4, No. 1, 1974, pp. 65-94.
[7] Clarke, G., and Wright, J. W, “Scheduling of vehicles from a central depot to a number of delivery points. Operations research”, Vol. 12, No. 4, 1964, pp. 568-581.
[8] Tung, D. V., and Pinnoi, A, “Vehicle routing–scheduling for waste collection in Hanoi”, European Journal of Operational Research, Vol. 125, No. 3, 2000, pp. 449-468.
[9] Solomon, M. M, “Algorithms for the vehicle routing and scheduling problems with time window constraints”, Operations research, Vol. 35, No. 2, 1987, pp. 254-265.
[10] Poot, A., Kant, G., and Wagelmans, A. P. M, “A savings based method for real-life vehicle routing problems”, Journal of the Operational Research Society, Vol. 53, No. 1, 2002, pp. 57-68.
[11] Aringhieri, R., Bruglieri, M., Malucelli, F., and Nonato, M, “An asymmetric vehicle routing problem arising in the collection and disposal of special waste”, Electronic notes in discrete mathematics, Vol. 17, 2004, pp. 41-47.
[12] Kim, B. I., Kim, S., and Sahoo, S, “Waste collection vehicle routing problem with time windows”, Computers and Operations Research, Vol. 33, No. 12, 2006, pp. 3624-3642.
[13] Dotoli, M., and Epicoco, N, “A Vehicle Routing Technique for Hazardous Waste Collection”, IFAC-PapersOnLine, Vol. 50, No. 1, 2017, pp. 9694-9699.
[14] Inghels, D., Dullaert, W., and Vigo, D, “A service network design model for multimodal municipal solid waste transport”, European Journal of Operational Research, Vol. 254, No. 1, 2016, pp. 68-79.‏
[15] Babaee Tirkolaee, E., Alinaghian, M., Bakhshi Sasi, and Seyyed Esfahani, M. M, “Solving a robust capacitated arc routing problem using a hybrid simulated annealing algorithm: A waste collection application”, Journal of Industrial Engineering and Management Studies, Vol. 3, No. 1, 2016, pp. 61-76.
[16] Erfani, S. M. H., Danesh, S., Karrabi, S. M., and Shad, R, “A novel approach to find and optimize bin locations and collection routes using a geographic information system”, Waste Management and Research, Vol. 35, No. 7, 2017, pp. 776-785.
[17] Tirkolaee, E. B., Mahdavi, I., & Esfahani, M. M. S., “A robust periodic capacitated arc routing problem for urban waste collection considering drivers and crew’s working time”, Waste Management, Vol. 76, 2018, pp. 138-146.
[18] مهدوی ایرج، توکلی مقدم، رضا و قاضی زاده هاشمی، سید مصطفی، "مسیریابی وسایل نقلیه و تعیین تعداد ماشین های جمع آوری زباله با استفاده از یک روش فرا ابتکاری- یک مطالعه ی موردی"، پژوهشنامه حمل و نقل، دوره 7، شماره 1، بهار 1389، صفحه 95-101.
[19] شاهبندرزاده، حمید، نجمی، محمد حسن، عطایی، علیرضا، "ارائۀ مدل ریاضی بر اساس مسئلۀ مسیریابی خودرو ظرفیت‎دار با پنجره‌های زمانی برای جمع‎آوری زباله"، نشریه مدیریت صنعتی، دوره 9، شماره 1، بهار 1396، صفحه 147-166.
[20] اسدی گنگرج، ابراهیم، بزرگ نژاد، فاطمه، پایدار، محمد مهدی، "توسعه روش های فراابتکاری برای حل مسئله زمانبندی نیروی انسانی در محیط جریان کارگاهی"، مدل سازی در مهندسی, دوره 16، شماره 54، پاییز 1397، صفحه 20-20.
[21] رستمی، عباس، نوروزی، امیر، مختاری، هادی، نعمتی، یاسر، "مساله بهینه سازی پورتفولیوی چندهدفه با اهداف حداکثر کردن بازده، حداقل کردن ریسک و حداقل کردن تعداد دارایی"، مدل سازی در مهندسی، دوره 14، شماره 45، تابستان 1395، صفحه 99-109.
[22] حکیم پور، فرشاد، طلعت اهری، سیامک، رنجبر، ابوالفضل، "ارزیابی و مقایسه الگوریتم های بهینه سازی ژنتیک، شبیه سازی تبرید و فاخته ها در مکان یابی رقابتی تسهیلات (مطالعه موردی: بانکها)"، مدل سازی در مهندسی, دوره 15، شماره 48، بهار 1396، صفحه 231-246.
[23] Song, X., Tang, L., Zhao, S., Zhang, X., Li, L., Huang, J., & Cai, W., “Grey Wolf Optimizer for parameter estimation in surface waves”, Soil Dynamics and Earthquake Engineering, Vol. 75, 2015, pp. 147-157.
[24] Madadi, A., & Motlagh, M. M., “Optimal control of DC motor using grey wolf optimizer algorithm”, Technical Journal of Engineering and Applied Science, Vol, 4, No. 4, 2014, pp. 373-379.
[25] Faris, H., Aljarah, I., Al-Betar, M. A., & Mirjalili, S., “Grey wolf optimizer: a review of recent variants and applications”, Neural computing and applications, 2018, pp. 1-23.
[26] Rathee, P., Garg, R., & Meena, S., “Using grey wolf optimizer for image registration”, International Journal of Advance Research in Science and Engineering, Vol. 4, No. 4, 2015, pp. 360-364.
[27] Gupta, P., Kumar, V., Rana, K. P. S., & Mishra, P., “Comparative study of some optimization techniques applied to Jacketed CSTR control”, 4th International Conference on Reliability, Infocom Technologies and Optimization (ICRITO) (Trends and Future Directions), 2015, pp. 1-6.
[28] Kubotani, H., & Yoshimura, K., “Performance evaluation of acceptance probability functions for multi-objective SA”, Computers & Operations Research, Vol. 30, No. 3, 2003, pp. 427-442.S
[29] Mirjalili, S., Mirjalili, S. M., and Lewis, A, “Grey wolf optimizer”, Advances in engineering software, Vol. 69, 2014, pp. 46-61.
[30] Medjahed, S. A., Saadi, T. A., Benyettou, A., and Ouali, M, “Grey Wolf Optimizer for hyperspectral band selection”, Applied Soft Computing, Vol. 40, 2016, pp. 178-186.
[31] Glover, F. W., and Kochenberger, G. A., eds., “Handbook of metaheuristics”. Springer Science and Business Media, Vol. 57, 2006.
[32] Shannon, C. E. (1948). “A mathematical theory of communication”. Bell system technical journal, Vol. 27, No. 3, pp. 379-423.
Journal of Modeling in Engineering
Volume 17, Issue 57
July 2019
Pages 93-110

Files

History

  • Receive Date: 09 November 2018
  • Revise Date: 10 February 2019
  • Accept Date: 02 March 2019

Share

How to cite

Statistics