حل مسئله زمان‌بندی و مسیریابی سبز وسایل حمل‏ونقل با ناوگان ناهمگن شامل لجستیک معکوس به شکل جمع‌آوری کالاهای بازگشتی با الگوریتم ژنتیک

اعظمی, عادل; سعیدی مهرآباد, محمد

doi:10.22119/jte.2020.87203

حل مسئله زمان‌بندی و مسیریابی سبز وسایل حمل‏ونقل با ناوگان ناهمگن شامل لجستیک معکوس به شکل جمع‌آوری کالاهای بازگشتی با الگوریتم ژنتیک

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

نویسندگان

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

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

10.22119/jte.2020.87203

چکیده

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

کلیدواژه‌ها

20.1001.1.20086598.1399.11.4.8.8

موضوعات

مهندسی صنایع - مسیریابی

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

Solving green vehicle routing and scheduling problem with heterogeneous fleet including reverse logistics in the form of collecting returned goods using genetic algorithm

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

Adel Aazami ¹
Mohammad Saidi Mehrabad ²

¹ Ph D. Candidate, Department of Industrial Engineering, Iran University of Science and Technology, Tehran

² Professor, Department of Industrial Engineering, Iran University of Science and Technology, Tehran

چکیده [English]

Vehicle routing problem (VRP) is about finding optimal routes for a fleet of vehicles so that they can meet the demands for a set of given customers by traveling through those paths. This problem is one of the most important and most applicable problems of transportation and logistics scope. In this paper, green vehicle routing and scheduling problem with a heterogeneous fleet, including reverse logistics in the form of collecting returned goods along with weighted earliness and tardiness costs considering multiple time windows, is studied to establish a trade-off between operational and environmental costs. In this regard, a mixed-integer non-linear programming (MINLP) model is proposed at the first stage; then its accuracy and correct functioning are evaluated by solving some examples. Demand is considered uncertain based on fuzzy numbers that robust possibilistic programming is employed regarding the other parameters uncertainty. Since this problem is categorized as an NP-hard problem, a genetic algorithm (GA) is suggested to find near-optimal solutions for large instances in a rational computational time. Eventually, the GA’s performance is evaluated compared to solving the mathematical model for small-sized problems. Analysis of the results considering two criteria, solutions quality and computational times, indicates the satisfactory operation of the proposed algorithm in a proper computational time.

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

Genetic Algorithm
Green Vehicle Routing and Scheduling
Reverse Logistics
Heterogeneous Fleet
Robust Possibilistic Programming

مراجع

- بهشتی نیا، محمد علی، و اعرابی، آتنا (۱۳۹۶)" ارایه یک آلگوریتم ژنتیک برای مساله یکپارچگی مسیریابی وسایل نقلیه و زمان بندی تولید و زنجیره تامین. (مطالعه موردی : زنجیره تامین تجهیزات پزشکی)، نشریه مهندسی صنایع دانشکده فنی دانشگاه تهران، دوره ۵۱، شماره ۲، ص. ۱۴۷-۱۶۰

-بهشتی نیا، محمد علی، فیض، داوود و سدادی، فاطیما (۱۳۹۷) "یکپارچگی مساله مسیریابی وسایل نقلیه با زمان بندی حمل و نقل و تولید زنجیره تامین"، فصلنامه مهندسی حمل و نقل، جلد ۹، شماره ۴، ص. ۵۴۹-۵۷۰

-فرحبخش، فریبا، توکلی مقدم، رضا و قضاوتی، وحیدرضا (۱۳۹۶) "توسعه مدل ریاضی چند هدفه برای مساله مسیریابی وسایل نقلیه ناهمگن تحت شرایط بحران"، فصلنامه مهندسی حمل و نقل، دوره ۹، شماره ۲، ص. ۱۶۹-۱۸۷

-Alshamsi, A. and Diabat, A. (2017) "A Genetic Algorithm for Reverse Logistics network design: A case study from the GCC", Journal of Cleaner Production, Vol. 151, pp. 652–669.

-Beheshtinia, M. A., and Ghasemi, A. (2018) "A multi-objective and integrated model for supply chain scheduling optimization in a multi-site manufacturing system", Engineering Optimization, Vol. 50, No. 9, pp. 1415-1433.

-Beheshtinia, M. A., Ghasemi, A., and Farokhnia, M. (2018) "Supply chain scheduling and routing in multi-site manufacturing system (case study: a drug manufacturing company)", Journal of Modelling in Management, Vol. 13, No. 1, pp. 27-49.

-Bektaş, T. and Laporte, G. (2011) "The pollution-routing problem", Transportation Research Part B: Methodological, Vol. 45, No. 8, pp. 1232–1250.

-Bertsimas, D. and Sim, M. (2004) "The price of robustness", Operations research, Vol. 52, No. 1, pp. 35–53.

