Elektrikli Araçla Periyodik Teknisyen Rotalama ve İstasyon Yeri Seçim Problemi

Öz

Bu çalışmada Elektrikli Araçla Periyodik Teknisyen Rotalama ve Şarj İstasyonu Yeri Belirleme Problemi tanımlanmıştır. Problemde farklı coğrafi bölgelerde bulunan müşterilere bir dizi önleyici ve düzeltici bakım ve yedek parça tedariki hizmetleri sunulmaktadır. Ayrıca müşteriler, planlama ufku boyunca farklı zaman dilimlerinde bu ve benzeri hizmetleri talep edebilmektedir. Farklı yetkinliklere sahip olan teknisyenlerden takımlar oluşturulup müşterilerin bulunduğu ortamda talep edilen hizmetler sağlanmaktadır. Hali hazırda iş gücü çizelgeleme ve rotalama probleminin NP-zor sınıfta yer aldığı göz önüne alınırsa, tanımlanan problemde aynı sınıfta yer almaktadır. Literatürden farklı olarak bu çalışmada, teknisyenlerin müşterilere ulaşmada klasik içten yanmalı motorlu araçlar kullanması yerine elektrikli araçlarla müşterilere ulaşması göz önüne alınmıştır. Bu sayede fosil yakıt kullanımı azaltılarak, bu yakıtların ulaşım kaynaklı çevresel etkilerinin azaltılması gerçekleşebilecektir. Ayrıca, çevre dostu elektrikli araçların işletme maliyetlerinin klasik içten yanmalı motorlu araçlara göre daha az olması da işletmelerin karşısına ekonomik bir alternatif olarak ortaya çıkmaktadır. Elektrikli araçların avantajlarının yanı sıra kısıtlı menzili onları istasyon kullanmaya bağımlı kılmaktadır. Bu sebepten ötürü bu araçların fosil yakıt kullanan araçlarla rekabet edebilmesi için rotalama planlarının da etkin bir şekilde yapılması gerekmektedir. Tanımlanan problemde planlama ufku boyunca takımlar için günlük çizelge ve rota oluşturmanın yanı sıra, elektrikli araçların şarj durumunun takibi ve istasyon yeri belirleme kararı da bulunmaktadır. Ayrıca teknisyenlerin yasal dinlenme süreleri de göz önüne alınmıştır. Belirli çalışma süresini tamamlayan teknisyenlerin mola vererek dinlenmesi sağlanmıştır. Önerilen karma tam sayılı programlama ile problem modellenmiştir. Gerçek hayat verisinden üretilen veri seti kesin yöntemle çözülmüştür. Ayrıca üretilen farklı boyutlardaki problemlerin çözümü için değişken komşu arama sezgiseli kullanılmıştır. Elde edilen kesin sonuçlar değişken komşu arama sezgiseli ile karşılaştırılmıştır. Gerçekleştirilen hesaplamalı karşılaştırma analizleri sezgisel yöntemin optimum çözümü bulabildiğini ve CPLEX çözücüsünden daha iyi sonuçlar ürettiğini ortaya koymaktadır.

Anahtar Kelimeler

• Elektrikli Araçlar
• Periyodik Teknisyen Rotalama
• Şarj İstasyonu Yeri Belirleme
• Değişken Komşu Arama

Electric Multiperiod Technician Routing and Charging Station Location Problem

Abstract

In this study, Electric Multiperiodic Technician Routing and Charging Station Location Problem is defined. A series of preventive and corrective maintenance-repair and spare parts supply services are offered to customers located in different geographical regions of the problem. In addition, the customers can request these tasks in different time windows throughout the planning horizon. Teams of technicians with different competencies are formed and allocated to these tasks that are provided in the customer locations. Considering that the workforce scheduling and routing problem is in the NP-hard class, thus the defined problem is also in the same class. Unlike the literature, in this study, it is taken into account that technicians reach customers with electric vehicles instead of using conventional internal combustion engine vehicles. In this way, it will be possible to reduce the use of fossil fuels and the environmental impact of these fuels due to transportation. In addition, due to the operating costs of electric vehicles are lower than those of conventional vehicles, electric vehicles emerge as an economical option for businesses. In addition to their advantages, the limited range of electric vehicles makes them dependent on using charging stations. For this reason, routing plans need to be made efficiently in order for these vehicles to compete with conventional vehicles. In the proposed problem, while creating a daily schedule and route for the teams throughout the planning horizon, tracking the state of charge of the vehicles and determining the location of the charging station are also considered. In addition, the legal rest periods of the technicians are also taken into account. The problem is modelled with the mixed integer programming formulation. Furthermore, the data set generated from the real-life instances. In order to solve the problem variable neighbourhood search heuristic is used. Computational comparisons are conducted to compare the performance of the heuristic. The results indicate that it can find the optimum solutions. Moreover, the heuristic is able to produces better results than the CPLEX solver in a reasonable time.

