Upper Bound Finding Algorithms and Mathematical Models for Electric Vehicle Routing Problem with Charging Station Capacity Constraint
Abstract
Electric vehicle routing problem (EVRP) has been addressed in many studies since the sustainability has gained importance. The EVRP has differences compared to the classical internal combustion engine vehicle routing problem. An electric vehicle (EV) has a certain charging capacity and it stops in case of necessity at the appropriate charging station and it is charged to complete its route. In real life, the capacity of charging stations is limited. The number of vehicles charged simultaneously at a station cannot exceed the number of charging units at the related station. In this study, it is assumed that only one EV can be charged at each station at a time. In this study, mathematical models with and without charging station copy nodes are proposed for the relevant problem. Additionally, two upper bound finding algorithms are proposed for the problem. Upper bound finding algorithms are compared in terms of solution time and quality. As a result, feasible solutions are obtained in a shorter time with the proposed upper bound finding algorithms for the problems that mathematical model could not obtain a solution in reasonable times.