Program > By speaker > Keskin Merve

The Electric Vehicle Routing Problem with Time Windows (EVRPTW) is an extension of the well-known VRPTW where an electric vehicle (EV) fleet is used instead of internal combustion engine vehicles. An EV has a limited driving range due to its battery capacity and may need to visit stations for recharging while servicing the customers along its route. Recharging may take place at any battery level and the energy charged may be 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 two recharging configurations which can be referred to normal recharge and fast recharge. In fast recharge, the battery is recharged 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 an extensive computational study to investigate the benefits of fast recharges and test the performance of the proposed approach using benchmark instances from the literature.