-Borumand, A., & Beheshtinia, M. A. (2018) "A developed genetic algorithm for solving the multi-objective supply chain scheduling problem", Kybernetes, Vol. 47, No. 7, pp. 1401-1419.

-Coelho, I. M., Munhoz, P. L. A., Ochi, L. S., et al. (2016) "An integrated CPU–GPU heuristic inspired on variable neighbourhood search for the single vehicle routing problem with deliveries and selective pickups", International Journal of Production Research, Vol. 54, No. 4, pp. 945–962.

-Daniel, S. E., Diakoulaki, D. C. and Pappis, C. P. (1997) "Operations research and environmental planning", European journal of operational research, Vol. 102, No. 2, pp. 248–263.

-Dantzig, G. B. and Ramser, J. H. (1959) "The truck dispatching problem", Management science, Vol. 6, No. 1, pp. 80–91.

-Dehghan, E., Nikabadi, M. S., Amiri, M. and Jabbarzadeh, A. (2018) "Hybrid robust, stochastic and possibilistic programming for closed-loop supply chain network design", Computers & Industrial Engineering, Vol. 123, pp. 220–231.

-Demir, E., Bektaş, T. and Laporte, G. (2012) "An adaptive large neighborhood search heuristic for the pollution-routing problem", European Journal of Operational Research, Vol. 223, No. 2, pp. 346–359.

-Demir, E., Bektaş, T. and Laporte, G. (2014b) "The bi-objective pollution-routing problem", European Journal of Operational Research, Vol. 232, No. 3, pp. 464–478.

-Erdoğan, S. and Miller-Hooks, E. (2012) "A green vehicle routing problem", Transportation Research Part E: Logistics and Transportation Review, Vol. 48, No. 1, pp. 100–114.

-Eydi, A. and Alavi, H. (2018) "Vehicle Routing Problem in Reverse Logistics with Split Demands of Customers and Fuel Consumption Optimization", Arabian Journal for Science and Engineering, pp. 1–11.

-Ferreira, H. S., Bogue, E. T., Noronha, T. F., et al. (2018) "Variable neighborhood search for vehicle routing problem with multiple time windows", Electronic Notes in Discrete Mathematics, Vol. 66, pp. 207–214.

-Figliozzi, M. (2010) "Vehicle routing problem for emissions minimization", Transportation Research Record: Journal of Transportation Research Board, Vol. 2197, pp. 1–7.

-Foroutan, R. A., Rezaeian, J., and Mahdavi, I. (2020) "Green vehicle routing and scheduling problem with heterogeneous fleet including reverse logistics in the form of collecting returned goods", Applied Soft Computing, Vol. 94, pp. 106462.

-Franceschetti, A., Honhon, D., Van Woensel, T., et al. (2013) "The time-dependent pollution-routing problem", Transportation Research Part B: Methodological, Vol. 56, pp. 265–293.

-Gaur, D. R., Mudgal, A. and Singh, R. R. (2013) "Routing vehicles to minimize fuel consumption", Operations Research Letters, Vol. 41, No. 6, pp. 576–580.

-Ghannadpour, S. F. and Zarrabi, A. (2019) "Multi-objective heterogeneous vehicle routing and scheduling problem with energy minimizing", Swarm and evolutionary computation, Vol. 44, pp. 728–747.

-Hoogeboom, M., Dullaert, W., Lai, D. and Vigo, D. (2020) "Efficient neighborhood evaluations for the vehicle routing problem with multiple time windows", Transportation Science, Vol. 54, No. 2, pp. 400–416.

-Kara, I., Kara, B. and Yetis, M. K. (2007) "Energy minimizing vehicle routing problem", Combinatorial optimization and applications, pp. 62–71.

-Khodabandeh, M., Hejazi, S. and Rasti-Barzoki, M. (2013) "A Genetic Algorithm for an Integrated Production and Distribution Scheduling Problem with VRP", Journal of Industrial Engineering Research in Production Systems, Vol. 1, No. 2, pp. 167-181 (In Persian).

-Koç, Ç., Bektaş, T., Jabali, O., et al. (2015) "A hybrid evolutionary algorithm for heterogeneous fleet vehicle routing problems with time windows", Computers & Operations Research, Vol. 64, pp. 11–27.

-Kwon, Y.-J., Choi, Y.-J. and Lee, D.-H. (2013) "Heterogeneous fixed fleet vehicle routing considering carbon emission", Transportation Research Part D: Transport and Environment, Vol. 23, pp. 81–89.

-Lenstra, J. K. and Kan, A. H. G. (1981) "Complexity of vehicle routing and scheduling problems", Networks, Vol. 11, No. 2, pp. 221–227.

-Li, J., Guo, H., Zhou, Q. and Yang, B. (2019) "Vehicle routing and scheduling optimization of ship steel distribution center under green shipbuilding mode", Sustainability, Vol. 11, No. 15, pp. 42–48.

