# Integrated Optimization of Fleet Sizing, Deployment, and Routing for Electric Service Vehicles

Bouchra Ben Messabih, Walid Behiri, Sana Belmokhtar-Berraf, Tasseda Boukherroub, Abderrahim Sahli

► To cite this version:

Bouchra Ben Messabih, Walid Behiri, Sana Belmokhtar-Berraf, Tasseda Boukherroub, Abderrahim Sahli. Integrated Optimization of Fleet Sizing, Deployment, and Routing for Electric Service Vehicles. ROADEF 2026, Université de Tours [UT], Feb 2026, Tours, France. hal-05534852

HAL Id: hal-05534852

https://hal.science/hal-05534852v1

Submitted on 3 Mar 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Integrated Optimization of Fleet Sizing, Deployment, and
Routing for Electric Service Vehicles

B. Z. Ben Messabih¹, W. Behiri¹, S. Belmokhtar-Berraf¹, T. Boukherroub² and A. Sahli¹

¹ Univ Gustave Eiffel, COSYS-GRETTIA, F-77454 Marne-la-Vallée, France
{bouchra.benmessabih, walid.behiri, sana.belmokhtar-berraf,abderrahim.sahli
}@univ-eiffel.fr

² École de Technologie superieure (ÉTS) & CIRRELT Montréal, Canada
tasseda.boukherroub@etsmtl.ca

**Keywords** : MILP, fleet sizing, fleet deployment, routing, electric fleet.

# 1 Introduction

The transition toward sustainable urban mobility has become a central objective for public transport operators worldwide. In this context, the Société de Transport de Montréal (STM) has launched an ambitious plan to electrify its entire service fleet by 2030, aiming to reduce greenhouse-gas emissions and improve air quality while ensuring the economic viability and reliability of its operations. Among the vehicles concerned are those assigned to Operations Supervisors (OS), who play a key role in maintaining service continuity by responding to incidents and disruptions across the bus network. Electrifying this fleet is therefore not only an environmental measure, but also an opportunity to enhance service quality, minimize delays, and strengthen passenger satisfaction [2]. However, the electrification of service vehicles introduces new strategic and operational challenges, notably in determining the optimal fleet size, the geographical deployment of vehicles, and their routing to incident locations. These decisions must balance environmental objectives, operational costs, and service-level performance. The literature on emergency fleet management covering medical [1], fire, traffic [5], and disaster response provides valuable insights through classical problems such as location, deployment, dispatching, relocation, and routing [4]. However, few studies explicitly address the integration of these decisions within the context of electric vehicle fleets for public transport operations.

# 2 Problem description and assumptions

The study focuses on the island of Montréal, which is divided into 15 operational sectors and served by eight STM depots. These depots not only store buses but also provide key maintenance, charging, and support services. Each depot hosts OS working in rotating 6-hour shifts to ensure service continuity across the bus network. When an incident occurs such as equipment failure, signage malfunction, or passenger disruption the Central Operations Center coordinates a rapid response by dispatching the nearest available OS vehicle. Each incident is defined by its geographic position and service duration. The objective of this research is to determine the optimal fleet size and spatial allocation of OS service vehicles across depots, while accounting for their routing through incident locations as an operational necessity. The aim is to support cost-efficient investment decisions without compromising service quality or responsiveness. Although the proposed approach is not intended as a real-time incident-management tool, it integrates the characteristics of incident response, which lie at the core of these vehicles' mission. To capture operational realism, several assumptions are made: incidents are treated with equal priority, each requires one vehicle, service times and vehicle speeds are known, and travel distances are computed using geodesic measures.
# 3 Solution methods

We developed a lexicographic bi-objective Mixed-Integer Linear Programming (MILP) model designed to optimize the deployment and routing of the STM's electric service vehicles [3]. The formulation reflects the company's priorities by minimizing the fleet size before the total response time, thus achieving a balance between economic efficiency and service quality. The model simultaneously addresses strategic and operational decisions, including the number of vehicles to deploy, their assignment to depots, and their routing across incidents within each service shift. To assess its performance, the model was implemented in Java and solved using CPLEX 22.1. In the numerical experiments, we generated instances based on incident data produced by a forecasting model trained on several years of historical observations. These instances faithfully reflect Montréal's operational environment and allow us to evaluate the model under realistic demand conditions. Numerical results show that the formulation efficiently solves small-scale cases within short computation times. However, given the NP-hard nature of the problem, solving larger instances directly quickly becomes computationally challenging. This limitation motivated us to explore decomposition-based strategies. Preliminary tests indicate that such approaches could substantially improve scalability.

# 4 Conclusions and perspectives

This study presents a bi-objective MILP model for Montréal's electric service vehicle, integrating strategic fleet sizing and depot allocation with operational vehicle routing. A lexicographic approach is applied to prioritize minimizing fleet size before reducing response times. Computational tests on STM-representative instances confirmed its effectiveness for small-scale problems, though scalability remains a challenge beyond ten incidents. To tackle larger instances, a decomposition heuristic was introduced, showing encouraging preliminary results. Future work will aim to extend the current framework by incorporating tactical-level decisions, such as shift scheduling and charging planning for electric service vehicles. To tackle large-scale instances, we plan to explore decomposition-based techniques. Additionally, to account for the dynamic and stochastic nature of demand, simulation-based approaches will be considered, enabling a more realistic evaluation of operational performance under uncertainty.

# References

[1] Y Frichi and F Jawab. A review and classification of ambulance deployment and redeployment models in emergencies. 'A review and classification of ambulance deployment and redeployment models in emergencies'. Technical Report 1, 2024.

[2] MS Hossain, Laveet Kumar, MM Islam, and Jeyraj Selvaraj. A comprehensive review on the integration of electric vehicles for sustainable development. *Journal of Advanced Transportation*, 2022(1):3868388, 2022.

[3] B. Z. Ben Messabih, W. Behiri, S. Belmokhtar-Berraf, T. Boukherroub, A. Sahli, and I. Zouaghi. A lexicographic bi-objective approach to fleet sizing and routing for service vehicles in a real-world passenger transport system. In *Proceedings of the 11th International Conference on Control, Decision and Information Technologies (CoDIT)*, Split, Croatia, 2025. IEEE. To appear.

[4] Guangli Zhang, Rui Ma, Yunfeng Kong, Chenchen Lian, Hao Guo, and Shiyan Zhai. A multi-period capacitated facility location problem with maximum travel time and backup service for locating and sizing EMS stations. *Computational Urban Science*, 4(1), 12 2024.

[5] Lu Zhen, Jingwen Wu, Fengli Chen, and Shuaian Wang. Traffic emergency vehicle deployment and dispatch under uncertainty. *Transportation Research Part E: Logistics and Transportation Review*, 183, 3 2024.