SCRO / Journées de l'optimisation

HEC Montréal, 29-31 mai 2023


HEC Montréal, 29 — 31 mai 2023

Horaire Auteurs Mon horaire

OEVCII Optimizing Electric Vehicle Charging Infrastructure II

29 mai 2023 15h30 – 17h10

Salle: TAL Gestion globale d'actifs inc. (vert)

Présidée par Mohsen Dastpak

4 présentations

  • 15h30 - 15h55

    Joint Optimization of Electric Bus Scheduling and Fast Charging Infrastructure Location Planning

    • Kayhan Alamatsaz, prés., Concordia University
    • Frédéric Quesnel, GERAD
    • Ursula Eicker, Concordia University

    Beginning in 2025, Montreal has committed to purchasing only fully electric buses (EB), and the adopted strategy for charging these fully electric buses is fast-charging infrastructure technology. Therefore, fast-charging infrastructure planning would emerge as a crucial problem. Moreover, scheduling of EBs is different from conventional buses concerning the charging limitation. Electric buses have battery limitations, and their operation process regarding scheduling and charging is different from conventional buses. The operating range of EBs is less and their charging time is more than refueling diesel buses. Thus, to improve bus scheduling, a reasonable charging strategy is required.
    This study aims to integrate fast-charging infrastructure planning and electric bus scheduling to minimize the number of required vehicles. The objectives of the study are finding the optimum number of charging stations and their best locations and minimizing the number of EBs and deadhead trips. We develop a mathematical optimization model and use Column Generation algorithm to deal with large-scale problems. The model can solve relatively large problems with promising optimality gaps in a reasonable time. The findings of this study will provide important insights for transit authorities on how to effectively transition to a fully electric bus fleet while maintaining operational efficiency.
    Keywords: Electric bus scheduling, Fast charging station location, Column Generation, MILP

  • 15h55 - 16h20

    Mean Field Games and Model Predictive Control for Charging Electric Vehicles in Solar Powered Parking Lots

    • Samuel M. Muhindo, prés., Polytechnique Montréal
    • Roland Malhamé, GERAD - Polytechnique Montréal
    • Geza Joos, McGill University

    We propose a strategy, with concepts from Mean Field Game (MFG) theory and Model Predictive Control (MPC), to coordinate the charging of a large population of battery electric vehicles (BEVs) in a parking lot powered by solar energy and managed by an aggregator. An ARIMA model is used for solar forecasting, while a Poisson distribution (with finite population) model of BEV arrivals and departures is assumed. Both model forecasts are updated as fresh observations become available. We propose a MFG-MPC strategy to recharge BEVs present in the parking lot. The goal is to share the solar energy so as to minimize the standard deviation (STD) of the state of charge (SOC) of BEVs of the time vehicles leave the parking lot, while maintaining some fairness and decentralization criteria.

  • 16h20 - 16h45

    The Electric Time-Dependent Capacitated Arc Routing Problem with Non-linear Consumption

    • Jahir Llagas, Pontifícia Universidade Católica do Rio de Janeiro (PUC-Rio)
    • Rafael Martinelli, prés., Pontifícia Universidade Católica do Rio de Janeiro (PUC-Rio)

    The eco-awareness has increased efforts to reduce greenhouse gas emissions and promote alternative energy. Since the transport sector significantly contributes to carbon dioxide emissions, electric vehicles (EVs) are a promising alternative to fossil fuel vehicles. However, limited range, battery degradation, and long charging times hinder their widespread adoption. The literature on EV routing problems has evolved, with studies focusing on charging policies, charging models, and energy consumption. However, mathematical models are complex, and the numerous variables make it challenging to address all issues simultaneously. This work proposes a new problem, the Electric Time-Dependent Capacitated Arc Routing Problem (E-TDCARP), which integrates EVs into the Time-Dependent Capacitated Arc Routing Problem with Travel Times. The E-TDCARP addresses oversimplifications in EV routing problems related to energy consumption calculations, such as single and constant speed, mass, and travel time. We propose a method to preprocess the energy consumption function based on mass and time and an algorithm to obtain the quickest paths for each node pair with their respective energy consumption functions. Two scenarios are evaluated, one with constant mass and another with variable mass. The approach aims to identify the impact of mass, speed, and travel times on energy consumption, check solution feasibility under different battery capacity levels, and compare the results obtained. A metaheuristic approach combining ILS and SA with penalties is implemented to solve the problem. Computational analyses based on solutions of literature-based instances show the approach efficiency and the impact of the time dependency and the non-linear consumption functions.

  • 16h45 - 17h10

    Dynamic Routing for Electric Vehicle Shortest Path Problems with Charging Station Occupancy Information

    • Mohsen Dastpak, prés., École de technologie supérieure
    • Fausto Errico, École de technologie supérieure
    • Ola Jabali, Politecnico di Milano
    • Federico Malucelli, DEI, Politecnico di Milano

    Electric vehicles (EVs) have the potential to revolutionize transportation. However, EVs face technical challenges that require consideration, such as limited autonomy, sparsely and unevenly dispersed charging stations (CSs), long charging sessions, and long waiting times at public CSs. In this paper, we focus on long-distance trips, where an EV opts to travel from an origin to a destination in the shortest amount of time. Nowadays, technology advances have provided us with online tools that allow us to access real-time information regarding the occupancy of CSs as a binary indicator.
    In particular, we quantify the added value of this information in enhancing the decision-making process. We formulate the problem as a Markov Decision Process (MDP) that aims at developing a routing and charging policy for the EV to choose the next location to drive to and the amount of charge to receive in order to minimize the total duration of its trip. We then propose an online reoptimization algorithm based on the MDP formulation that incorporates the occupancy indicator of CSs to solve this problem. Finally, we conduct a comprehensive computational study and compare the performance of our method with a benchmark that observes the status of CSs only upon arrival (i.e., no occupancy indicator is available). Results show that our method reduces waiting times and total trip duration by an average of 23.7%-95.4% and 1.4%-18.5%, respectively. A sensitivity analysis show that our method is most effective in situations where CSs are slower, there is a higher capacity for EVs waiting in queues, and the EV needs to recharge more frequently during its journey between the origin and destination.

    Keywords: Battery-equipped vehicles, Shortest path routing, Charging Station Occupancy Information