Electric Vehicle Routing Problem with Time Windows and Flexible Service Locations

Abstract

The rapid development of shared delivery, parcel lockers, and community pickup services has enabled customers to receive orders at multiple alternative service locations. In such scenarios, the fixed-location assumption adopted in traditional electric vehicle routing problems is no longer appropriate. This paper investigates the Electric Vehicle Routing Problem with Time Windows and Flexible Service Locations (EVRPTW-FSL), in which customers can be served at one selected location from a candidate set, while each service location may accommodate multiple customers subject to capacity limits. A mixed-integer optimization model is developed to jointly determine service location assignments, vehicle routing, and charging decisions under vehicle capacity, battery range, partial recharging, and customer time-window constraints. To balance operational efficiency and customer convenience, the objective minimizes the total travel cost and the customer deviation cost incurred when a customer is assigned to an alternative service location rather than the original service location. To solve this NP-hard problem, a Modified Adaptive Large Neighborhood Search with Fix-and-Optimize mechanism (MALNS-FO) is proposed, incorporating specialized operators such as location association destroy, location similarity destroy, and route reconstruction repair, as well as a fix-and-optimize mechanism. Computational experiments demonstrate that the proposed method consistently outperforms benchmark approaches in solution quality and computational efficiency. Results further show that introducing flexible service locations can significantly reduce fleet usage and routing cost by consolidating spatially dispersed demand. Moreover, moderate customer flexibility provides substantial operational benefits while maintaining acceptable service deviation levels.