Fast route planning for a standard car is well explored, lots of research, and many algorithms exist. For trucks or other heavy vehicles, the available research and quick algorithm alternatives dwindle. This thesis focuses on available alternatives for trucks and other vehicles with attributes hindering them from traversing parts of the road network. Attributes like height are one among many, which can hinder a vehicle on its path. These attributes can vary greatly and is the reason why known solutions can’t be applied. Many well-known solutions rely partially on precalculated data regarding the shortest path for its performance. Precalculating for all possible combinations of attributes is not practical due to the number of possible configurations and the amount of computing needed for each one. The implemented solution is derived from multiple existing solutions and was evaluated on a graph representing Sweden’s road network. The solution is sufficiently fast to allow commercial use and allows changes to the road network with nightly updates. The solution is based on trying to predict which roads are more important when searching for the shortest path. With this knowledge, a search for the shortest path can be said to prioritize the before mentioned roads, which results in it finding its goal faster. / Snabb ruttplanering för en vanlig personbil är välutforskat med mycket tillgänglig forskning och många existerande algoritmer. För lastbilar och andra tunga fordon minskar den tillgängliga forskningen och alternativa algoritmer kraftigt. Den här avhandlingen fokuserar på alternativen som existerar för lastbilar, samt andra fordon som har egenskaper vilket blockerar dem från att framföras på delar av vägnätverket. Höjd är ett attribut bland flera som kan hindra ett fordon från att ta sig fram. Dessa egenskaper kan variera kraftigt och är orsaken till varför kända lösningar inte går att applicera. Många välkända lösningar förlitar sig på förberäknad data gällande snabbaste möjliga väg för sin prestanda. Att utföra dessa beräkningar för alla möjliga kombinationer av egenskaper är opraktiskt på grund av antalet möjliga konfigurationer och hur mycket som måste räknas ut för varje. Den implementerade lösningen är en kombination av flera existerande lösningar och utvärderades på en graf som representerar det svenska vägnätet. Lösningen är snabb nog för att tillåta bruk inom det kommersiella och den tillåter förändringar i vägnätet med nattliga uppdateringar. Lösningen bygger på att försöka förutsäga vilka vägar i ett vägnät som är viktigare än andra när det gäller att finna den snabbaste vägen. Med hjälp av det kan man sedan styra en sökning så att den prioriterar dessa vägar och därmed hitta sitt mål fortare.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:uu-411686 |
| Date | January 2020 |
| Creators | Söderberg, Fredrik |
| Publisher | Uppsala universitet, Institutionen för informationsteknologi |
| 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 | UPTEC IT, 1401-5749 ; 20006 |
Page generated in 0.0021 seconds