As the transport industry shifts towards Battery Electric Vehicles (BEVs) the need for accurate route planning rises. BEVs have reduced range compared to traditional fuel based vehicles, and the range can vary greatly depending on ambient conditions and vehicle load. Existing research focuses more on the theoretical algorithms, and often have none or very simple vehicle models, leaning towards consumer cars instead of heavy duty trucks. Vehicle Route Planning (VRP) is a wide research area, and this thesis focuses on the Shortest Path subproblem. Contraction Hierarchies (CHs) is a commonly used family of algorithms for finding shortest paths in road networks, and is prevalent in the research frontier. CHs however comes with certain drawbacks, such as having to perform a costly preprocessing phase whenever metrics change, and not being able to share map data between multiple vehicles in a fleet. This thesis extends CHs to support a mixed fleet, with fast metric updates and support for more detailed cost optimization goals. This is done by implementing Customizable Contraction Hierarchies (CCHs), but with custom data structures and customization phase. This implementation allows map data to be shared between vehicles in a fleet, and keeps each vehicle's edge weights separate. The edge weights can be updated quickly, as the customization phase scales linearly with the size of the map. The implementation also supports edge weights that do not adhere to triangle inequality, which the previous research did not. Experiments are executed on a map of Stockholm and a synthetic map, to test the algorithm's performance, verify correctness, and stress the importance of accurate metrics for optimization goals. The CCH performed as expected, if not better, and its correctness is upheld. The implementation is fit to be integrated into a route planner, but further research should be conducted to see how it meshes with other parts of VRP, such as time windows, turn costs, and charging stations. / När transportindustrin övergår till batterielektriska fordon ökar behovet av rigorös ruttplanering. Batterielektriska fordon har minskad räckvidd jämfört med traditionella bränslebaserade fordon, och räckvidden kan variera stort beroende på omgivningsförhållanden och fordonets belastning. Existerande forskning fokuserar mer på de teoretiska algoritmerna och har ofta inga eller mycket enkla fordonsmodeller, som liknar mer konsumentbilar istället för tunga lastbilar. Ruttplanering är ett brett forskningsområde, och denna avhandling fokuserar på underproblemet att hitta kortaste vägen. Kontraktionshierarkier är en välanvänd familj av algoritmer för att hitta kortaste vägen i ett vägnät, och är prevalent i forskningsfronten. Kontraktionshierarkier har dock vissa nackdelar, som att de behöver utföra en kostsam förbehandlingsfas när parametrar ändras, och att kartdatan inte kan delas mellan flera fordon i en flotta. Den här avhandlingen utökar Kontraktionshierarkier för att stödja en blandad fordonsflotta, med snabba uppdateringar av parametrar och stöd för mer detaljerade optimeringsmål. Detta görs genom att implementera Anpassningsbara Kontraktionsierarkier, men med anpassade datastrukturer och anpassningsfas. Denna implementering tillåter att kartdata delas mellan fordonen i en flotta, och håller varje fordons kantvikter separat. Kantvikterna kan uppdateras snabbt, eftersom anpassningsfasen skalas linjärt med storleken på kartan. Implementationen stöder också kantvikter som inte följer triangelojämlikheten, vilket den tidigare forskningen inte gjorde. Experiment utförs på en karta över Stockholm och en syntetisk karta, för att testa algoritmens prestanda, verifiera korrekthet, och betona vikten av detaljerade parametrar i optimeringsmål. Anpassningsbara Kontraktionshierarkier presterade som förväntat, om inte bättre, och dess korrekthet uppehölls. Implementeringen är lämplig för att integreras i en ruttplanerare, men ytterligare forskning bör genomföras för att se hur den passar ihop med andra delar av ruttplaneringsproblemet, så som tidsfönster, svängkostnader och laddstationer.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-333079 |
| Date | January 2023 |
| Creators | Larsson, Martin |
| Publisher | KTH, Skolan för elektroteknik och datavetenskap (EECS), Stockholm : KTH Royal Institute of Technology |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-EECS-EX ; 2023:554 |
Page generated in 0.0029 seconds