Taxi placement problem is a problem where a number of available taxi vehicles needs to be placed in an area with the objective of covering as much of the demand population as possible in order to acquire as many customer orders as possible. This study tries to model the taxi placement problem as maximum covering location problem (MCLP) and solve it with the heuristic methods, greedy adding (GA) algorithm and local search. The model implementation and solution methods were formulated with adjustments and key assumptions to fit the core problem of taxi placement problem. The performance of model and solution methods were examined in terms of solution quality and run time. Results found that GA algorithm gave high quality solution with relatively low run time and that local search improved on GA solution by around 1,6% on average but suffered from long run times. The testing concluded that there is potential in modelling the taxi placement problem as a MCLP model but the current implementation has potential problems such as discretization not being fine enough and that it relies on several key assumptions. If the key assumptions were to not hold, the problem becomes more complex and/or adjustments needs to be made to reflect it. / Taxiplaceringsproblemet är ett problem där ett antal tillgängliga taxibilar behöver placeras inom ett område med målet att täcka så mycket som möjligt av efterfrågan och öka antal kundordrar som fås. Denna studie försöker modellera taxiplaceringsproblemet som en maximum covering location problem (MCLP) och lösa det med heuristiska metoderna greedy adding (GA) algoritmen och local search. Implementationen av modell samt lösningsmetoderna formulerades med justeringar och nyckelantaganden för att passa kärnproblemet av taxiplaceringsproblemet. Därefter värderades prestandan av modellen och lösningsmetoderna utifrån lösningskvalitet och körtid. Resultaten visade att GA algoritmen gav hög kvalitet i lösning och hade relativt snabb körtid medan local search förbättrade GA lösningen med cirka 1,6% men hade en lång körtid. Testerna visade att det finns potential i att modellera taxiplaceringsproblemet som ett MCLP modell men den nuvarande implementationen har potentiella problem så som diskretiseringen inte är tillräckligt bra och att modellen är beroende av vissa nyckelantaganden. Om dessa nyckelantaganden inte skulle gälla längre kan problemet bli mer komplext och/eller behöver problemet justeras för att ta hänsyn till det.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-233578 |
| Date | January 2018 |
| Creators | Ma, San-San |
| Publisher | KTH, Optimeringslära och systemteori |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | TRITA-SCI-GRU ; 2018:345 |
Page generated in 0.002 seconds