| dc.description.abstract | Denne oppgaven utforsker dial-a-ride problemet (DARP) til Ruter Aldersvennlig Transport (RAT), en dør til dør transporttjeneste for eldre i Oslo. DARP dreier seg om å designe ruteplaner for transport av passasjerer mellom ulike start- og endelokasjoner. En andel av transportforespørslene er kjent på forhånd, mens andre kommer i løpet av dagen. Problemet er derfor dynamisk. Det kan også oppstå andre uforutsette hendelser, som forsinkelser, kanselleringer og kunder som ikke møter opp. Å bruke optimering til å konstruere og opprettholde effektive ruteplaner ved slike hendelser, er derfor av høy interesse for RAT.
For å få en bredere forståelse av problemet, presenteres en oversikt over tidligere publisert litteratur relatert til emnet. Litteraturen som blir presentert omhandler først og fremst det dynamiske DARP eller håndtering av uforutsette hendelser generelt. Det fremkommer at eksisterende litteratur på det dynamiske DARP først og fremst fokuserer på håndtering av nye transportforespørsler. Andre uforutsette hendelser blir sjeldent diskutert. Vårt bidrag til litteraturen er derfor å modellere og løse et DARP som inkluderer mange ulike typer uforutsette hendelser.
Den foreslåtte løsningsmetoden består av fire hoveddeler: en grådig konstruksjonsheuristikk, en adaptive large neighbourhood search (ALNS) heuristikk, en grådig innsettingsheuristikk og en hendelsesoppdaterer. I tillegg har vi konstruert et realistisk simuleringsrammeverk som genererer de uforutsette hendelsene. Først brukes den grådige konstruksjonsheuristikken til å lage en initiell ruteplan for de forespørslene som har kommet inn før klokken 10:00 samme dag. Så brukes ALNSen til å forbedre ruteplanen. Simulatoren begynnere så å generere hendelser. Ved nye forespørsler prøver den grådige innsettingsheuristikken å raskt legge forespørselen inn i ruteplanen. Andre hendelser håndteres først av hendelsesoppdatereren, som oppdaterer ruteplanen til å inkludere hendelsen. ALNSen brukes så til å forbedre ruteplanen. Løsningsmetoden og simulatoren kjøres iterativt gjennom hele den operasjonelle dagen.
For å best etterligne det virkelige problemet brukes historisk data fra RAT til å generere testinstanser og utvikle simuleringsrammeverket. Gjennom en beregningsstudie blir disse brukt til å skaffe verdifull innsikt om problemet. Resultatene viser at den foreslåtte løsningsmetoden klarer å løse alle testinstanser innen rimelig tid. I tillegg håndterer den effektivt uforutsette hendelser og har en kort responstid til kunden. Sammenlignet med enklere løsningsmetoder klarer heuristikken å håndtere flere transportforespørsler samt å bedre redusere konsekvensen av forsinkelser. Arbeidet kan dermed tjene som grunnlag for videre forskning rundt håndtering av uforutsette hendelser i DARP.
Videre gir oppgaven beslutningstøtte til RAT gjennom å analysere verdien av å implementere ulike strategier. Strategiene omfatter endring av avviste kunders hentetidspunkter, implementering av en bestillingsfrist, endringer i antall busser og innføringen av formiddags- og ettermiddagsskift. Flere av strategiene resulterer i redusert antall avvisninger og mer kostnadseffektive ruter. De bidrar derfor med verdifull innsikt relevant for RAT tjenesten. | |
| dc.description.abstract | This thesis explores the dial-a-ride problem (DARP) faced by Ruter Aldersvennlig Transport (RAT), a door-to-door transportation service for the elderly in Oslo. The DARP concerns the design of vehicle routes and schedules to meet several requests for passenger transportation between specified origins and destinations. A subset of the requests is known beforehand, while others are revealed throughout the day, thus making the problem dynamic. Further, the service may be subject to other disruptions such as delays, cancellations, and no-shows. Therefore, utilising operational research to create and maintain efficient routes in case of unforeseen events is of great interest for RAT.
A literature study is conducted to obtain a broader understanding of existing literature relevant to the thesis. The study mainly focuses on literature regarding the dynamic DARP and disruption management in general. It is revealed that existing literature on the disruptive DARP is somewhat limited, focusing mainly on the arrival of new user requests. Consequently, our contribution is the implementation of disruption management for a wide range of disruption types.
The proposed solution method consists of four main parts: a greedy construction heuristic, an adaptive large neighbourhood search (ALNS) heuristic, a greedy insertion heuristic, and a disruption updater. Additionally, a realistic simulation framework is developed to generate disruptions. Firstly, the greedy construction heuristic creates an initial route plan for the requests that have arrived before the beginning of the operational day. The ALNS is then used to improve the route plan. Next, the simulator starts to generate disruptions. In the case of a new request, the greedy insertion heuristic tries to quickly insert the request into the current route plan. The other disruption types are first handled by the disruption updater, which adapts the current route plan to include the disruption. The ALNS is then used to improve the route plan. The solution method and simulator are run iteratively throughout the operational day.
To best mirror the real-life problem, historical request data provided by RAT has been used to generate test instances and develop the proposed simulation framework. Through a computational study, these are used to provide valuable insights into the problem. Results show that the proposed solution method successfully solves all instances within a reasonable time. Additionally, it handles disruptions in a timely manner, with a fast response time to the customer. The heuristic is also shown to serve more requests and better reduce the impact of delays compared with simpler solvers. The work may thus serve as a basis for further research on the disruptive DARP.
Furthermore, managerial insights are obtained by analysing the value of implementing different policies. Specifically, these policies involve adjusting the pick-up time of rejected requests, implementing an order deadline on new requests, changing the vehicle fleet size, and implementing a morning and afternoon shift. Several of the policies are shown to reduce the rejection rate and provide more cost-effective routes, thus providing RAT with valuable insights relevant to their decision-making. | |
