El problema Dial–a–Ride y sus variantes
Keywords:
Optimization, vehicle routing problem, dial-a-ride problemAbstract
Dial-a-Ride problem (DARP) consists of designing vehicle routes and schedules for users who demand service from a point of origin to a destination. The principal application is transferring the elderly or people with disabilities. In the classic problem, a set of customers makes a request for service, so these must be collected at some point called the origin and delivered at a different point called the destination. Customers usually set some schedules in which they want to be transported, so DARP can be defined as a combination of a vehicle routing problem (VRP) and a scheduling problem. This paper presents an updated classification of DARP variants and some of the most relevant references that have been studied in the literature.
References
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.
