The dial-a-ride problem: models and algorithms
Tóm tắt
The Dial-a-Ride Problem (DARP) consists of designing vehicle routes and schedules for n users who specify pickup and delivery requests between origins and destinations. The aim is to plan a set of m minimum cost vehicle routes capable of accommodating as many users as possible, under a set of constraints. The most common example arises in door-to-door transportation for elderly or disabled people. The purpose of this article is to review the scientific literature on the DARP. The main features of the problem are described and a summary of the most important models and algorithms is provided.
Từ khóa
Tài liệu tham khảo
Aldaihani, M., & Dessouky, M. M. (2003). Hybrid scheduling methods for paratransit operations. Computers & Industrial Engineering, 45, 75–96.
Bodin, L. D., & Sexton, T. (1986). The multi-vehicle subscriber dial-a-ride problem. TIMS Studies in Management Science, 2, 73–86.
Borndörfer, R., Klostermeier, F., Grötschel, M., & Küttner, C. (1997). Telebus Berlin: vehicle scheduling in a dial-a-ride system, Technical report SC 97-23, Konrad-Zuse-Zentrum für Informationstechnik, Berlin.
Brotcorne, L., Laporte, G., & Semet, F. (2003). Ambulance location and relocation models. European Journal of Operational Research, 147, 451–468.
Colorni, A., & Righini, G. (2001). Modeling and optimizing dynamic dial-a-ride problems. International Transactions in Operational Research, 8, 155–166.
Cordeau, J.-F. (2006). A Branch-and-cut algorithm for the dial-a-ride problem. Operations Research, 54, 573–586.
Cordeau, J.-F., & Laporte, G. (2003a). A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research B, 37, 579–594.
Cordeau, J.-F., & Laporte, G. (2003b). The dial-a-ride problem (DARP): variants, modeling issues and algorithms. 4OR: A Quarterly Journal of Operations Research, 1, 89–101.
Cordeau, J.-F., Laporte, G., & Mercier, A. (2001). A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52, 928–936.
Cordeau, J.-F., Laporte, G., Potvin, J.-Y., & Savelsbergh, M. W. P. (2007a). Transportation on demand. In C. Barnhart & G. Laporte (Eds.), Transportation. Amsterdam: Elsevier.
Cordeau, J.-F., Laporte, G., Savelsbergh, M. W. P., & Vigo, D. (2007b). Vehicle routing. In C. Barnhart & G. Laporte (Eds.), Transportation. Amsterdam: Elsevier.
Coslovich, L., Pesenti, R., & Ukovich, W. (2006). A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem. European Journal of Operational Research, 175, 1605–1615.
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.
Desrosiers, J., Dumas, Y., Soumis, F., Taillefer, S., & Villeneuve, D. (1991). An algorithm for mini-clustering in handicapped transport. Les Cahiers du GERAD, G-91-02, HEC Montréal.
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. (1989a). Large scale multi-vehicle dial-a-ride problems. Les Cahiers du GERAD, G-89-30, HEC Montréal.
Dumas, Y., Soumis, F., & Desrosiers, J. (1989b). Optimizing the schedule for a fixed vehicle path with convex inconvenience cost. Les Cahiers du GERAD, G-89-08, HEC Montréal.
Fu, L. (2002). Scheduling dial-a-ride paratransit under time-varying, stochastic congestion. Transportation Research B, 36, 485–506.
Gendreau, M., Hertz, A., & Laporte, G. (1994). A tabu search heuristic for the vehicle routing problem. Management Science, 40, 1276–1290.
Gendreau, M., Laporte, G., & Semet, F. (2001). A dynamic model and parallel tabu search algorithm for real-time ambulance relocation. Parallel Computing, 27, 1641–1653.
Hunsaker, B., & Savelsbergh, M. W. P. (2002). Efficient feasibility testing for dial-a-ride problems. Operations Research Letters, 30, 169–173.
Ioachim, I., Desrosiers, J., Dumas, Y., & Solomon, M. M. (1995). A request clustering algorithm for door-to-door handicapped transportation. Transportation Science, 29, 63–78.
Jaw, 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 B, 20, 243–257.
Jørgensen, R. M., Larsen, J., & Bergvinsdottir, K. B. (2007, in press). Solving the dial-a-ride problem using genetic algorithms. Journal of the Operational Research Society.
Madsen, O. B. G., Ravn, H. F., & Rygaard, J. M. (1995). A heuristic algorithm for the a dial-a-ride problem with time windows, multiple capacities, and multiple objectives. Annals of Operations Research, 60, 193–208.
Melachrinoudis, E., Ilhan, A. B., & Min, H. (2007). A dial-a-ride problem for client transportation in a health-care organization. Computers & Operations Research, 34, 742–759.
Mitrović-Minić, S., Krishnamurti, R., & Laporte, G. (2004). Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows. Transportation Research B, 38, 669–685.
Pallottino, P., & Scutellà, M. G. (1998). Shortest path algorithms in transportation models: classical and innovative aspects. In P. Marcotte & S. Nguyen (Eds.), Equilibrium and advanced transportation modelling (pp. 245–281). Boston: Kluwer.
Psaraftis, H. N. (1980). A dynamic programming approach to the single-vehicle, many-to-many immediate request dial-a-ride problem. Transportation Science, 14, 130–154.
Psaraftis, H. N. (1983). An exact algorithm for the single-vehicle many-to-many dial-a-ride problem with time windows. Transportation Science, 17, 351–357.
Psaraftis, H. N. (1988). Dynamic vehicle routing problems. In B. L. Golden & A. A. Assad (Eds.), Vehicle routing: method and studies (pp. 223–248). Amsterdam: North-Holland.
Psaraftis, H. N. (1995). Dynamic vehicle routing: status and prospects. Annals of Operations Research, 61, 143–164.
Rekiek, B., Delchambre, A., & Saleh, H. A. (2006). Handicapped person transportation: an application of the grouping genetic algorithm. Engineering Application of Artificial Intelligence, 19, 511–520.
Ropke, 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.
Savelsbergh, M. W. P. (1992). The vehicle routing problem with time windows: minimizing route duration. ORSA Journal on Computing, 4, 146–154.
Sexton, T. (1979). The single vehicle many-to-many routing and scheduling problem. Ph.D. dissertation, SUNY at Stony Brook.
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. Routing. Transportation Science, 19, 411–435.
Teodorovic, D., & Radivojevic, G. (2000). A fuzzy logic approach to dynamic dial-a-ride problem. Fuzzy Sets and Systems, 116, 23–33.
Toth, P., & Vigo, D. (1996). Fast local search algorithms for the handicapped persons transportation problem. In I. H. Osman & J. P. Kelly (Eds.), Meta-heuristics: theory and applications (pp. 677–690). Boston: Kluwer.
Toth, P., & Vigo, D. (1997). Heuristic algorithms for the handicapped persons transportation problem. Transportation Science, 31, 60–71.
Wolfler Calvo, R., & Colorni, A. (2007). An effective and fast heuristic for the dial-a-ride problem. 4OR: A Quarterly Journal of Operations Research, 5, 61–73.
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.