Lorenzo Calosso
Mixing decomposition techniques and approximate dynamic programming for the Stochastic Electric Vehicle Routing Problem.
Rel. Edoardo Fadda, Ornella Pisacane, Maurizio Bruglieri, Domenico Potena. Politecnico di Torino, Corso di laurea magistrale in Data Science And Engineering, 2024
Abstract: |
This work addresses the Electric Vehicle Routing Problem with Time Windows (E-VRPTW), incorporating stochastic consumption and travel times due to possible uncertainties in road conditions and unforeseen events. Unlike traditional approaches that assume deterministic variables, this study formulates a more realistic version of the E-VRPTW, where both energy consumption and travel times are subject to fluctuations. Furthermore, the problem is complicated by the need for electric vehicles (EVs) to recharge at stations en-route, given their limited driving range. In order to address this complexity, a solution methodology combining Approximate Dynamic Programming (ADP) and Column Generation (CG) is proposed. The ADP agents are created to optimize energy consumption and time management while accounting for factors such as partial recharging and the dynamic state of charge (SOC) of the vehicles. Different approaches for representing the value function, including full discretization and approximation via interpolators, are compared in terms of solution accuracy and computational efficiency. Many tests are then conducted on instances of increasing size and complexity, in order to evaluate the overall performance of this approach. The results are able to demonstrate that the proposed solution can effectively handle uncertainty, reducing total costs while maintaining adherence to the various constraints. |
---|---|
Relators: | Edoardo Fadda, Ornella Pisacane, Maurizio Bruglieri, Domenico Potena |
Academic year: | 2024/25 |
Publication type: | Electronic |
Number of Pages: | 65 |
Additional Information: | Tesi secretata. Fulltext non presente |
Subjects: | |
Corso di laurea: | Corso di laurea magistrale in Data Science And Engineering |
Classe di laurea: | New organization > Master science > LM-32 - COMPUTER SYSTEMS ENGINEERING |
Aziende collaboratrici: | Politecnico di Torino |
URI: | http://webthesis.biblio.polito.it/id/eprint/33044 |
Modify record (reserved for operators) |