Değişken komşuluk arama algoritmaları ile elektrikli araç rotalama problemlerinin çözümü
Variable neighborhood search algorithms for solving electric vehicle routing problems
Yazar: YUSUF YILMAZ
Danışman: DR. ÖĞR. ÜYESİ CAN BERK KALAYCI
Pamukkale Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2023
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
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ı topladağı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.
ANAHTAR KELİMELER: Elektrikli araç rotalama problemi, değişken
komşuluk arama algoritması, sezgisel çözüm yöntemi, kesin çözüm yöntemi

Abstract:
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, 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 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.
KEYWORDS: Electric vehicle routing problem, variable neighborhood search
algorithm, heuristic solution approach, exact solution approach