A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints. (English) Zbl 1103.90022
Summary: This paper presents a heuristic, which concentrates on solving a large-scale static dial-a-ride problem bearing complex constraints. In this heuristic, a properly organized local search strategy and a diversification strategy are used to improve initial solutions. Then the improved solutions can be refined further by an intensification strategy. The performance of this heuristic was evaluated by intensive computational tests on some randomly generated instances. Small gaps to the lower bounds from the column generation method were obtained in very short time for instances with no more than 200 requests. Although the result is not sensitive to the initial solution, the computational time can be greatly reduced if some effort is spent to construct a good initial solution. With this good initial solution, larger instances up to 2000 requests were solved in less than 10 hours on a popular personal computer.
MSC:
| 90B06 | Transportation, logistics and supply chain management |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Backer, B.; Furnon, V.; Shaw, P.; Kilby, P.; Prosser, P., Solving vehicle routing problem using constraint programming and metaheuristics, Journal of Heuristics, 6, 501-523 (2000) · Zbl 0972.68631 |
| [2] | Bodin, L. D.; Sexton, T., The multi-vehicle subscriber dial-a-ride problem, TIMS Studies in Management Science, 26, 73-86 (1986) |
| [3] | Cordeau, J.F., Laporte G., 2002. The dial-a-ride problem: Variants, modeling issues and algorithms, Technical report ISSN: 0711-2440, Les Cahiers du GERAD, Montréal.; Cordeau, J.F., Laporte G., 2002. The dial-a-ride problem: Variants, modeling issues and algorithms, Technical report ISSN: 0711-2440, Les Cahiers du GERAD, Montréal. |
| [4] | Cordeau, J. F.; Laporte, G., A Tabu search heuristic for the static multi-vehicle dial-a-ride problem, Transportation Research Part B, 37, 579-594 (2003) |
| [5] | Cordone, R.; Wolfler Calvo, R., A heuristic for the vehicle routing problem with time windows, Journal of Heuristics, 7, 107-129 (2001) · Zbl 0994.90036 |
| [6] | Desaulniers, G., Desrosiers, J., Erdmann, A., Solomon, M.M., Soumis, F., 2002. VRP with pickup and delivery. In: Toth, P., Vigo, D. (Eds), The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, pp. 225-242.; Desaulniers, G., Desrosiers, J., Erdmann, A., Solomon, M.M., Soumis, F., 2002. VRP with pickup and delivery. In: Toth, P., Vigo, D. (Eds), The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, pp. 225-242. · Zbl 1076.90544 |
| [7] | Desrosiers, J.; Dumas, Y.; Soumis, F., 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 (1986) · Zbl 0632.90087 |
| [8] | Desrosiers, J., Dumas, Y., Soumis, F., Taillefer, S., Villeneuve, D., 1991. An algorithm for mini-clustering in handicapped transport. Cahier du GERAD G-91-22, Ecole des Hautes Etudes commerciales, Montréal.; Desrosiers, J., Dumas, Y., Soumis, F., Taillefer, S., Villeneuve, D., 1991. An algorithm for mini-clustering in handicapped transport. Cahier du GERAD G-91-22, Ecole des Hautes Etudes commerciales, Montréal. |
| [9] | Dorigo, M., Maniezzo, V., Colorni, A., 1991. The ant system: An autocatalytic optimizing process. Technical report No. 91-016 revised. Politecnico di Milano, Italy.; Dorigo, M., Maniezzo, V., Colorni, A., 1991. The ant system: An autocatalytic optimizing process. Technical report No. 91-016 revised. Politecnico di Milano, Italy. · Zbl 0912.90240 |
| [10] | Dumas, Y., Desrosiers, J., Soumis, F., 1989. Large scale multi-vehicle dial-a-ride problems. Cahier du GERAD G-89-30, Ecole des Hautes Etudes commerciales, Montréal.; Dumas, Y., Desrosiers, J., Soumis, F., 1989. Large scale multi-vehicle dial-a-ride problems. Cahier du GERAD G-89-30, Ecole des Hautes Etudes commerciales, Montréal. · Zbl 0632.90087 |
| [11] | Dumas, Y.; Desrosiers, J.; Soumis, F., The pickup and delivery problem with time windows, European Journal of Operational Research, 54, 7-22 (1991) · Zbl 0736.90028 |
| [12] | Gillett, B.; Miller, L., A heuristic algorithm for the vehicle dispatch problem, Operations Research, 22, 340-349 (1974) · Zbl 0274.90013 |
| [13] | Glover, F.; Laguna, M., Tabu Search (1997), Kluwer: Kluwer Boston · Zbl 0930.90083 |
| [14] | Healy, P.; Moll, R., A new extension of local search applied to the dial-a-ride problem, European Journal of Operational Research, 83, 83-104 (1995) · Zbl 0903.90135 |
| [15] | Holland, J. H., Adaptation in natural and artificial systems (1975), University of Michigan Press: University of Michigan Press Ann Arbor · Zbl 0317.68006 |
| [16] | Hunsaker, B.; Savelsbergh, M., Efficient feasibility testing for dial-a-ride problems, Operations Research Letters, 30, 169-173 (2002) · Zbl 1010.90006 |
| [17] | Ioachim, I.; Desrosiers, J.; Dumas, Y.; Solomon, M. M., A request clustering algorithm for door-to-door handicapped transportation, Transportation Science, 29, 63-78 (1995) · Zbl 0826.90045 |
| [18] | Jaw, J.; Odoni, A. R.; Psaraftis, H. N.; Wilson, N. H.M., A heuristic algorithm for the multi-vehicle advance-request dial-a-ride problem with time windows, Transportation Research B, 20, 243-257 (1986) |
| [19] | Kinderwater, G. A.P.; Savelsbergh, M. W.P., Vehicle routing: Handling edge exchanges, (Aarts, E. H.L.; Lenstra, J. K., Local Search in Combinatorial Optimization (1997), Wiley: Wiley Chichester), 337-360 · Zbl 0887.90060 |
| [20] | Kirckpatrick, S.; Gelatt, C.; Vecchi, M., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162 |
| [21] | Laporte, G.; Gendreau, M.; Potvin, J. Y.; Semet, F., Classical and modern heuristics for the vehicle routing problem, International Transactions in Operational Research, 7, 285-300 (2000) |
| [22] | Lin, S., Computer solutions of the travelling salesman problem, Bell System Technical Journal, 44, 2245-2269 (1965) · Zbl 0136.14705 |
| [23] | Lin, S.; Kernighan, B., An effective heuristic algorithm for the travelling salesman problem, Operations Research, 21, 498-516 (1973) · Zbl 0256.90038 |
| [24] | Or, I., 1976. Travelling salesman-type combinatorial optimization problems and their relation to the logistics of regional blood banking. Ph.D. dissertation, Northwestern University, Evanston, IL.; Or, I., 1976. Travelling salesman-type combinatorial optimization problems and their relation to the logistics of regional blood banking. Ph.D. dissertation, Northwestern University, Evanston, IL. |
| [25] | Nanry, W. P.; Barnes, J. W., Solving the pickup and delivery problem with time windows using reactive tabu search, Transportation Research B, 34, 107-121 (2000) |
| [26] | Psaraftis, H. N., A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem, Transportation Science, 14, 130-154 (1980) |
| [27] | Psaraftis, H. N., An exact algorithm for the single vehicle many-to-many immediate request dial-a-ride problem with time windows, Transportation Science, 17, 351-357 (1983) |
| [28] | Psaraftis, H. N., \(k\)-Interchange procedures for local search in a precedence-constrained routing problem, European Journal of Operational Research, 13, 391-402 (1983) · Zbl 0505.90045 |
| [29] | Roy, S., Rousseau, J.M., Lapalme, G., Ferland, J.A., 1984a. Routing and scheduling for the transportation of disabled persons—the algorithm. Technical Report TP 5596E, Centre de Recherche sur les Transports, Montréal.; Roy, S., Rousseau, J.M., Lapalme, G., Ferland, J.A., 1984a. Routing and scheduling for the transportation of disabled persons—the algorithm. Technical Report TP 5596E, Centre de Recherche sur les Transports, Montréal. |
| [30] | Roy, S., Rousseau, J.M., Lapalme, G., Ferland, J.A., 1984b. Routing and scheduling for the transportation of disabled persons—the tests. Technical Report TP 5598E, Centre de Recherche sur les Transports, Montréal.; Roy, S., Rousseau, J.M., Lapalme, G., Ferland, J.A., 1984b. Routing and scheduling for the transportation of disabled persons—the tests. Technical Report TP 5598E, Centre de Recherche sur les Transports, Montréal. |
| [31] | Savelsbergh, M. W.P., The vehicle routing problem with time windows: Minimizing route duration, ORSA Journal on Computing, 4, 146-154 (1992) · Zbl 0780.90105 |
| [32] | Savelsbergh, M. W.P.; Sol, M., Drive: Dynamic routing of independent vehicles, Operations Research, 46, 474-490 (1998) · Zbl 0987.90511 |
| [33] | Tan, K. C.; Lee, L. H.; Ou, K., Artificial intelligence heuristics in solving vehicle routing problems with time window constraints, Engineering applications of artificial intelligence, 14, 825-837 (2001) |
| [34] | Toth, P.; Vigo, D., Heuristic algorithms for the handicapped persons transportation problem, Transportation Science, 31, 60-71 (1997) · Zbl 0888.90117 |
| [35] | Van Breedam, A., Comparing descent heuristics and metaheuristics for the vehicle routing problem, Computers and Operations Research, 28, 289-315 (2001) · Zbl 0976.90018 |
| [36] | Voudouris, C., Tsang, E., 1995. Guided local search. Technical Report CSM-247, Department of Computer Science, University of Essex, Colchester, UK.; Voudouris, C., Tsang, E., 1995. Guided local search. Technical Report CSM-247, Department of Computer Science, University of Essex, Colchester, UK. · Zbl 0983.90056 |
| [37] | Wilson, H., Sussman, J., Higonnet, B., 1971. Scheduling algorithms for dial-a-ride systems. Technical Report USL TR-70-13, Urban Systems Laboratory, MIT, Boston.; Wilson, H., Sussman, J., Higonnet, B., 1971. Scheduling algorithms for dial-a-ride systems. Technical Report USL TR-70-13, Urban Systems Laboratory, MIT, Boston. |
| [38] | Xu, H.; Chen, Z. L.; Rajagopal, S.; Arunapuram, S., Solving a practical pickup and delivery problem, Transportation Science, 37, 347-367 (2003) |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
