The electric vehicle shortest path problem with hard time windows and prize collection

The Shortest Path Electric Vehicle Problem (SPEVP) aims at finding the shortest path for an electric vehicle (EV) departing from a given origin and arriving at a given destination. The limited autonomy of the EV is considered, and recharging its battery at charging stations (CS) is permitted. Due to the scarcity of CSs, compared to gas stations, finding an EV shortest path is difficult. The EV is allowed to partially recharge its battery at CSs, which may have different charging technologies. Furthermore, the charging time follows a nonlinear charging function. In particular, we consider long EV trips, e.g., when the unrestricted travel time between the origin and the destination is at least six hours. During such long trips. several charging stops may be necessary. The driver may have certain preferences to stop at CSs that match her interest, e.g., visiting cultural sites. Moreover, the user may also want to perform some particular activity during specific time windows, like having lunch or sleeping. Therefore, the overall goal of the thesis is to model and solve a version of the SPEVP in which the charging decisions along the path are harmonized with user preferences and requirements. To achieve this goal, we attribute a score for each CS, which represents how much it suits the preferences of the user. We then address the problem of finding a route that maximizes the total gained score, respects all the time windows and never violates the EV autonomy constraints. In particular, we impose a temporal tolerance on the deviation of such a path from the shortest EV path in time. We propose a MILP formulation for this setting which we denote with Maximum Discounted Profit Model, and we develop a heuristic for it. The latter is based on a A* search algorithm, which works with modified arc weights of the graph in order to account for the CS scores. We evaluate our models on several realistic instances, with CSs located in Central Europe. In particular, we demonstrate the effectiveness of the proposed heuristic, when compared to the exact solutions obtained by the MILP.

Il Problema dei Cammini Minimi per Veicoli Elettrici (SPEVP) cerca di trovare il cammino più veloce per un veicolo elettrico che percorre la strada da una data origine ad una data destinazione. Viene considerata l'autonomia limitata dei veicoli elettrici, ed è ammessa la ricarica, anche parziale, della batteria nelle stazioni di ricarica, le quali possono avere tecnologie di ricarica differenti. A causa della scarsità di stazioni di ricarica, rispetto alle stazioni di benzina, trovare il cammino più veloce per un veicolo elettrico è complesso. In particolare, si considerano lunghi viaggi, ad esempio quando il tempo minimo tra origine e destinazione senza tappe di ricarica è superiore alle sei ore. Durante questi lunghi viaggi, potrebbero essere necessarie diverse tappe per la ricarica. Il guidatore potrebbe preferire di fermarsi in stazioni di ricarica che ben rappresenta i suoi interessi, ad esempio, visitando siti culturali. Inoltre, l'utente potrebbe anche voler svolgere determinate attività durante specifiche finestre temporali, come pranzare o dormire. L'obbiettivo di questa tesi è quello di modellare e risolvere una versione del SPEVP in cui le decisioni sulle fermate di ricarica lungo il percorso sono allineate con le preferenze e i vincoli imposti dall'utente. Per raggiungere questo scopo, si è attribuito ad ogni stazione di ricarica un punteggio che rappresenta quanto quella stazione è interessante per l'utente. Si è poi considerato il problema di trovare un percorso che massimizza il punteggio totale ottenuto, che rispetti tutte le finestre temporali e che non violi mai i vincoli di autonomia del veicolo elettrico. Inoltre, si è imposto una tolleranza temporale sulla deviazione del percorso ottenuto rispetto alla percorso più veloce. Si è poi proposta una formulazione MILP per questo tipo di problema denotata con il nome di Modello del Massimo Profitto Scontato, e si è sviluppata una euristica per risolverlo. Quest'ultima si basa sull'algortimo di ricerca A*, che lavora con dei pesi modificati per ogni arco del grafo, in modo da tener conto dei punteggi per ogni stazione di ricarica. Si sono poi valutati i nostri modelli su diverse tratte realistiche, con stazioni di ricarica posizionati in Europa Centrale. Infine si è dimostrata l'efficacia dell'euristica proposta, rispetto alla soluzione esatta ottenuta dal MILP.