By producing zero greenhouse gas emissions, EVs provide a range of environmental benefits. In urban settings, last-mile deliveries typically involve short distances and frequent stops, conditions in which EVs perform particularly well. Electric motors are highly efficient during stop-and-go operations, consume less energy, and require less maintenance than internal combustion engine (ICE) vehicles. As a result, EVs offer clear economic advantages, especially for urban logistics. Each EV type also has its own load capacity and range, making certain EV types more suitable for specific operating contexts. In particular, the ambiant temperature has a significant impact on the EV energy consumption. Indeed, studies show that it can rise by 92% as the temperature decreases from 22°C to -7°C [1]. Notably, the existing EV routing literature often assumes that the energy consumption remains constant over a given distance. While this simplification is valid at an operational (daily) level, we argue that fleet purchasing decisions should account for the temperature variations throughout the year. For these reasons, we study the electric vehicle fleet composition problem [2] with temperature considerations (eFCT). It is a strategic-level problem that accounts for variations in energy consumption due to ambient temperature, and vehicle load. As it is common among last-mile delivery practitioners, we assume the urban area is partitioned into service sectors. Moreover, reflecting typical industry practice, we assume that EVs are charged only overnight and not en route during operations. Given the strategic scope of the eFCT, it is unrealistic to model detailed daily routing decisions over a multi-year planning horizon. Instead, we approximate routing costs. This work builds upon the work presented during ROADEF 2025 [3], by proposing several methodological contributions.

We optimize the composition of an electric vehicle fleet considering several EV types. The fleet serves a given set of sectors over a multi-day planning horizon (365 days in our experiments). Each sector covers a given area and has a density of customers, each with a unitary demand. The sector's centroid is located at a fixed distance from the depot, and the sector's demand must be met every day. Each EV type is characterized by a load capacity, a battery capacity, an energy consumption rate, a purchase cost, and an operating cost. We assume that the depot is equipped with chargers capable of fully recharging all vehicles overnight. In addition, we account for daily energy costs. The operating cost reflects the travel required to reach a sector, serve a subset of its customers, and drive back to the depot. Given the strategic scope of the fleet composition decisions, we approximate the routing costs using the Beardwood–Halton–Hammersley (BHH) formula [4]. We model the energy consumption as a function of daily temperature. Our goal is to determine the optimal fleet composition, i.e. the number of EVs to purchase of each type. This fleet is assumed to be available every day throughout the planning horizon. For each day and each sector, EVs must be assigned such that the total load capacity of the assigned vehicles meets the sector's expected demand. The overall objective is to minimize the total EV purchase cost and total charging costs incurred over the planning horizon.

We propose three main solution methods for the eFCT. The first two method are compact MILP formulations. We first introduce a natural formulation using decision variables representing the fleet composition, along with variables that explicitly indicate how much demand is assigned to each vehicle on each day. We then derive a concavity property for the cost function. Specifically, we show that, for each EV type the most cost-efficient assignment strategy imposes having at most one EV with a load below its full capacity, while all remaining vehicles are either fully used or left unused. This property allows us to construct an alternative MILP formulation in which a subset of variables still represents the fleet composition, whereas others track the number of fully loaded EVs and the demand assigned to the single partially loaded vehicle. Our third solution method is a combination of a lower bound derived by a Lagrangian relaxation and a heuristic solution method for obtaining an upper bound. The heuristic decomposes the problem into a purchasing stage and an assignment stage. In the purchasing stage, EV purchasing decisions are made under the simplifying assumption that all vehicles operate at full capacity. Once the fleet is purchased, the assignment stage then assigns demand to EVs to ensure that fleet capacity suffices to meet the demand. The Lagrangian relaxation is derived from the alternative formulation, by relaxing the constraints that guarantee sufficient fleet is purchased to satisfy demand, and provides a strong lower bound.

To test our solution methods, we generated a set of 50 instances based on temperatures from Marseille and Montréal. Within a maximum running time of one hour, the natural formulation found no optimal solution, whereas the alternative formulation found 15 optimal solutions. Our third method found optimal solutions for 45 instances using a fraction of the computational time. Experimental results for all solution methods, alongside with managerial insights, will be presented during the ROADEF 2026 conference.

[1] Lohse-Busch, H., Duoba, M., Rask, E., Stutenberg, K., Gowri, V., Slezak, L., Anderson, D. (2013). Ambient temperature (20 F, 72 F and 95 F) impact on fuel and energy consumption for several conventional vehicles, hybrid and plug-in hybrid electric vehicles and battery electric vehicle. SAE International, Technical report.

[2] Hiermann G., Puchinger J., Ropke S., Hartl, R.F. (2016). The electric fleet size and mix vehicle routing problem with time windows and recharging stations. European Journal of Operational Research, 252(3), 995-1018.

[3] Vendé P., Jabali O., Naoum-Sawaya J. (2025). The heterogeneous-electric vehicle fleet sizing problem for given service zones considering temperature variations. ROADEF 2025.

[4] Beardwood J., Halton J.H., Hammersley J.M. (1959). The shortest path through many points. Mathematical proceedings of the Cambridge philosophical society, 55(4):299–327.