Electric Vehicle Routing With Flexible Time Windows: a Column Generation Solution Approach

Abstract

In this paper, we introduce the Electric Vehicle Routing Problem with Flexible Time Windows (EVRPFTW) in which vehicles are allowed to serve customers before and after the earliest and latest time window bounds, respectively. The objective of this problem is to assign electric vehicles to feasible routes and make schedules with minimum total cost that includes the traveling costs, the costs of using electric vehicles and the penalty costs incurred for earliness and lateness. The proposed mathematical model is solved by a column generation procedure. To generate an integer solution, we solve an integer programming problem using the routes constructed by the column generation algorithm. We further develop a linear programming model to compute the optimal times to start service at each customer for the selected routes. A number of wellknown benchmark instances is solved by our solution procedure to evaluate the operational gains obtained by employing flexible time windows.