Het effect van gebruikersflexibiliteit bij dial-a-ride diensten

Yves
Molenbruch

DIAL-A-RIDE DIENSTEN:  ONDERWEG NAAR MOBILITEIT OP MAAT

Tijdens de voorbije decennia hebben diverse demografische en maatschappelijke evoluties, zoals de vergrijzing van de bevolking en de ontwikkeling van dagopvangsystemen voor gehandicapten, de nood aan vervoer op maat van personen met een beperkte mobiliteit doen toenemen. Omdat zij doorgaans moeilijk gebruik kunnen maken van het gewone openbaar vervoer, leek het voor steeds meer vervoeraanbieders interessant om een zogenaamd dial-a-ride systeem op te zetten. Hierbij vraagt de klant een verplaatsing aan tussen twee locaties naar keuze, met daaraan gekoppeld een aantal kwaliteitsvoorwaarden. De aanbieder verzamelt al deze aanvragen en tracht vervolgens de routes van zijn voertuigen, die eventueel gelijktijdig meerdere passagiers aan boord kunnen hebben, zodanig uit te tekenen dat al deze verzoeken worden ingewilligd. Naarmate het aantal klanten toeneemt, wordt dit echter een steeds moeilijkere opdracht. Enerzijds moet de routeplanning immers correct en efficiënt zijn, opdat de aanbieder een zo beperkt mogelijke werkingskost oploopt, maar anderzijds dient het resultaat snel berekend en geactualiseerd te kunnen worden om een vlotte service te garanderen. Dit probleem leidde gaandeweg tot de ontwikkeling van verschillende wiskundige oplossingsmethoden.

Een adequate benadering

Een dergelijke oplossingsmethode is slechts bruikbaar indien de kenmerken van een reëel systeem er in voldoende mate in geïntegreerd zijn. Een klant die vooraf reserveert, wenst bijvoorbeeld een richttijdstip te formuleren waarop zijn vertrek of zijn aankomst dient plaats te vinden. De methode moet dan in staat zijn een planning af te leveren waarin deze voorwaarde met een bepaalde striktheid gerespecteerd wordt. En dit is nog maar één voorbeeld van de complexe kwaliteitseisen die de werkelijkheid kenmerken. Nog talloze andere beperkingen kunnen relevant zijn: een maximale reistijd voor de klant, de mogelijkheid om rolstoelgebruikers te vervoeren, het respecteren van rij- en rusttijden van de bestuurder, enzovoort. Daar komen dan ook nog eens de kenmerken bij die inherent zijn aan het probleem. Zo dienen het vertrek- en eindpunt van elke klant bijvoorbeeld in dezelfde route en in de juiste volgorde aangedaan te worden en mag de voertuigcapaciteit nooit overschreden worden. Al deze voorwaarden worden omgezet in mathematische beperkingen.

Rekening houdend hiermee, tracht de oplossingmethode een routeplanning uit te werken waarin een bepaalde doelstelling op efficiënte wijze wordt nagestreefd. Deze doelstelling omvat minstens het minimaliseren van de werkingskost voor de aanbieder. In praktijksituaties is het in de eerste plaats belangrijk om snel een goed en correct resultaat te bekomen. Dit hoeft daarom niet noodzakelijk de optimale oplossing te zijn. Exacte oplossingsmethoden zijn doorgaans te complex om dienst te doen in een reële context, omdat de uitvoering ervan bijzonder veel rekentijd kan vergen. Aanbieders maken dan ook veelal gebruik van zogenaamde heuristische methoden. Dergelijke methoden benaderen het probleem op een intuïtief logische, maar eenvoudigere wijze en kunnen dikwijls tot een routeplanning komen die zeer dicht bij het optimale resultaat aanleunt.

De keuze van de aanbieder

Bij het toepassen van een oplossingsmethode wordt de aanbieder geconfronteerd met een fundamenteel dilemma tussen het kwalitatieve en het economische aspect van de dienstverlening. Enerzijds wenst hij een behoorlijke service te bieden door de tijdswensen van de klant te respecteren. Dit houdt in dat de afwijking van het door de klant opgegeven richttijdstip gelimiteerd wordt. Hetzelfde geldt voor de duur van de omweg waarmee de klant onderweg geconfronteerd mag worden. Anderzijds is het zo dat een minder strikte afbakening van deze kwaliteitsparameters leidt tot een lagere werkingskost. De aanbieder zal dus de operationele voordelen van een versoepeling in de kwaliteitsparameters dienen af te wegen tegen de bijkomende ongemakken voor de klant.

