Scientific Program > Talks by Speaker > Taş Duygu

This paper studies the Electric Vehicle Routing Problem with Flexible Time Windows (EVRPFTW). In this problem, EVs are permitted to serve customers outside their original time window boundaries with respect to a given tolerance. This relaxation brings a penalty cost as time window violations negatively affect the customer satisfaction. The objective of the EVRPFTW is to minimize the total cost including the traveling costs, the costs of using electric vehicles and the penalty costs. We propose a solution procedure based on column generation where the pricing subproblem corresponds to an elementary shortest path problem with resource constraints. An integer solution is generated by solving an integer programming problem using the routes constructed by the column generation algorithm. A linear programming model is then solved to compute the optimal times to start service at each customer for the selected routes. We conduct our computational experiments for a number of well-known benchmark instances and evaluate the operational gains obtained by employing flexible time windows.