Scientific Program > Talks by Speaker > Duman Ece Naz

We study the Electric Vehicle Routing Problem with Time Windows (EVRPTW) where electric vehicles (EVs) with limited driving range may need to recharge their batteries en-route in order to complete their tours. Recharging may take place at any battery state of charge and at any station, and its duration is linearly proportional to the amount of energy transferred. We address two variants of the problem where the stations are equipped with single and multiple charging technologies. We solve these problems by employing a branch-and-price method based on a column generation algorithm. We develop a modified version of the ng-route algorithm to solve the pricing subproblem of the column generation method, which corresponds to the Elementary Shortest Path Problem with Resource Constraints (ESPPRC). A two-stage label correcting algorithm based on ng-route algorithm is implemented to solve the ESPPRC. The ng-route algorithm is then improved by applying the state-of-the-art acceleration techniques including a heuristic column generator and a bounding procedure. In addition, we reduce the size of the transportation digraph by eliminating the dominated stations and merging station nodes with customer nodes, which further speeds up the algorithm. The performances of the proposed methods are tested by conducting an extensive computational study using well-known benchmark instances from the literature.