De gegenereerde besparing bij iedere bijkomende verlaging van het kwaliteitsniveau wordt geleidelijk kleiner. Op basis van het hierbij vastgestelde patroon is het daarom vanuit operationeel standpunt mogelijk om een gefundeerde kwaliteitskeuze te maken. Deze beslissing kan verschillen naargelang de concrete omstandigheden, bijvoorbeeld omdat de mogelijkheid om aanvragen te combineren niet altijd even groot is. Zo blijkt dat grote aanbieders procentueel een grotere besparing kunnen realiseren dan hun kleinere concurrenten, alsook dat er een groter potentieel is tijdens drukbeklante dagdelen.

De invloed van het kwaliteitsniveau op de tevredenheid en het gedrag van de klant valt moeilijker concreet te becijferen en dient in verder onderzoek zeker nog uitgediept te worden. Wel blijkt het economisch zinvol om de kwaliteitsparameters niet voor elke klant gelijk te veronderstellen, maar twee categorieën te creëren op basis van het verplaatsingsdoel. Klanten op weg naar een doktersafspraak hechten bijvoorbeeld meer belang aan het strikt respecteren van hun richttijdstip dan klanten die op familiebezoek gaan. Bij het plannen van de routes voor klanten in de tweede categorie kan de aanbieder dus een besparing in de werkingskost realiseren zonder veel bijkomend ongemak te veroorzaken.

Bestemming nog niet bereikt

Toch is de weg naar een klantvriendelijke en efficiënte organisatie van dial-a-ride systemen nog lang. In een ideaal scenario zouden reservaties bijvoorbeeld verwerkt worden door een centrale coördinatiedienst, die de aanvragen van alle klanten ontvangt en optimaal verdeelt onder de verschillende aanbieders. Momenteel moet de klant echter nog zelf op zoek naar een aanbieder die zijn aanvraag kan inwilligen en werken deze aanbieders in een geïsoleerde context, hetgeen de globale kost onnodig hoog maakt. Ook met betrekking tot de routeconstructies kan nog vooruitgang geboekt worden. Tot op heden focuste onderzoek voornamelijk op statische oplossingsmethoden. Dit betekent dat de routes definitief zijn vastgelegd op het moment dat de voertuigen hun depot verlaten. Een dergelijk gebrek aan flexibiliteit strookt uiteraard niet met de eisen van de hedendaagse samenleving. Het zou bijvoorbeeld mogelijk moeten zijn om nieuwe vervoeraanvragen of vertragingen als gevolg van allerhande verkeersinvloeden in real time te verwerken. Alleen zo kunnen dial-a-ride systemen uitgroeien tot een efficiënt en eenvoudig aan te wenden vervoeralternatief.

