Erdeş H.Kesen S.E.2026-03-102026-03-10202697830321701941865-0929https://doi.org/10.1007/978-3-032-17020-0_15https://hdl.handle.net/20.500.13091/13084Sustainable logistics systems encompass critical components of environmental sustainability, such as reducing carbon emissions, and social sustainability, improving community well-being and ensuring fair working conditions. Consequently, there has been a growing shift towards alternative transportation modes like Electric Vehicles (EVs), which have increasingly attracted the attention of the operations research community. In this paper, we investigate the Speed and Load Dependent Multi-Depot Electric Vehicle Routing Problem with Half-Open Rotations (SLD-MDEVRP-HOR), considering two conflicting objective functions: the minimization of CO2 emissions and the minimization of total tardiness. In this problem, customer demands are fulfilled by a homogeneous and limited fleet of EVs with specific battery and load capacities. EVs are allowed to serve multiple routes (rotations) and may end their journeys at a different depot from the one they depart from (half-open rotations). While recharging is possible both at depots and at Recharging Stations, load replenishment is only performed at depots. An energy consumption model is employed, which incorporates the effects of five discrete speed modes and the vehicle’s carried load. Given that the problem is a variation of the well-known NP-hard Vehicle Routing Problem, we develop a metaheuristic algorithm named the Multi-Directional Local Search algorithm, which is based on the concept of Pareto dominance. Computational experiments are conducted on modified small- and large-sized instances derived from recent literature. To evaluate the performance of the proposed algorithm, we report the number of Pareto solutions, Quality Metric values, Hypervolume values and run time of each solution with different seeds. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2026.eninfo:eu-repo/semantics/closedAccessElectric Vehicle Routing ProblemHalf-Open RotationsMulti-Directional Local SearchMulti-Objective OptimizationConference Object10.1007/978-3-032-17020-0_152-s2.0-105030341450