Elektrikli araçların detaylı enerji tüketimini dikkate alan dinamik gezgin satıcı problemi
Dynamic travelling salesman problem considering explicit energy consumption of electric vehicles
Yazar: VOLKAN ÜNAL
Danışman: DOÇ. DR. MEHMET SOYSAL
Hacettepe Üniversitesi / Sosyal Bilimler Enstitüsü / İşletme Ana Bilim Dalı / Üretim Yönetimi Bilim Dalı
Derece: Doktora, 2023
Konu: İşletme = Business Administration
Dizin: Batarya = Battery ; Dinamik programlama = Dynamic programming ; Elektrikli araçlar = Electric vehicles ; Elektrikli otomobiller = Electric cars ; Enerji tüketimi = Energy consumption ; Gezgin satıcı problemi = Travelling salesman problem ; Lojistik = Logistics

Özet:
Elektrikli araçlar, konvansiyonel araçlara oranla çevreye daha az zarar verdiklerinden son yıllarda özellikle şehir içinde lojistik operasyonlarda sıklıkla kullanılmaya başlanmıştır. Hem araç teknolojilerindeki gelişim, hem de bilgi teknolojilerindeki ilerleme sayesinde araçlardan anlık olarak elde edilen veriler, araç rotalaması yapılırken daha verimli ve daha az maliyetli dağıtım planlarının oluşumuna temel oluşturmuştur. Bu çalışmada ilk olarak seyahat esnasında araç hızlarının dinamik olarak değişebildiği varsayımıyla ele alınan deterministik batarya tüketimi altında dinamik Gezgin Satıcı Problemi için dinamik programlama tabanlı ve bağlantı eleme yöntemine dayalı bir algoritma geliştirilmiştir. Büyük ölçekli problemlerin çözümü için önerilen algoritma 90 problem üzerinde uygulanmış ve bu problemlerin 51 tanesinde önerilen algoritmanın Kısıtlı Dinamik Programlama algoritmasından daha iyi sonuçlar ürettiği gözlenmiştir. Çalışma kapsamında ele alınan trafik yoğunluğunun belirsizliği nedeniyle batarya tüketim hızının kesin olarak bilinmemesi probleminde, belirsiz batarya tüketimi altında dinamik Gezgin Satıcı Problemi için dinamik programlama tabanlı ve Prim algoritması destekli sezgisel bir algoritma önerilmiştir. Önerilen yaklaşım ile trafik yoğunluğunun ve ihtiyaç duyulan batarya miktarının önceden kesin olarak bilinmediği, her ikisinin taşıma süreci içinde değişiklik gösterdiği durumlarda şehir içi trafik yoğunluğunun, CO2 salınımlarının ve elektrikli araç sürücülerinin menzil kaygılarının (range anxiety) azaltılmasına katkı sağlayacak taşıma planlarının elde edilmesi amaçlanmıştır. Büyük ölçekli 270 problem üzerinde yapılan analizler, önerilen algoritmanın Kısıtlı Dinamik Programlama algoritmasına göre, toplam enerji tüketimi açısından ortalama %6,87 daha iyi performans gösterdiğini ortaya koymaktadır. Detaylı enerji tüketimini dikkate alan her iki karar destek modeli de kısa mesafeli yük taşımacılığında karşılaşılan büyük ölçekli rotalama problemleri için dağıtım planlarının oluşturulmasında kullanılabilir.

Abstract:
In recent years, electric vehicles have started to be used frequently in logistics operations, especially in cities, since they cause less damage to the environment compared to conventional vehicles. Instantaneous data from vehicles obtained with the help of the development in vehicle technologies and the progress in information technologies enable to have more efficient and less costly distribution routes. In  this study, first, the dynamic travelling salesman problem, which is taken into account with the assumption that vehicle speeds can change dynamically during travel, is addressed. An algorithm based on dynamic programming and the link elimination method have been developed for the problem under the conditions of deterministic battery consumption. The proposed approach has been applied to 90 problems. In 51 of those problems, it has been found to perform better than the Restricted Dynamic Programming Algorithm. The other problem covered by the study is the dynamic travelling salesman problem with uncertain battery consumption, where the battery consumption rate is not precisely known due to the uncertainty of the traffic density. A dynamic programming-based and Prim's algorithm supported heuristic algorithm have been proposed for the problem. With the proposed approach, the purpose is to obtain transportation plans that will aid in lowering urban traffic density, emissions, and range anxiety among electric vehicle drivers in circumstances where traffic density and required battery capacity are both uncertain in advance and change throughout the transportation process. It has been found out that the proposed algorithm outperformed the Restricted Dynamic Programming algorithm in terms of total energy consumption by an average of 6.87%, based on an analysis of 270 large-scale problems. For large-scale routing problems that arise in short-haul freight transportation, distribution plans can be made using either of the decision support models that account for precise energy use.