Charge scheduling and route planning of commercial electric vehicles by considering the effect of battery degradation

Abstract

Batarya, kısıtlı kullanım ömrü ve yüksek ürettim maliyetlerinden dolayı elektrikli araçların (EA) en önemli bileşenlerinden biridir. Bu sebeple eş güdümlü ve gelişmiş rota planlamaları ile beraber uygulanacak iyileştirilmiş şarj ve deşarj uygulamaları batarya sağlığını korumak ve bataryanın hızlı yıpranmasını önlemek için bir çözüm olabilir. Bu çalışmada Zaman Pencereli Elektrikli Gezgin Satıcı Problemi (ZPEGSP) ve Zaman Pencereli Elektrikli Araç Rotalama Problemi (ZPEARP) kapsamında batarya yıpranmasına ilişkin maliyetlerin ticari EA'ların rota ve şarj planlamaları sırasında dikkate alınmasının etkisini inceliyoruz. İlk olarak ZPEGSP'nin matematiksel programlama formülasyonunu amaç fonksiyonunun batarya yıpranması ve enerji tüketimiyle ilişkilendirilen maliyetleri en küçükleyeceği şekilde genişletiyoruz. Daha sonrasında, sezgisel sonuçların son optimizasyonu için kullanılan kesin çözücüyle geliştirilmiş Değişken Komşuluk Arama (DKA) tabanlı bir mat-sezgisel geliştiriyoruz. Mat-sezgiselimiz problemimize özgü tasarlanan bir mekanizma da içermektedir. Akabinde, literatürdeki problem örneklerini kullanarak sayısal deneyler gerçekleştiriyoruz ve elde ettiğimiz sonuçlar önerdiğimiz mat-sezgiselin iyi kalitede çözümlere makul çalışma süreleri içerisinde ulaştığını gösterir. Ayrıca, batarya yıpranmasını dikkate alarak ZPEARP'nin matematiksel modelini de genişletiyoruz ve literatürdeki küçük boyutlu örnekleri bu model ile çözerek bir deney gerçekleştiriyoruz. İki problem ortamında da elde ettiğimiz sonuçlar, batarya yıpranmasını probleme dahil etmenin rota planlamalarında dikkate değer değişikliklere sebep olabileceğini gösterir. Bir yandan sadece enerji sarfiyatının en küçüklendiği durumda elde edilen çözümlere kıyasla işletme maliyetlerinde önemli bir azalma imkanı sunar. Diğer yandan, rota boyunca daha sık şarj yapılmasına yol açar ve bu da ek operasyonel engeller getirir.

Battery is a critical component of electric vehicles (EVs) due to its limited useful economic life and high production cost. Hence, better recharging and discharging practices through coordinated and improved route planning decisions may be a remedy for maintaining good battery health and avoiding fast degradation. In this study, we investigate the effect of considering the battery degradation-related cost on the route and charge planning of commercial EVs within the context of the Electric Traveling Salesman Problem with Time Windows (ETSPTW) and Electric Vehicle Routing Problem with Time Windows (EVRPTW). First, we extend the mathematical programming formulation of the ETSPTW, where the objective function minimizes the costs associated with battery degradation and energy consumption. Next, we develop a Variable Neighborhood Search (VNS) based matheuristic enhanced with an exact solver employed for the post-optimization of heuristic solutions. Our matheuristic also includes a new mechanism designed specific to our problem. Then, we perform computational experiments using benchmark instances from the literature, and our results demonstrate that the proposed matheuristic achieves good quality solutions within reasonable computational time. We also extend the mathematical model of the EVRPTW by considering the battery degradation and conduct a computational study by solving small-size instances from the literature on a commercial solver. Our results in both problem settings show that incorporating battery degradation in the problem may yield significant changes in the route plans. On the one hand, it offers a potential for substantial reduction in operational costs compared to the solutions obtained by minimizing energy consumption only. On the other hand, it leads to more frequent recharges en route, which brings in additional operational hurdles.