A two-phase lexicographic optimization framework for fleet sizing and routing in electric vehicle routing problems

Abstract

This paper presents an electric vehicle routing problem with time windows and partial recharging (EVRPTW-PR) in which both the fleet size and the routing plan are decision variables. In many applications, the number of electric vehicles is a tactical decision that drives long-term investments in vehicles, chargers, and drivers, whereas routing is an operational decision made day-to-day for a given fleet. To support decisions at both levels, we formulate EVRPTW-PR with a lexicographic objective, in which we first determine the minimum number of vehicles needed to serve all customers within their time windows under battery and capacity constraints, and then we optimize the total travel distance for that fleet size. To solve this computational challenging problem efficiently, we propose a two-phase adaptive large neighborhood search (ALNS) tailored to this lexicographic structure. In addition, to further reduce computation and guide the search, we develop a supervised learning model that maps instance descriptors to a recommended fleet size. This model replaces the burdensome ALNS for fleet size reduction and warm-starts the second-phase ALNS. Numerical experiments on standard EVRPTW-PR benchmarks show that the designed two-phase ALNS framework improves a state-of-the-art ALNS, and that the learning-enhanced variant reduces the average fleet size by about 0.24 vehicles per instance with very similar travel distances, including under stochastic demand perturbations.