El problema Dial–a–Ride y sus variantes
Palabras clave:
Optimización, ruteo de vehículos, DARPResumen
El problema Dial–a–Ride (DARP) consiste en diseñar rutas de vehículos y programar el traslado de usuarios que demandan servicio desde un punto de origen a un destino. Su principal aplicación se encuentra en trasladar personas de la tercera edad o personas con alguna discapacidad. En el problema clásico, un conjunto de clientes realiza una solicitud de servicio, por lo que estos deben ser recogidos en algún punto llamado origen y entregados en algún punto denominado destino. Por lo general los clientes establecen algunos horarios en los que desean ser transportados, por lo que el DARP puede ser definido como una combinación de un problema de ruteo de vehículos (VRP) y un problema de planificación de tareas. En este trabajo se presenta una clasificación actualizada de las variantes del DARP y algunas de las referencias más relevantes que han sido estudiadas en la literatura.
Citas
S. C. Ho, W. Y. Szeto, Y.-H. Kuo, J. M. Y. Leung, M. Petering, and T. W. H. Tou, “A survey of dial-a-ride
problems: Literature review and recent developments,” Transportation Research Part B: Methodological,
vol. 111, pp. 395–421, May. 2018.
P. Oxley, “Dial/a/ride: a review,” Transportation Planning and Technology, vol. 6, no. 3, pp. 141–148, Jan.
K. F. Doerner and J.-J. Salazar-González, “Chapter 7: Pickup-and-Delivery Problems for People
Transportation,” Vehicle Routing, pp. 193–212, Nov. 2014.
Y. Molenbruch, K. Braekers, and A. Caris, “Typology and literature review for dial-a-ride problems,” Annals
of Operations Research, vol. 259, no. 1–2, pp. 295–325, May. 2017.
J.-F. Cordeau and G. Laporte, “The dial-a-ride problem: models and algorithms,” Annals of Operations
Research, vol. 153, no. 1, pp. 29–46, May. 2007.
Y. Dumas, J. Desrosiers, and F. Soumis, “The pickup and delivery problem with time windows,” European
Journal of Operational Research, vol. 54, no. 1, pp. 7–22, Sep. 1991.
S. Gökay, A. Heuvels, and K.-H. Krempels, “A High-level Category Survey of Dial-a-Ride Problems,”
Proceedings of the 5th International Conference on Vehicle Technology and Intelligent Transport Systems,
Z. Zhang, M. Liu, and A. Lim, “A memetic algorithm for the patient transportation problem,” Omega, vol.
, pp. 60–71, Jul. 2015.
H. N. Psaraftis, “A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate
Request Dial-a-Ride Problem,” Transportation Science, vol. 14, no. 2, pp. 130–154, May 1980.
J.-F. Cordeau, “A Branch-and-Cut Algorithm for the Dial-a-Ride Problem,” Operations Research, vol. 54,
no. 3, pp. 573–586, Jun. 2006.
M. Chassaing, G. Fleury, C. Duhamel, and P. Lacomme, “Determination of robust solutions for the DARP
with variations in transportation time,” IFAC-PapersOnLine, vol. 49, no. 12, pp. 943–948, 2016.
H. N. Psaraftis, “An Exact Algorithm for the Single Vehicle Many-to-Many Dial-A-Ride Problem with Time
Windows,” Transportation Science, vol. 17, no. 3, pp. 351–357, Aug. 1983.
M. Maalouf, C. A. MacKenzie, S. Radakrishnan, and M. Court, “A new fuzzy logic approach to capacitated
dynamic Dial-a-Ride problem,” Fuzzy Sets and Systems, vol. 255, pp. 30–40, Nov. 2014.
S. N. Parragh, “Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-
ride problem,” Transportation Research Part C: Emerging Technologies, vol. 19, no. 5, pp. 912–930, Aug.
O. Tellez, S. Vercraene, F. Lehuédé, O. Péton, and T. Monteiro, “The fleet size and mix dial-a-ride problem
with reconfigurable vehicle capacity,” Transportation Research Part C: Emerging Technologies, vol. 91,
pp. 99–123, Jun. 2018.
K. Braekers, A. Caris, and G. K. Janssens, “Exact and meta-heuristic approach for a general
heterogeneous dial-a-ride problem with multiple depots,” Transportation Research Part B: Methodological,
vol. 67, pp. 166–186, Sep. 2014.
R. Masson, F. Lehuédé, and O. Péton, “The Dial-A-Ride Problem with Transfers,” Computers &
Operations Research, vol. 41, pp. 12–23, Jan. 2014.
J. Pierotti and J. Theresia van Essen, “MILP models for the Dial-a-ride problem with transfers,” EURO
Journal on Transportation and Logistics, vol. 10, p. 100037, 2021.
S. N. Parragh, J. Pinho de Sousa, and B. Almada-Lobo, “The Dial-a-Ride Problem with Split Requests
and Profits,” Transportation Science, vol. 49, no. 2, pp. 311–334, May 2015.
M. Liu, Z. Luo, and A. Lim, “A branch-and-cut algorithm for a realistic dial-a-ride problem,” Transportation
Research Part B: Methodological, vol. 81, pp. 267–288, Nov. 2015.
M. A. Masmoudi, M. Hosny, E. Demir, K. N. Genikomsakis, and N. Cheikhrouhou, “The dial-a-ride problem
with electric vehicles and battery swapping stations,” Transportation Research Part E: Logistics and
Transportation Review, vol. 118, pp. 392–420, Oct. 2018.
C. Bongiovanni, M. Kaspi, and N. Geroliminis, “The electric autonomous dial-a-ride problem,”
Transportation Research Part B: Methodological, vol. 122, pp. 436–456, Apr. 2019.
D. O. Santos and E. C. Xavier, “Taxi and Ride Sharing: A Dynamic Dial-a-Ride Problem with Money as
an Incentive,” Expert Systems with Applications, vol. 42, no. 19, pp. 6728–6737, Nov. 2015.
A. Atahran, C. Lenté, and V. T’kindt, “A Multicriteria Dial-a-Ride Problem with an Ecological Measure and
Heterogeneous Vehicles,” Journal of Multi-Criteria Decision Analysis, vol. 21, no. 5–6, pp. 279–298, Mar.
C. H. Häll, H. Andersson, J. T. Lundgren, and P. Värbrand, “The Integrated Dial-a-Ride Problem,” Public
Transport, vol. 1, no. 1, pp. 39–54, Nov. 2008.
O. Tellez, S. Vercraene, F. Lehuédé, O. Péton, and T. Monteiro, “The time-consistent dial-a-ride problem,”
Networks, Jun. 2021.
