×

zbMATH — the first resource for mathematics

A hybrid tabu search and constraint programming algorithm for the dynamic dial-a-ride problem. (English) Zbl 1460.90083
Summary: This paper introduces a hybrid algorithm for the dynamic dial-a-ride problem in which service requests arrive in real time. The hybrid algorithm combines an exact constraint programming algorithm and a tabu search heuristic. An important component of the tabu search heuristic consists of three scheduling procedures that are executed sequentially. Experiments show that the constraint programming algorithm is sometimes able to accept or reject incoming requests, and that the hybrid method outperforms each of the two algorithms when they are executed alone.

MSC:
90B35 Deterministic scheduling theory in operations research
90B06 Transportation, logistics and supply chain management
90C59 Approximation methods and heuristics in mathematical programming
Software:
Tabu search; TSPTW
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Attanasio A., Cordeau J.-F., Ghiani G., Laporte G.Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem. Parallel Comput. (2004) 30(3):377-387CrossRef
[2] Beaudry A., Laporte G., Melo T., Nickel S.Dynamic transportation of patients in hospitals. OR Spectrum (2010) 32(1):77-107CrossRef · Zbl 1181.90173
[3] Berbeglia G., Cordeau J.-F., Laporte G.Dynamic pickup and delivery problems. Eur. J. Oper. Res. (2010a) 202(1):8-15CrossRef · Zbl 1176.90048
[4] Berbeglia G., Pesant G., Rousseau L.-M.Checking the feasibility of dial-a-ride instances using constraint programming. Transportation Sci. (2010b) . ePub ahead of print September 24, http://dx.doi.org/10.1287/trsc.1100.0336
[5] Borndörfer R., Klostermeier F., Grötschel M., Küttner C.Telebus Berlin: Vehicle scheduling in a dial-a-ride system. (1997) . Technical Report SC 97-23, Konrad-Zuse-Zentrum fur Informationstechnik, Berlin
[6] Cordeau J.-F.A branch-and-cut algorithm for the dial-a-ride problem. Oper. Res. (2006) 54(3):573-586Link · Zbl 1167.90681
[7] Cordeau J.-F., Laporte G.A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Res. Part B (2003) 37(6):579-594CrossRef
[8] Cordeau J.-F., Laporte G.The dial-a-ride problem: Models and algorithms. Ann. Oper. Res. (2007) 153(1):29-46CrossRef · Zbl 1157.90353
[9] Cordeau J.-F., Laporte G., Mercier A.A unified tabu search heuristic for vehicle routing problems with time windows. J. Oper. Res. Soc. (2001) 52(8):928-936CrossRef · Zbl 1181.90034
[10] Coslovich L., Pesenti R., Ukovich W.A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem. Eur. J. Oper. Res. (2006) 175(3):1605-1615CrossRef · Zbl 1142.90323
[11] Desrosiers J., Dumas Y., Soumis F.A dynamic programming solution of the large-scale single-vehicle dial-a-ride problem with time windows. Amer. J. Math. Management Sci. (1986) 6(3-4):301-325CrossRef · Zbl 0632.90087
[12] Focacci F., Lodi A., Milano M.A hybrid exact algorithm for the TSPTW. INFORMS J. Comput. (2002) 14(4):403-417Link · Zbl 1238.90054
[13] Gendreau M., Hertz A., Laporte G.A tabu search heuristic for the vehicle routing problem. Management Sci. (1994) 40(10):1276-1290Link · Zbl 0822.90053
[14] Glover F., Laguna M.Tabu Search (1997) (Kluwer Academic Publishers, Boston) CrossRef · Zbl 0930.90083
[15] Hoogeveen J. A., Vestjens A. P. A., Cunningham W. H., McCormick S. T., Queyranne M.Optimal on-line algorithms for single-machine scheduling. Conf. Integer Programming Combin. Optim., Vol. 1084 (1996) (Springer-Verlag, Berlin) 404-414Lecture Notes in Computer Science
[16] Horn M. E. T.Fleet scheduling and dispatching for demand-responsive passenger services. Transportation Res. Part C (2002) 10(1):35-63CrossRef
[17] Madsen O. B. G., Ravn H. F., Rygaard J. M.A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives. Ann. Oper. Res. (1995) 60(1):193-208CrossRef · Zbl 0839.90033
[18] Mitrović-Minić S., Laporte G.Waiting strategies for the dynamic pickup and delivery problem with time windows. Transportation Res. Part B (2004) 38(7):635-655CrossRef
[19] Psaraftis H. N.A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem. Transportation Sci. (1980) 14(2):130-154Link
[20] Rekiek B., Delchambre A., Saleh H. A.Handicapped person transportation: An application of the grouping genetic algorithm. Engrg. Appl. Artificial Intelligence (2006) 19(5):511-520CrossRef
[21] Ropke S., Cordeau J.-F., Laporte G.Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks (2007) 49(4):258-272CrossRef · Zbl 1141.90340
[22] Spivey M. Z., Powell W. B.The dynamic assignment problem. Transportation Sci. (2004) 38(4):399-419Link
[23] Toth P., Vigo D., Osman I. H., Kelly J. P.Fast local search algorithms for the handicapped persons transportation problem. Meta-Heuristics Theory and Applications (1996) (Kluwer Academic Publishers, Boston) 677-690CrossRef · Zbl 0877.90035
[24] Van Hentenryck P.Constraint Satisfaction in Logic Programming (1989) (MIT Press, Cambridge, MA)
[25] van Hoeve W.-J., Katriel I., Rossi F., Van Beek P., Walsh T.Global constraints. Handbook of Constraint Programming (2006) (Elsevier, Amsterdam) 169-208CrossRef
[26] Xiang Z., Chu C., Chen H.The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments. Eur. J. Oper. Res. (2008) 185(4):534-551 · Zbl 1137.90339
[27] Yuen C. W., Wong K. I., Han A. F.Waiting strategies for the dynamic dial-a-ride problem. Internat. J. Environment Sustainable Dev. (2009) 8(3-4):314-329
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.