Sürdürülebilir işgücü çizelgeleme ve rotalama probleminin değişken komşu arama algoritmasıyla çözümü: Samsun örneği

Öz

Bu çalışmada sürdürülebilir işgücü çizelgeleme ve rotalama problemi (S-İÇRP) ele alınmıştır. Problemde farklı yetkinlik seviyesine sahip çalışanlardan takımlar oluşturularak farklı ilçelerde bulunan müşterilere önceden belirlenmiş zaman dilimi içerisinde hizmet verilmektedir. Problem için tam sayılı doğrusal programlama modeli geliştirilmiş olup model araç rotalama, işgücü çizelgeleme, araç şarj durumu takibi ve şarj istasyonu ziyareti gibi kararlar da gözetilmiştir. Ayrıca farklı amaç fonksiyonları göz önüne alınarak toplam mesafenin yanı sıra, araç maliyeti de dikkate alınmıştır. Yapılan deneysel çalışmalar bize elektrikli araçların bakım hizmeti sağlayan firmalarda günlük kullanılabilirliğini göstermiştir. Ayrıca geliştirilen değişken komşu arama (DKA) algoritmasının performansı kesin çözüm yöntemiyle karşılaştırılmış ve sonuçlar önerilen yöntemin iyi çözüm bulmadaki etkinliğini göstermiştir.

Anahtar Kelimeler

• Elektrikli Araçlar
• İşgücü Çizelgeleme
• Matematiksel programlama.

The Sustainable workforce scheduling and routing problem with variable neighbourhood search algorithm: The case of Samsun

Abstract

This paper addresses sustainable workforce scheduling and routing problem (WSRP), in which technicians with different levels of competence are paired into teams to serve customers in different geographic regions-districts within predetermined time windows. We formulate the WSRP as a mixed integer linear programming formulation that covers the decisions such as scheduling, routing, state of charge, and visiting of the charging stations. Furthermore, we developed different objective functions minimizing not only total travelled distance, but also the number of electrical vehicles employed. The performance of the proposed heuristic is tested by using real-world data. In addition, the developed variable neighbourhood search algorithm is compared with the exact solution method and the computational results indicates that the proposed heuristic can yield high quality of solutions.

Keywords

• Electric vehicles
• Workforce scheduling
• Mathematical programming.

Kaynakça

1. O. Kherbash ve M. L. Mocan, "A Review of Logistics and Transport Sector as a Factor of Globalization," Procedia Economics and Finance, vol. 27, pp. 42-47, 2015/01/01/ 2015, doi: https://doi.org/10.1016/S2212-5671(15)00969-7.
2. T. Haasz vd., "Perspectives on decarbonizing the transport sector in the EU-28," Energy Strategy Reviews, vol. 20, pp. 124-132, 2018/04/01/ 2018, https://doi.org/10.1016/j.esr.2017.12.007.
3. R. Engström, "The Roads’ Role in the Freight Transport System," Transportation Research Procedia, vol. 14, pp. 1443-1452, 2016/01/01/ 2016, https://doi.org/10.1016/ j.trpro.2016.05.217.
4. EU-SCIENCE-HUB. "Transport sector economic analysis." https://ec.europa.eu/jrc/en/research-topic/ transport-sector-economic-analysis (accessed 01.04.2020.
5. (2014). Technical report No 09/2014 Annual European union greenhouse gas inventory 1990–2012 and inventory report 2014.
6. European Comission "Report from the comission to the European parliament and the council –Progress towards achieving the Kyoto and EU2020 objecitves.," European Comission., 2014.
7. European-Commission, "WHITE PAPER Roadmap to a Single European Transport Area – Towards a competitive and resource efficient transport system," ed, 2011.
8. M. Schiffer ve G. Walther, "The electric location routing problem with time windows and partial recharging," European Journal of Operational Research, vol. 260, no. 3, pp. 995-1013, 8/1/ 2017, https://doi.org/10.1016/j.ejor.2017.01.011.