Keywords

• Electric Vehicles
• Technician Routing
• Charging Station Location Problem
• Variable Neighbourhood Search

Kaynakça

1. Castillo-Salazar, J. A., Landa-Silva, D., ve Qu, R. (2014). Workforce scheduling and routing problems: literature survey and computational study. Annals of Operations Research, 1-29. doi:10.1007/s10479-014-1687-2
2. Cordeau, J.-F., Laporte, G., Pasin, F., ve Ropke, S. (2010). Scheduling technicians and tasks in a telecommunications company. Journal of Scheduling, 13(4), 393-409. doi:10.1007/s10951-010-0188-7
3. Dohn, A., Kolind, E., ve Clausen, J. (2009). The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach. Computers & Operations Research, 36(4), 1145-1157. doi:http://dx.doi.org/10.1016/j.cor.2007.12.011
4. Edelstein, S. (2017). 2017 electric cars with more than 100 miles of range (updated). Retrieved from https://www.greencarreports.com/news/1107455_2017-electric-cars-with-more-than-100-miles-of-range
5. Ernst, A. T., Jiang, H., Krishnamoorthy, M., ve Sier, D. (2004). Staff scheduling and rostering: A review of applications, methods and models. European Journal of Operational Research, 153(1), 3-27. doi:http://dx.doi.org/10.1016/S0377-2217(03)00095-X
6. European-Commission. (2011). WHITE PAPER Roadmap to a Single European Transport Area – Towards a competitive and resource efficient transport system. In.
7. European-Commission. (2014). WHITE PAPER Roadmap to a Single European Transport Area – Towards a competitive and resource efficient transport system. Retrieved from http://eur-lex.europa.eu/legal-content/en/ALL/?uri=celex%3A52011DC0144
8. European Comission (2014). Report from the comission to the European parliament and the council –Progress towards achieving the Kyoto and EU2020 objecitves. Retrieved from

9. European Environment Agency. (2014). Annual European union greenhouse gas inventory 1990–2012 and inventory report 2014. (Technical report No 09/2014 ). European Environment Agency
10. Google. (2020). The Google Maps Distance Matrix API. Retrieved from https://developers.google.com/maps/documentation/distance-matrix/intro
11. Hansen, P., Mladenović, N., Brimberg, J., ve Pérez, J. A. M. (2010). Variable Neighborhood Search. In M. Gendreau ve J.-Y. Potvin (Eds.), Handbook of Metaheuristics (pp. 61-86). Boston, MA: Springer US.
12. Kovacs, A. A., Parragh, S. N., Doerner, K. F., ve Hartl, R. F. (2012). Adaptive large neighborhood search for service technician routing and scheduling problems. Journal of Scheduling, 15(5), 579-600. doi:10.1007/s10951-011-0246-9
13. Schiffer, M., ve Walther, G. (2017). The electric location routing problem with time windows and partial recharging. European Journal of Operational Research, 260(3), 995-1013. doi:https://doi.org/10.1016/j.ejor.2017.01.011
14. Schmidt, E. (2017). Battery Electric Cars Reported Range Comparison. Retrieved from https://www.fleetcarma.com/2017-battery-electric-cars-reported-range-comparison/
15. Xu, J., ve Chiu, S. Y. (2001). Effective Heuristic Procedures for a Field Technician Scheduling Problem. Journal of Heuristics, 7(5), 495-509. doi:10.1023/A:1011377929184
16. Zamorano, E., ve Stolletz, R. (2017). Branch-and-price approaches for the Multiperiod Technician Routing and Scheduling Problem. European Journal of Operational Research, 257(1), 55-68. doi:https://doi.org/10.1016/j.ejor.2016.06.058