Heuristic Solutions for Electric Vehicle Routing Problem with Time Windows and Recharging Stations

Abstract

Due to the regulation and laws concerning the emission of greenhouse gasses, carriers are starting to use electric vehicles for last-mile deliveries. The limited battery capacities of these vehicles necessitate visits to recharging stations during delivery tours of industry-typical length, which have to be considered in the route planning to avoid inefficient vehicle routes with long detours. This thesis seeks to propose new heuristic solution methods for Electric Vehicle Routing Problem with Time Windows (E-VRPTW), which incorporates the possibility of recharging at any of the available charging stations to minimize the total travel distance based on the Clarke and Wright (CW) Saving Heuristic. The solution method focuses on the construction of routes according to waiting time of vehicles, determined priority of customers with regard to their earliest starting service time, customers’ demands and etc. Moreover, the recharging rate, vehicle freight capacity, battery capacity, time windows and recharging time are considered to make it close to real-life logistics problems. Numerical tests are performed on newly designed instances by Schneider and performances of proposed methods are discussed. Keywords: Vehicle Routing Problem, Clarke and Wright Saving Heuristic, Green Logistic, Electric Vehicles, Combinatorial Optimization

ÖZ : Sera gazlarının salınımı ile ilgili kural ve yasalardan dolayı taşımacılar şehir içi taşımalarını elektrikle çalışan araçlarla yapmaya başlamışlardır. Bu araçların sınırlı olan batarya kapasiteleri, taşıma sırasında zorunlu olarak batarya dolum istasyonlarında şarj edilmeleri gereksinimini doğurmakta ve bu durum da uzun ve verimsiz rotaların önlenmesi için rota planlamasında gözönüne alınmalıdır. Bu tezin amacı, alınan toplam mesafeyi enküçüklemek amacıyla şarjın tüm dolum istasyonlarında mümkün olduğu ve Clarke & Wright tasarruf algoritmasını esas alan Electric Vehicle Routing Problem with Time Windows (E-VRPTW) problemine yeni bir sezgisel çözüm yöntemi önermektir. Önerilen çözüm yöntemi öncelikle araçların bekleme sürelerine, müşterilerin zaman önceliklerine, taleplerine vs. göre rotalar oluşturmaya odaklanmaktadır. Problemin lojistik olarak daha da gerçekçi olmasını sağlamak üzere araçların taşıma kapasiteleri, batarya kapasiteleri, zaman aralıkları, şarj zamanları ve hızları da gözönüne alınmıştır. Schneider’in değerleri üzerinden sayısal deneyler de yapılmış ve önerilen yöntemlerin performansları da tartışılmıştır. Anahtar Kelimeler: Araç rotalama sorunu, Clarke ve Wright tasarruf sezgiseli, yeşil lojistik, elektrikli araçlar, birleşi eniyilemesi