9. G. Suizo. "Large & recharged: Top electric vehicles." https://www.greenfleetmagazine.com/ 155563/large-recharged-top-electric-fleets (Accessed 01.05.2020).
10. A. T. Ernst, H. Jiang, M. Krishnamoorthy, B. Owens, ve D. Sier, "An Annotated Bibliography of Personnel Scheduling and Rostering," (in English), Ann Oper Res, vol. 127, no. 1-4, pp. 21-144, 2004/03/01 2004, doi: 10.1023/B:ANOR.0000019087.46656.e2.
11. A. T. Ernst, H. Jiang, M. Krishnamoorthy, ve D. Sier, "Staff scheduling and rostering: A review of applications, methods and models," European Journal of Operational Research, vol. 153, no. 1, pp. 3-27, 2004/02/16/ 2004, https://doi.org/10.1016/S0377-2217(03)00095-X.
12. J. Van den Bergh, J. Beliën, P. De Bruecker, E. Demeulemeester, ve L. De Boeck, "Personnel scheduling: A literature review," European Journal of Operational Research, vol. 226, no. 3, pp. 367-385, 5/1/ 2013, http://dx.doi.org/10.1016/j.ejor. 2012.11.029.
13. J. A. Castillo-Salazar, D. Landa-Silva, ve R. Qu, "Workforce scheduling and routing problems: literature survey and computational study," (in English), Ann Oper Res, pp. 1-29, 2014/08/14 2014, doi: 10.1007/s10479-014-1687-2.
14. J.-F. Cordeau, G. Laporte, F. Pasin, ve S. Ropke, "Scheduling technicians and tasks in a telecommunications company," Journal of Scheduling, vol. 13, no. 4, pp. 393-409, 2010/08/01 2010, doi: 10.1007/s10951-010-0188-7.
15. A. A. Kovacs, S. N. Parragh, K. F. Doerner, ve R. F. Hartl, "Adaptive large neighborhood search for service technician routing and scheduling problems," Journal of Scheduling, vol. 15, no. 5, pp. 579-600, 2012/10/01 2012, doi: 10.1007/s10951-011-0246-9.
16. A. Lim, B. Rodrigues, ve L. Song, "Manpower allocation with time windows," Journal of the Operational Research Society, vol. 55, no. 11, pp. 1178-1186, 2004/11/01 2004, doi: 10.1057/palgrave.jors.2601782.
17. Y. Li, A. Lim, ve B. Rodrigues, "Manpower allocation with time windows and job-teaming constraints," Naval Research Logistics (NRL), vol. 52, no. 4, pp. 302-311, 2005, doi: 10.1002/nav.20075.
18. A. Dohn, E. Kolind, ve J. Clausen, "The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach," Computers & Operations Research, vol. 36, no. 4, pp. 1145-1157, 2009/04/01/ 2009, https://doi.org/10.1016/ j.cor.2007.12.011.
19. J. Xu ve S. Y. Chiu, "Effective Heuristic Procedures for a Field Technician Scheduling Problem," Journal of Heuristics, vol. 7, no. 5, pp. 495-509, 2001/09/01 2001, doi: 10.1023/A:1011377929184.
20. V. Pillac, C. Guéret, ve A. L. Medaglia, "A parallel matheuristic for the technician routing and scheduling problem," Optimization Letters, vol. 7, no. 7, pp. 1525-1535, 2013/10/01 2013, doi: 10.1007/s11590-012-0567-4.
21. E. Zamorano ve R. Stolletz, "Branch-and-price approaches for the Multiperiod Technician Routing and Scheduling Problem," European Journal of Operational Research, vol. 257, no. 1, pp. 55-68, 2017/02/16/ 2017, doi: https://doi.org/10.1016/ j.ejor.2016.06.058.
22. M. Erdem, "Elektrikli Araçla Periyodik Teknisyen Rotalama ve İstasyon Yeri Seçim Problemi," Avrupa Bilim ve Teknoloji Dergisi , Ejosat, no. Special issue, pp. 16-27, 2020, doi: 10.31590/ejosat.818352.
23. S. Erdoğan ve E. Miller-Hooks, "A Green Vehicle Routing Problem," Transportation Research Part E: Logistics and Transportation Review, vol. 48, no. 1, pp. 100-114, 1// 2012, https://doi.org/10.1016/j.tre. 2011.08.001.
24. M. Schneider, A. Stenger, ve D. Goeke, "The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations," Transportation Science, vol. 48, no. 4, pp. 500-520, 2014, doi: 10.1287/trsc.2013.0490.
25. R. G. Conrad ve M. A. Figliozzi, "The Recharging Vehicle Routing Problem," in Industrial Engineering Research Conference, T. Doolen and E. V. Aken, Eds., 2011.
26. J. Hof, M. Schneider, ve D. Goeke, "Solving the battery swap station location-routing problem with capacitated electric vehicles using an AVNS algorithm for vehicle-routing problems with intermediate stops," Transportation Research Part B: Methodological, vol. 97, pp. 102-112, 2017/03/01/ 2017, https://doi.org/ 10.1016/j.trb.2016.11.009.
27. D. Goeke ve M. Schneider, "Routing a mixed fleet of electric and conventional vehicles," European Journal of Operational Research, vol. 245, no. 1, pp. 81-99, 2015/08/16/ 2015, http://dx.doi.org/10.1016/ j.ejor.2015.01.049.
28. G. Desaulniers, F. Errico, S. Irnich, ve M. Schneider, "Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows," Operations Research, vol. 64, no. 6, pp. 1388-1405, 2016, doi: 10.1287/opre.2016.1535.
29. G. Hiermann, J. Puchinger, S. Ropke, ve R. F. Hartl, "The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations," European Journal of Operational Research, vol. 252, no. 3, pp. 995-1018, 2016/08/01/ 2016, http://dx.doi.org/10.1016/j.ejor.2016.01.038.
30. Á. Felipe, M. T. Ortuño, G. Righini, ve G. Tirado, "A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges," Transportation Research Part E: Logistics and Transportation Review, vol. 71, pp. 111-128, 2014/11/01/ 2014, http://dx.doi.org/10.1016/ j.tre.2014.09.003.
31. M. Keskin ve B. Çatay, "Partial recharge strategies for the electric vehicle routing problem with time windows," Transportation Research Part C: Emerging Technologies, vol. 65, pp. 111-127, 4// 2016, https://doi.org/10.1016/j.trc.2016.01.013.
32. M. Erdem ve Ç. Koç, "Analysis of electric vehicles in home health care routing problem," Journal of Cleaner Production, vol. 234, pp. 1471-1483, 2019/10/10/ 2019, https://doi.org/10.1016/j.jclepro. 2019.06.236.
33. S. Pelletier, O. Jabali, ve G. Laporte, "50th Anniversary invited article-Goods distribution with electric vehicles: review and research perspectives," Transportation Science, vol. 50 (1), pp. 3–22, 2016.
34. S. Pelletier, O. Jabali, G. Laporte, ve M. Veneroni, "Battery degradation and behaviour for electric vehicles: Review and numerical analyses of several models," Transportation Research Part B: Methodological, vol. 103, pp. 158-187, 2017/09/01/ 2017, https://doi.org/10.1016/ j.trb.2017.01.020.
35. M. Schiffer, M. Schneider, ve G. Laporte, "Designing sustainable mid-haul logistics networks with intra-route multi-resource facilities," European Journal of Operational Research, vol. 265, no. 2, pp. 517-532, 2018/03/01/ 2018, https://doi.org/10.1016/j.ejor. 2017.07.067.
36. N. Mladenović ve P. Hansen, "Variable neighborhood search," Computers & Operations Research, vol. 24, no. 11, pp. 1097-1100, 1997/11/01/ 1997, http://dx.doi.org/10.1016/S0305-0548(97)00031-2.
37. P. Hansen, N. Mladenović, J. Brimberg, ve J. A. M. Pérez, "Variable Neighborhood Search," in Handbook of Metaheuristics, M. Gendreau and J.-Y. Potvin Eds. Boston, MA: Springer US, 2010, pp. 61-86.
38. P. Hansen ve N. Mladenović, "Variable neighborhood search: Principles and applications," European Journal of Operational Research, vol. 130, no. 3, pp. 449-467, 5/1/ 2001, http://dx.doi.org/10.1016/S0377-2217(00)00100-4.
39. Google. "The Google Maps Distance Matrix API." https://developers.google.com/maps/documentation/distance-matrix/intro (Accessed 01.05.2020).
40. S. Edelstein. "2017 electric cars with more than 100 miles of range (updated)." Green car reports. https://www.greencarreports.com/news/1107455_2017-electric-cars-with-more-than-100-miles-of-range (Accessed 01.01.2018).
41. E. Schmidt. "Battery Electric Cars Reported Range Comparison." https://www.fleetcarma.com/2017-battery-electric-cars-reported-range-comparison/ (Accessed 01.05.2020).
42. Ramos, J., Padrón, S., Guillén, L., Piera, M., Guimarans, D., ve Herrero, R. Intelligent platform for sustainable routing, 2010, https://www.researchgate.net/publication/236455075_Intelligent_platform_for_sustainable_routing (Accessed 01.12.2021).