The vehicle routing problem is an old and well-studied problem that arise in last mile logistics. The rapid increase of e-commerce, in particular with an increasing the demand for time scheduled home deliveries on the customer’s terms, is making the problem ever more relevant. By minimizing the cost and environmental impact, we have the setting for mathematical problem called the vehicle routing problem with time windows. Since the problem is NP-Hard, heuristic methods are often used. In practice, they work very well and typically offer a good tradeoff between speed and quality. However, since the heuristics are often tailormade to fit the needs of the underlying problem, no known algorithm dominates the other on all problems. One way to overcome the need for specialization is to produce heuristics that are adaptive. In this thesis, an offline learning method is proposed to generate an adaptive heuristic using local search heuristics and reinforcement learning. The reinforcement learning agents explored in this thesis are situated in both discrete and continuous state representations. Common to all state spaces are that they are inspired by human-crafted reference models where the last action and the result of that action define the state. Four different reinforcement learning models are evaluated in the various environments. By evaluating the models on a subset of the Solomon benchmark instances, we find that all models but one improve upon a random baseline. The average learner from each of the successful models was slightly worse than the human crafted baseline. However, the best among the generated models was an actor-critic based model which outperformed the best human baseline model. Due to the scalar objective function, the results are not directly comparable to the Solomon benchmark results with hierarchal objectives. None the less, the results are encouraging as a proof of principle with results in line with the human crafted baseline. The results indicate two clear paths for further work. First, applying the formulation to more complex environments with more actions and more powerful state spaces. Secondly, investigate models based on stochastic policies and recurrent neural networks to cope with the inherently partially observed environment. / Ruttoptimering är ett gammalt och välstuderat optimeringsproblem som uppstår i city-nära logistik. Med en ständigt växande e-handel, ökar efterfrågan av tidspassade hemleveranser på kundens villkor. Att minimera kostnaden och miljöpåverkan blir då ett ruttoptimeringsproblem med tidsfönster. Då optimerinsproblemet är NP-Svårt, används heuristiska lösningsmetoder. I denna uppsatts undersöks möjligheten att generera heuristiker genom att träna på liknande problem. Mer specifikt genererar vi en heurisitik baserad på lokalsök genom att formulera lärningsproblemet som ett reinforcement learning problem. De metoder som används är baserade på både diskreta och kontinuerliga tillståndsrum. Gemensamt för tillståndsrummen är att de är inspirerade av den information som används av mänskligt genererade heuristiker där det tidigare valet valet och dess resultat är informationsbärare. Fyra olika reinforcement learning modeller utvärderas på olika problem samt tillståndsrymnder. Genom att träna modellerna på olika typer av problem från de välkända Solomon problemen och utvärdera dessa på ett oberoende test set, kan vi konstatera att alla utom en modell är bättre än slumpen. Ingen av modellerna slog dock den bästa referensmodellen i medeltal då variationen i utfallet var stort, men de är alla mycket nära. Den bästa bland alla modeller, vilket var en actor critic agent, uppnådde ett bättre resultat än den bästa referensmodellen. På grund av att en skalär målfunktion använts är resultaten inte direkt jämförbara med andras på Solomon problemen då de skall optimeras med en hierarkisk målfunktion. Trotts detta är resultaten goda och visar att metoden som introducerats fungerar bra eftersom de presterar i linje med referensmodellerna baserade på samma information. Resultaten pekar på två vägar framåt för vidare arbete. Det första är en mera kraftfull tillståndsrymd med mera information samt fler handlingsmöjligheter. Det andra är att applicera stokastiska baserade modeller eller motsvarande för att överkomma tillståndsrymndernas inneboende ofullständighet.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-224428 |
| Date | January 2018 |
| Creators | Ödling, David |
| 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:039 |
Page generated in 0.0022 seconds