title   
  

A matheuristic method for the electric vehicle routing problem with time windows and fast chargers

Keskin, Merve and Çatay, Bülent (2017) A matheuristic method for the electric vehicle routing problem with time windows and fast chargers. [Working Paper / Technical Report] Sabanci University ID:UNSPECIFIED

[img]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
1094Kb

Abstract

The Electric Vehicle Routing Problem with Time Windows (EVRPTW) is an extension of the well-known VRPTW where electric vehicles (EVs) are used instead of internal combustion engine vehicles. An EV has a limited driving range due to its battery capacity and may need recharging to complete its route. Recharging can be made at any battery level and may be at any quantity up to the battery capacity. Furthermore, the stations may be equipped with chargers with different power supply, power voltage, maximum current options which affect the recharge duration. In this study, we model the EVRPTW by allowing partial recharges with three recharging configurations which can be referred to as normal, fast and super-fast recharges. In faster options, the battery is charged with the same energy in a shorter time but at a higher cost. Our objective is to minimize the total recharging cost while operating minimum number of vehicles. We formulated this problem as a mixed integer linear program and solved the small instances using CPLEX. To solve the larger problems, we develop a matheuristic approach which couples the Adaptive Large Neighborhood Search (ALNS) approach with an exact method. Our ALNS is equipped with various destroy-repair algorithms to efficiently explore the neighborhoods and uses CPLEX to strengthen the routes obtained. We carried out extensive experiments to investigate the benefits of fast recharges and test the performance of our algorithm using benchmark instances from the literature. The results show the effectiveness of the proposed matheuristic and demonstrate the benefits of fast chargers on the fleet size and energy costs.

Item Type:Working Paper / Technical Report
Uncontrolled Keywords:Electric vehicle; vehicle routing problem with time windows; adaptive large neighborhood search; matheuristic; partial recharge; fast recharge
Subjects:T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis
ID Code:34879
Deposited By:Bülent Çatay
Deposited On:25 Jun 2018 11:53
Last Modified:25 Jun 2018 11:53

Repository Staff Only: item control page