-Li, J., Qin, H., Baldacci, R. and Zhu, W. (2020) "Branch-and-price-and-cut for the synchronized vehicle routing problem with split delivery, proportional service time and multiple time windows", Transportation Research Part E: Logistics and Transportation Review, Vol. 140, pp. 101955.

-Liao, T. W. (2020) "Integrated Outbound Vehicle Routing and Scheduling Problem at a Multi-Door Cross-Dock Terminal", IEEE Transactions on Intelligent Transportation Systems, pp. 1–14.

-Lin, C., Choy, K. L., Ho, G. T. S., et al. (2014) "Survey of green vehicle routing problem: past and future trends", Expert Systems with Applications, Vol. 41, No. 4, pp. 1118–1138.

-Malandraki, C. and Daskin, M. S. (1992) "Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms", Transportation science, Vol. 26, No. 3, pp. 185–200.

-Mirzapour Al-e-hashem, S. M. J. and Rekik, Y. (2014) "Multi-product multi-period Inventory Routing Problem with a transshipment option: A green approach", International Journal of Production Economics, Vol. 157, pp. 80–88.

-Niu, Y., Yang, Z., Chen, P., et al. (2018) "Optimizing the green open vehicle routing problem with time windows by minimizing comprehensive routing cost", Journal of Cleaner Production, Vol. 171, pp. 962–971.

-Norouzi, N., Tavakkoli-Moghaddam, R. (2017) "Minimizing Energy Consumption and Travel Time in a Vehicle Routing Problem with Time-Dependent Speeds Using an Imperialist Competitive Algorithm", Journal of Industrial Engineering Research in Production Systems, Vol. 4, No. 9, pp. 213-219 (In Persian).

-Pishvaee, M. S., Razmi, J. and Torabi, S. A. (2012) "Robust possibilistic programming for socially responsible supply chain network design: A new approach", Fuzzy sets and systems, Vol. 206, pp. 1–20.

-Rabbani, M., Bosjin, S., Yazdanparast, R., et al. (2018) "A stochastic time-dependent green capacitated vehicle routing and scheduling problem with time window, resiliency and reliability: a case study", Decision Science Letters, Vol. 7, No. 4, pp. 381–394.

-Rabbani, M., Hosseini-Mokhallesun, S. A. A., Ordibazar, A. H. and Farrokhi-Asl, H. (2020) "A hybrid robust possibilistic approach for a sustainable supply chain location-allocation network design", International Journal of Systems Science: Operations & Logistics, Vol. 7, No. 1, pp. 60–75.

-Salamat-Bakhsh, A., Tavakkoli-Moghaddam, R., Alinaghian, M. and Najafi, I. (2017) "Robust optimization approach in a competitive vehicle routing problem in an uncertain condition by using improved differential evolution", Quarterly Journal of Transportation Engineering, In Press (In Persian).

-Soysal, M. (2016) "Closed-loop Inventory Routing Problem for returnable transport items", Transportation Research Part D: Transport and Environment, Vol. 48, pp. 31–45.

-Statistics, I. E. A. (2015) "CO2 emissions from fuel combustion-highlights", IEA, Paris, www. iea. org/co2highlights/co2highlights. pdf. Cited July.

-Sun, J. U. (2007) "A taguchi approach to parameter setting in a genetic algorithm for general job shop scheduling problem", IEMS, Vol. 6, No. 2, pp. 119–124.

-Taguchi, G. (1986) "Introduction to quality engineering: designing quality into products and processes", The Asian Productivity Organization.

-Tang, Q. and Xie, F. (2007) "A genetic algorithm for reverse logistics network design", in Natural Computation, 2007. ICNC 2007. Third International Conference on. IEEE, pp. 277–281.

-Tasan, A. S. and Gen, M. (2012) "A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries", Computers & Industrial Engineering, Vol. 62, No. 3, pp. 755–761.

-The ministry of land, infrastructure, transport and tourism of Japan website, www.mlit.go.jp/common/000037099.pdf.

-Tirkolaee, E. B., Hosseinabadi, A. A. R., Soltani, M., et al. (2018) "A Hybrid Genetic Algorithm for Multi-Trip Green Capacitated Arc Routing Problem in the Scope of Urban Services.", Sustainability, Vol. 10, No. 5, pp. 1050-2071.

-Varun Kumar, S. G. and Panneerselvam, R. (2017) "A study of crossover operators for genetic algorithms to solve VRP and its variants and new sinusoidal motion crossover operator", Int. J. Comput. Intell. Res, Vol. 13, No. 7, pp. 1717–1733.

-Xiao, Y. and Konak, A. (2015) "A simulating annealing algorithm to solve the green vehicle routing & scheduling problem with hierarchical objectives and weighted tardiness", Applied Soft Computing, Vol. 34, pp. 372–388.

-Xiao, Y. and Konak, A. (2016) "The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion", Transportation Research Part E: Logistics and Transportation Review, Vol. 88, pp. 146–166.