A Benders Decomposition Approach for Solving the Electric Vehicle Routing Problem with Soft Time Windows
Soheil Jalili  1, *@  , Farid Khoshalhan  1@  
1 : K. N. Toosi University of Technology, Faculty of Industrial Engineering  -  Website
* : Corresponding author

The Electric Vehicle Routing Problem with Time Windows (EVRPTW) is a variant of the VRP where battery electric vehicles (BEVs) are used in order to service customers with time windows. A BEV has a limited travel range due to its battery charge capacity and may need to be recharged at recharging stations. EVRPTW aims at minimizing the number of capacitated vehicles and total travelling costs. In this study, we model the Electric Vehicle Routing Problem with Soft Time Windows (EVRPSTW) by allowing vehicles to visit customers beyond their time windows by a given tolerance, which enables early and late servicing with some penalty costs. EVRPSTW challenges the distribution task of public services and private organizations in a context with heavy traffic, which servicing customers within their time windows is severe. Moreover, the hard time windows can strongly increase the vehicle number necessary to serve all customers, which leads to very high vehicle acquisition costs. Therefore, the flexibility in time windows enables big savings in the investments on vehicle fleet, since the possibility to serve customers out of their time window range may reduce the vehicle number. We formulate this problem as a mixed integer linear program and solve the small instances using CPLEX. To solve the larger problems we develop a Benders decomposition approach. We carried out a computational study to investigate the benefits of soft time windows and test the performance of the proposed approach using benchmark instances from the literature in terms of solution times and quality.

Online user: 1 RSS Feed