Değişken komşuluk arama algoritmaları ile elektrikli araç rotalama problemlerinin çözümü

Abstract

Dünya, Paris Anlaşması'nı uygulayarak iklim değişikliğinin etkilerini sınırlamayı kabul etmiştir. Bu da dünya ekonomisinin en yoğun karbon-yoğun sektörlerinden biri olan ulaştırma sektöründe temel ve köklü değişiklikleri gerektirmektedir. Sektörde açık ara baskın enerji kaynağı petrol olduğu için, kullanılan araçların elektrifikasyonu dekarbonizasyon açısından önemli bir rol oynayacaktır. Böylece sera gazı emisyonuna ek olarak hava ve gürültü kirliliği de azaltılarak, bu kapsamdaki sağlık sorunlarının önlenmesine katkıda bulunulacaktır. Lojistik şirketleri açısından ise araç filolarının elektrifikasyonu, fosil yakıtlardaki yüksek ve dalgalı fiyatlara karşılık yenilenebilir enerji kaynaklarından üretilen elektrik enerjisinin kullanımı ile lojistik maliyetlerinde ciddi oranda tasarruf anlamına gelmektedir. Lojistik faaliyetlerinde elektrikli araçların (EA’ların) kullanımının yaygınlaşmasının önünde aşılması gereken bazı engeller bulunmaktadır. EA’ların enerji ihtiyacının karşılandığı bataryanın enerji kapasitesinin düşük olması sürüş mesafesine, şarj süresinin uzun olması da şarj istasyonunda (Şİ’de) bekleme süresine olumsuz anlamda etki etmektedir. EA filosuna sahip lojistik şirketleri açısından filonun rotalamasının müşterilerin servis taleplerini miktar ve zaman açısından karşılayabilecek şekilde olması gerekmektedir. Bu tez çalışması kapsamında, şirketlerin EA filolarının rotalanması amacıyla Elektrikli Araç Rotalama Problemi (EARP) türevlerinin etkin bir şekilde çözülmesi amaçlanmıştır. EARP’ye ek olarak zaman penceresi ve eş zamanlı topla-dağıt kısıtlarını birlikte ve ayrı ayrı içeren üç EARP türevi matematiksel olarak modellenmiş, küçük boyutlu problemlerin kesin çözümleri bulunmuş, büyük boyutlu problemlerin çözümü için ise Değişken Komşuluk Arama (DKA) algoritmasını merkezine alan sezgisel çözüm yöntemleri önerilmiştir. Ayrıca DKA kapsamında literatürde kullanılan yerel arama operatörlerine ek olarak probleme özgü operatörler geliştirilmiştir. Yapılan deneysel çalışmalar sonucunda, önerilen sezgisel çözüm yöntemlerinden İndirgenmiş DKA’nın boru ve döngüsel komşuluk değiştirme adımını içeren iki versiyonunun problemlerin çözümünde en etkili algoritmalar olduğu görülmüştür. DKA operatörlerinin çözümü iyileştirme oranlarının problem türüne göre değişiklik gösterdiği, düşük performansa sahip operatörlerin kullanılmaması ile daha kısa sürede daha iyi çözümlere ulaşıldığı gözlemlenmiştir.

The world has agreed to limit the effects of climate change by implementing the Paris Agreement. This requires fundamental and significant changes in the transportation sector, which is among the most carbon-intensive sectors of the global economy. As oil is by far the dominant energy source in the sector, vehicle electrification will play a crucial role in decarbonization. In addition to reducing greenhouse gas emissions, air and noise pollution will also be diminished, contributing to the prevention of related health problems. For logistics companies, electrifying vehicle fleets implies substantial savings in logistics costs through the use of electrical energy produced from renewable sources, as opposed to high and fluctuating fossil fuel prices. Several challenges must be overcome to promote widespread use of electric vehicles (EVs) in logistics activities. The limited energy capacity of EV batteries negatively impacts driving range, while long charging times adversely affect waiting times at charging stations (CSs). For logistics companies with EV fleets, vehicle routing must be designed to meet customers' service demands in terms of both quantity and time. Within the scope of this thesis, the objective is to effectively solve Electric Vehicle Routing Problem (EVRP) derivatives for routing the EV fleets of companies. In addition to EVRP, three EVRP derivatives incorporating time window and simultaneous pickup and delivery constraints, both together and separately, have been mathematically modeled. Exact solutions for small-sized problems have been found, while heuristic solution methods centered on the Variable Neighborhood Search (VNS) algorithm have been proposed for larger problems. Besides the local search operators utilized in the literature, problem-specific VNS operators have been developed. As a result of experimental studies, it has been observed that two versions of the Reduced VNS, one of the proposed heuristic solution methods, featuring the pipe and cyclic neighborhood change step, are the most effective algorithms for solving the problems. It has been noted that the solution improvement rates of VNS operators vary according to problem type, and better solutions can be reached in less time by excluding operators with low performance.