allowing for bi-directional costs and different vehicle costs. The first model is based on shortest paths transformation and is regarded as a standard model. The second model is called native since it is based on the problem network and therefore is fundamentally different. The main subject of this repot is to introduce the reader to the native model and the technical implications that follows. Mainly it shows empirical evidence (not proof) that there are problems that formulated natively manifest significant- to large gains in computation performance. There is also a problem instance where the standard model takes at least 14 times longer time to compute. This report also attempts estimating the fraction of the possible problems that would have less variables when modeled natively and therefore might be expected to have an advantage in computation time. This fraction appears to be around ⅓ of all problems. / Denna rapport formulerar två modeller för ruttplanering av era fordon över era dagar och möjliggör kostnader för olika riktningar och för olika fordonskostnader. Den första modellen är baserad på transformation till minimalkostnadsvägar och betraktas som en standardmodell. Den andra modellen kallas för nativ eftersom den är baserad på problemets egna nätverk och den är därför fundamentalt annorlunda. Det primära syftet med denna rapport är att introducera läsaren till den nativa modellen och de tekniska konsekvenser som följer. Främst visar empiriska bevis att det finns problem som vinner mycket beräkningsprestanda om de modelleras nativt. Det finns också ett fall av problem där standardmodellen tar minst 14 gånger längre tid att beräkna. Utöver detta försöker denna rapport uppskatta hur stor andel av möjliga problem som skulle ha färre variabler när de modelleras nativt och därför kan förväntas ha bättre beräkningsprestanda. Denna fraktion verkar vara runt ⅓ av alla problem.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-200914 |
| Date | January 2017 |
| Creators | Kleyer, Niklas |
| Publisher | KTH, Optimeringslära och systemteori |
| 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-MAT-E ; 2017:01 |
Page generated in 0.0021 seconds