Bibliografie

  • Ascheuer, N., Fischetti, M., & Grötschel, M. (2000). A Branch and Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints. Computational Optimization and Applications, 17, 61-84.
  • Augerat, P., Belenguer, J.M., Benavent, F., Corberán, A., & Naddef, D. (1999). Separating Capacity Inequalities in the CVRP Using Tabu Search. European Journal of Operations Research, 106, 546-557.
  • Balas, E., Fischetti, M., & Pullyblank, W.R. (1995). The Precedence Constrained Asymmetric Traveling Salesman Problem. Mathematical Programming, 68, 241-265.
  • Baugh, J., John, W.K., Reddy, G.K., & Stone, J.R. (1998). Intractability of the Dial-a-Ride Problem and a Multiobjective Solution Using Simulated Annealing. Engineering Optimization, 30, 91-123.
  • Benders, J.F. (1962). Partitioning Procedure for Solving Mixed Variables Programming Problems. Numerische Mathematik, 4, 238-252.
  • Bergvinsdottir, K.B., Larsen, J., & Jorgensen, R.M. (2004). Solving the Dial-a-Ride Problem Using Genetic Algorithms. Opgevraagd op 9 juli, 2012, via http://orbit.dtu.dk/services/downloadRegister/2891780/imm3395.ps
  • Braekers, K., Caris, A., & Janssens, G.K. (2012). Integrated Planning of Loaded and Empty Container Movements. OR Spectrum, 35, 457-478.
  • Calvo, R.W., & Colorni, A. (2006). An Effective and Fast Heuristic for the Dial-a-Ride Problem. 4OR, 5, 61-73.
  • Carraghan, R., & Pardalos, P.M. (1990). An Exact Algorithm for the Maximum Clique Problem. Operations Research Letters, 9, 375-382.
  • Cordeau, J.F., & Laporte, G. (2003a). The Dial-a-Ride Problem (DARP): Variants, Modeling Issues and Algorithms. 4OR, 1, 89-101.
  • Cordeau, J.F., & Laporte, G. (2003b). A Tabu Search Heuristic for the Static Multi-Vehicle Dial-a-Ride Problem. Transportations Research Part B, 37, 597-594.
  • Cordeau, J.F. (2006). A Branch-and-Cut Algorithm for the Dial-a-Ride Problem. Operations Research, 54(3), 573-586.
  • Cordeau, J.F., & Laporte, G. (2007). The Dial-a-Ride Problem: Models and Algorithms. Annals of Operations Research, 153, 29-46.
  • Cormen, T.H., Leiserson, C.E., & Rivest, R.L. (1990). Introduction to Algorithms. Cambridge: The PIT Press.
  • Desrochers, J., & Laporte, G. (1991). Improvements and Extensions to the Miller-Tucker-Zemlin Subtour Elimination Constraints. Operations Research Letters, 10(1), 27-36.
  • Desrosiers, J., Dumas Y., & Soumis, F. (1986). A Dynamic Programming Solution of the Large-Scale Single-Vehicle Dial-a-Ride Problem with Time Windows. American Journal of Mathematical and Management Sciences, 6, 301-325.
  • De Vocht, A. (2009). Basishandboek SPSS 17. Utrecht: Bijleveld Press.
  • Diana, M., & Dessouky, M.M. (2004). A New Regret Insertion Heuristic for Solving Large-Scale Dial-a-Ride Problems with Time Windows. Transportation Research Part B, 38, 539-557.
  • Dumas, Y., Desrosiers, J., & Soumis, F. (1991). The Pickup and Delivery Problem with Time Windows. European Journal of Operational Research, 54, 7-22.
  • Fu, L. (2002). Scheduling Dial-a-Ride Paratransit under Time-Varying, Stochastic Congestion. Transportation Research Part B, 36, 485-506.
  • Gillett, B.E., & Miller, L.R. (1974). A Heuristic Algorithm for the Vehicle Dispatch Problem. Operations Research, 22(2), 340-349.
  • Glover, F.W. (1989). Tabu Search: Part I. ORSA Journal on Computing, 1(3), 190-206.
  • Glover, F.W. (1990). Tabu Search: Part II. ORSA Journal on Computing, 2(1), 4-32.
  • Glover, F.W. (1995). Tabu Thresholding: Improved Search Trajectories by Non-Monotonic Search Trajectories. ORSA Journal on Computing, 7, 426-442.
  • Glover, F.W. (1996). Ejection Chains, Reference Structures and Alternating Path Methods for Traveling Salesman Problems. Discrete Applied Mathematics, 65, 223-253.
  • Grötschel, M., & Padberg, M.W. (1985). Polyhedral Theory. In Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., & Shmoyns, D.B. (Eds.), The Traveling Salesman Problem, 251-305. New York: Wiley.
  • Häme, L. (2010). An Adaptive Insertion Algorithm for the Single-Vehicle Dial-a-Ride Problem with Narrow Time Windows. European Journal of Operational Research, 209, 11-22.
  • Healy, P., & Moll, R. (1995). A New Extension of Local Search Applied to the Dial-a-Ride Problem. European Journal of Operations Research, 83, 83-104.
  • Hillier, F.S., & Lieberman G.J. (2010). Introduction to Operations Research, Ninth Edition. New York: McGraw-Hill Companies, Inc.
  • Ioachim, I, Desrosiers, J., Dumas, Y., Solomon, M.M., & Villeneuve, D. (1995). A Request-Clustering Algorithm for Door-to-Door Handicapped Transportation. Transportation Science, 29(1), 63-78.
  • Jaw, J.J., Odoni, A.R., Psaraftis, H.N., & Wilson, N.H.M. (1986). A Heuristic Algorithm for the Multi-Vehicle Advance-Request Dial-a-Ride Problem with Time Windows. Transportation Research Part B, 20, 243-257.
  • Kirkpatrick, S., Gelatt, C.D., & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, 220, 671-680.
  • Kontoravdis, G., & Bard, J.F. (1995). A GRASP for the Vehicle Routing Problem with Time Windows. ORSA Journal on Computing, 7, 10-23.
  • Lasdon, L. (1970). Optimization Theory for Large Systems. New York: MacMillen.
  • Luo, Y., & Schonfeld, P. (2007). A Rejected-Reinsertion Heuristic for the Static Dial-a-Ride Problem. Transportation Research Part B, 41, 736-755.
  • Mauri, G.R., & Lorena, L.A.N. (2006). A Multiobjective Model and Simulated Annealing Approach for a Dial-a-Ride Problem. Opgevraagd op 9 juli, 2012, via
    http://mtc-m18.sid.inpe.br/col/sid.inpe.br/ePrint@80/2006/10.09.16.10/d…
  • Melachrinoudis, E., Ilhan, A.B., & Min, H. (2007). A Dial-a-Ride Problem for Client Transportation in Health-Care Organisations. Computers & Operations Research, 34, 742-759.
  • Minder Mobielen Centrales (z.d.). Opgevraagd op 4 april, 2012 via http://www.mindermobielencentrale.be/nl/node/17
  • Mladenovic, N., & Hansen, P. (1997). Variable Neighborhood Search. Computers & Operations Research, 24, 1097-1100.
  • Naddef, D., & Rinaldi, G. (2002). Branch-and-Cut Algorithms for the Capacitated VRP. In Toth, P., & Vigo, D. (Eds.), The Vehicle Routing Problem, 53-84. Philadelphia: Society for Industrial and Applied Economics.
  • Ontwerp van Beheersovereenkomst, afgesloten tussen de Vlaamse Regering en de VVM (2003). Vlaams Parlement. Opgevraagd op 4 april, 2012, via http://docs.vlaamsparlement.be/docs/stukken/2002-2003/g1706-1.pdf
  • Papadimitriou, C.H. (1977). The Euclidian Travelling Salesman Problem Is NP-Complete. Theoretical Computational Science, 4, 237-244.
  • Parragh, S.N., Doerner, K.F., & Hartl, R.F. (2008). A Survey on Pickup and Delivery Problems, Part II: Transportation between Pickup and Delivery Locations. Journal für Betriebswirtschaft, 58, 81-117.
  • Parragh, S.N., Doerner, K.F., & Hartl, R.F. (2010). Variable Neighborhood Search for the Dial-a-Ride Problem. Computers & Operations Research, 37, 1129-1138.
  • Psaraftis, H.N. (1980). A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem. Transportation Science, 14, 2, 131-154.
  • Psaraftis, H.N. (1983). Technical Note: an Exact Algorithm for the Single Vehicle Many-to-Many Dial-a-Ride Problem with Time Windows. Transportation Science, 17, 3, 351-357.
  • Raedts, M., & Masui, C. (2007). Van Vraag tot Tekst: Praktische Leidraad voor Literatuurverslagen. Leuven: Acco.
  • Rekiek, B., Delchambre, A., & Saleh, H.A. (2006). Handicapped Person Transportation: An Application of the Grouping Genetic Algorithm. Engineering Applications of Artificial Intelligence, 19, 511-520.
  • Røpke, S., Cordeau, J.F., & Laporte, G. (2007). Models and Branch-and-Cut Algorithms for Pickup and Delivery Problems with Time Windows. Networks, 49, 258-272.
  • Rose, K. (1998). Deterministic Annealing for Clustering, Compression, Classification, Regression and Related Optimization Problems. Proceedings of the IEEE, 86(11), 2210-2239.
  • Ruland, K.S. (1995). Polyhedral Solution to the Pickup and Delivery Problem, Ph.D. Thesis. Saint-Louis: Sever Institute of Technology, Washington University.
  • Ruland, K.S., & Rodin, E.Y. (1997). The Pickup and Delivery Problem: Faces and Branch-and-Cut Algorithm. Computer and Mathematics with Applications, 33, 1-13.
  • Sexton, T., & Bodin, L.D. (1985a). Optimizing Single Vehicle Many-to-Many Operations with Desired Delivery Times: I. Scheduling. Transportation Science, 19, 378-410.
  • Sexton, T., & Bodin, L.D. (1985b). Optimizing Single Vehicle Many-to-Many Operations with Desired Delivery Times: II. Scheduling. Transportation Science, 19, 411-435.
  • Stein, D.M. (1978). Scheduling Dial-a-Ride Transportation Systems. Transportation Science, 12, 3, 232-249.
  • Toth, P., & Vigo, D. (1997). Heuristic Algorithms for the Handicapped Persons Transportation Problem. Transportation Science, 31, 60-71.
  • Van Breedam, A. (2001). Comparing Descent Heuristics and Metaheuristics for the Vehicle Routing Problem. Computers & Operations Research, 28, 289-315.
  • Wong, K.I., & Bell, M.G.H. (2006). Solution of the Dial-a-Ride Problem with Multi-Dimensional Capacity Constraints. International Transactions in Operational Research, 13, 195-208.
  • Xiang, Z., Chu, C., & Chen, H. (2006). A Fast Heuristic for Solving a Large-Scale Static Dial-a-Ride Problem under Complex Constraints. European Journal of Operational Research, 174, 1117-1139.

 

Universiteit of Hogeschool
Universiteit Hasselt
Thesis jaar
2013