Algoritmo di Ottimizzazione per la Gestione delle Soste dei Veicoli Elettrici nei Servizi V2G

This thesis presents work carried out within the framework of the E-COSMOS project (Electric Charging Optimization for Sustainable MObility Systems). Building on the project’s objectives, it develops an integrated software platform for the simulation, scheduling, and real-time control of an electric vehicle (EV) operating in an urban environment. The platform simultaneously addresses two interdependent problems: the optimization of the daily task visit order under flexible time-window constraints, and the management of the vehicle battery to exploit Vehicle-to-Grid (V2G) energy discharge while preserving the charge needed for driving. The simulation backbone is provided by SUMO (Simulation of Urban MObility), a microscopic open-source traffic simulator, controlled step-by-step through the TraCI Python API. The road network is derived from OpenStreetMap data for a portion of the city of Pavia, Italy, and comprises 2,051 nodes and 4,136 edges. Background traffic is generated stochastically, and the EGO vehicle must navigate through it. The scheduling module performs an exhaustive permutation search for instances of up to eight tasks; for larger instances, it relies on a greedy earliest-deadline-first (EDF) heuristic refined by 2-opt local search. A battery partitioning rule reserves, on top of the absolute minimum state of charge, the estimated energy required for driving, increased by a 30% safety margin, and allocates the surplus to V2G discharge. The routing module combines two mechanisms: periodic traffic-aware rerouting, executed every 5 seconds, and event-driven congestion response, which monitors the road ahead every 2.5 seconds and triggers rerouting whenever congestion is detected. Both mechanisms rely on an energy-aware edge cost function whose weight increases with the battery reserve required for driving. A key technical contribution is the identification and resolution of the same-station consecutive stop problem, a scenario in which two successive tasks share the same charging station. The standard TraCI stop API fails in this configuration due to a geometric constraint: the vehicle’s lane position at the end of the first stop coincides with the station’s downstream boundary, making the second stop command invalid. The proposed solution combines all same-station consecutive tasks into a single SUMO stop with aggregated duration and processes subsequent tasks analytically upon stop completion, while the route is extended during the active stop to ensure the correct onward journey. The platform was evaluated on five simulation runs covering same-station consecutive stops, rigid-priority tasks, a battery-stress scenario and injected congestion under sparse and dense background traffic. In all runs the vehicle completed its tasks, the combined stop worked as intended and the battery partition limited V2G discharge as designed. The measured mean cost of a rerouting call (about 80–115 ms across the runs) remains well below SUMO’s 0.5-second step, as required for real-time operation, and is dominated by the update of the edge travel times of the whole network, while an event-driven check costs about 1 ms.

La presente tesi illustra il lavoro svolto nell’ambito del progetto E-COSMOS (Electric Charging Optimization for Sustainable MObility Systems). Partendo dagli obiettivi del progetto, sviluppa una piattaforma software integrata per la simulazione, la pianificazione e il controllo in tempo reale di un veicolo elettrico (EV) che opera in un contesto urbano. La piattaforma affronta contemporaneamente due problemi interdipendenti: l’ottimizzazione dell’ordine giornaliero di visita delle attività sotto vincoli di finestre temporali flessibili, e la gestione della batteria del veicolo per sfruttare la scarica di energia Vehicle-to-Grid (V2G), garantendo al contempo una carica sufficiente per la guida. La struttura portante della simulazione è fornita da SUMO (Simulation of Urban MObility), un simulatore di traffico microscopico open-source, controllato passo dopo passo tramite l’API Python di TraCI. La rete stradale è ricavata dai dati di OpenStreetMap relativi a una porzione della città di Pavia e comprende 2.051 nodi e 4.136 archi. Il traffico di fondo viene generato in modo stocastico, e il veicolo EGO deve muoversi al suo interno. Il modulo di pianificazione esegue una ricerca per permutazione esaustiva per istanze con un massimo di otto attività; per istanze più grandi, si affida a un’euristica greedy “earliestdeadline-first” (EDF) perfezionata dalla ricerca locale 2-opt. Una regola di partizionamento della batteria riserva, oltre allo stato di carica minimo assoluto, l’energia stimata necessaria per la guida, aumentata di un margine di sicurezza del 30%, e assegna l’eccedenza alla scarica V2G. Il modulo di routing combina due meccanismi: il ricalcolo periodico del percorso in base al traffico, eseguito ogni 5 secondi, e la risposta alla congestione guidata dagli eventi, che controlla la strada davanti al veicolo ogni 2,5 secondi e attiva il ricalcolo del percorso ogni volta che viene rilevata una congestione. Entrambi i meccanismi si basano su una funzione di costo degli archi sensibile al consumo energetico, il cui peso cresce con la riserva di batteria necessaria per la guida. Un contributo tecnico fondamentale è l’identificazione e la risoluzione del problema delle fermate consecutive nella stessa stazione, uno scenario in cui due attività successive condividono la stessa stazione di ricarica. L’API standard TraCI per le fermate non funziona in questa configurazione a causa di un vincolo geometrico: la posizione del veicolo nella corsia al termine della prima fermata coincide con il confine a valle della stazione, rendendo invalido il comando per la seconda fermata. La soluzione proposta raggruppa tutte le attività consecutive presso la stessa stazione in un’unica fermata SUMO con durata aggregata ed elabora analiticamente le attività successive al completamento della fermata, mentre il percorso viene esteso durante la fermata attiva per garantire il corretto proseguimento del viaggio. La piattaforma è stata valutata su cinque simulazioni, che coprono le fermate consecutive nella stessa stazione, le attività a priorità rigida, uno scenario di stress della batteria e una congestione indotta con traffico di fondo rado e denso. In tutte le simulazioni il veicolo ha completato le proprie attività, la fermata combinata ha funzionato come previsto e la partizione della batteria ha limitato la scarica V2G secondo il progetto. Il costo medio misurato di un ricalcolo del percorso (circa 80–115 ms nelle diverse simulazioni) resta ben al di sotto del passo di simulazione di 0,5 secondi di SUMO, come richiesto per un funzionamento in tempo reale ed è dominato dall’aggiornamento dei tempi di percorrenza di tutti gli archi della rete, mentre un controllo guidato dagli eventi costa circa 1 ms.