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 etkilerinisınırlamayı kabul etmiştir. Bu da dünya ekonomisinin en yoğun karbon-yoğunsektörlerinden biri olan ulaştırma sektöründe temel ve köklü değişikliklerigerektirmektedir. 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 roloynayacaktır. Böylece sera gazı emisyonuna ek olarak hava ve gürültü kirliliği deazaltı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ıtlardakiyüksek ve dalgalı fiyatlara karşılık yenilenebilir enerji kaynaklarından üretilenelektrik enerjisinin kullanımı ile lojistik maliyetlerinde ciddi oranda tasarrufanlamı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ı engellerbulunmaktadır. EA'ların enerji ihtiyacının karşılandığı bataryanın enerjikapasitesinin düşük olması sürüş mesafesine, şarj süresinin uzun olması da şarjistasyonunda (Şİ'de) bekleme süresine olumsuz anlamda etki etmektedir. EAfilosuna sahip lojistik şirketleri açısından filonun rotalamasının müşterilerin servistaleplerini 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ı topladağıt kısıtlarını birlikte ve ayrı ayrı içeren üç EARP türevi matematiksel olarakmodellenmiş, küçük boyutlu problemlerin kesin çözümleri bulunmuş, büyükboyutlu 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 DKAkapsamında literatürde kullanılan yerel arama operatörlerine ek olarak problemeözgü operatörler geliştirilmiştir. Yapılan deneysel çalışmalar sonucunda, önerilensezgisel çözüm yöntemlerinden İndirgenmiş DKA'nın boru ve döngüsel komşulukdeğiştirme adımını içeren iki versiyonunun problemlerin çözümünde en etkilialgoritmalar olduğu görülmüştür. DKA operatörlerinin çözümü iyileştirmeoranlarının problem türüne göre değişiklik gösterdiği, düşük performansa sahipoperatörlerin kullanılmaması ile daha kısa sürede daha iyi çözümlere ulaşıldığıgözlemlenmiştir.ANAHTAR KELİMELER: Elektrikli araç rotalama problemi, değişkenkomşuluk arama algoritması, sezgisel çözüm yöntemi, kesin çözüm yöntemi

The world has agreed to limit the effects of climate change by implementingthe Paris Agreement. This requires fundamental and significant changes in thetransportation sector, which is among the most carbon-intensive sectors of theglobal economy. As oil is by far the dominant energy source in the sector, vehicleelectrification will play a crucial role in decarbonization. In addition to reducinggreenhouse 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 theuse of electrical energy produced from renewable sources, as opposed to high andfluctuating fossil fuel prices. Several challenges must be overcome to promotewidespread use of electric vehicles (EVs) in logistics activities. The limited energycapacity of EV batteries negatively impacts driving range, while long chargingtimes adversely affect waiting times at charging stations (CSs). For logisticscompanies 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 ElectricVehicle Routing Problem (EVRP) derivatives for routing the EV fleets ofcompanies. In addition to EVRP, three EVRP derivatives incorporating timewindow and simultaneous pickup and delivery constraints, both together andseparately, have been mathematically modeled. Exact solutions for small-sizedproblems have been found, while heuristic solution methods centered on theVariable Neighborhood Search (VNS) algorithm have been proposed for largerproblems. Besides the local search operators utilized in the literature, problemspecific 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 proposedheuristic solution methods, featuring the pipe and cyclic neighborhood change step,are the most effective algorithms for solving the problems. It has been noted thatthe solution improvement rates of VNS operators vary according to problem type,and better solutions can be reached in less time by excluding operators with lowperformance.KEYWORDS: Electric vehicle routing problem, variable neighborhood searchalgorithm, heuristic solution approach, exact solution approach