A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. (English) Zbl 1077.90058
Summary: The vehicle routing problem with simultaneous pick-up and delivery (VRP_ SPD) is a variant of the classical vehicle routing problem (VRP) where clients require simultaneous pick-up and delivery service. Deliveries are supplied from a single depot at the beginning of the vehicle’s service, while pick-up loads are taken to the same depot at the conclusion of the service. One important characteristic of this problem is that a vehicle’s load in any given route is a mix of pick-up and delivery loads.
In this paper we develop a tabu search algorithm to solve VRP_ SPD. This algorithm uses three types of movements to obtain inter-route adjacent solutions: the relocation, interchange and crossover movements. A 2-opt procedure is used to obtain alternative intra-route solutions. Four types of neighbourhoods were implemented, three of them defined by the use of each of the single inter-route movements and the fourth by using a combination of these movements. Two different search strategies were implemented for selecting the next movement: first admissible movement and best admissible movement. Intensification and diversification of the search were achieved through frequency penalization. Computational results are reported for a set of 87 test problems with between 50 and 400 clients.
In this paper we develop a tabu search algorithm to solve VRP_ SPD. This algorithm uses three types of movements to obtain inter-route adjacent solutions: the relocation, interchange and crossover movements. A 2-opt procedure is used to obtain alternative intra-route solutions. Four types of neighbourhoods were implemented, three of them defined by the use of each of the single inter-route movements and the fourth by using a combination of these movements. Two different search strategies were implemented for selecting the next movement: first admissible movement and best admissible movement. Intensification and diversification of the search were achieved through frequency penalization. Computational results are reported for a set of 87 test problems with between 50 and 400 clients.
MSC:
| 90C27 | Combinatorial optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Software:
VRPReferences:
| [1] | Min, H., The multiple vehicle routing problem with simultaneous delivery and pickup points, Transportation Research A, 23, 377-386 (1989) |
| [2] | Galvão, R. D.; Guimarães, J., The control of helicopter operations in the Brazilian oil industryissues in the design and implementation of a computerized system, European Journal of Operational Research, 49, 266-270 (1990) |
| [3] | Dethloff, J., Vehicle routing and reverse logisticsthe vehicle routing problem with simultaneous delivery and pick-up, OR Spektrum, 23, 79-96 (2001) · Zbl 1015.90022 |
| [4] | Salhi, S.; Nagy, G., A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling, Journal of the Operational Research Society, 50, 1034-1042 (1999) · Zbl 1054.90523 |
| [5] | Golden BL, Baker E, Alfaro J, Schaffer J. The vehicle routing problem with backhauling: two approaches. Proceedings of the Twenty-First Annual Meeting of the S. E. TIMS, Myrtle Beach, SC, USA, 1985.; Golden BL, Baker E, Alfaro J, Schaffer J. The vehicle routing problem with backhauling: two approaches. Proceedings of the Twenty-First Annual Meeting of the S. E. TIMS, Myrtle Beach, SC, USA, 1985. |
| [6] | Casco, D. O.; Golden, B. L.; Wasil, E. A., Vehicle routing with backhauls, (Golden, B. L.; Assad, A. A., Vehicle routingmethods and studies (1988), North-Holland: North-Holland Amsterdam), 127-147 · Zbl 0638.00043 |
| [7] | Salhi S, Nagy G. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European Journal of Operational Research 2004. Available online at www.sciencedirect.com; Salhi S, Nagy G. Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. European Journal of Operational Research 2004. Available online at www.sciencedirect.com · Zbl 1132.90380 |
| [8] | Tang, F. A.; Galvão, R. D., Vehicle routing problems with simultaneous pick-up and delivery service, Journal of the Operational Research Society of India (OPSEARCH), 39, 19-33 (2002) · Zbl 1278.90419 |
| [9] | Beasley, J. E., Route first-cluster second methods for vehicle routing, Omega, 11, 403-408 (1983) |
| [10] | Gillett, B. E.; Miller, L. R., A heuristic algorithm for the vehicle dispatch problem, Operations Research, 22, 340-349 (1974) · Zbl 0274.90013 |
| [11] | Angelelli E, Mansini R. A branch-and-price algorithm for a simultaneous pick-up and delivery problem. Working Paper, Article presented at the EURO/INFORMS Meeting, 2003.; Angelelli E, Mansini R. A branch-and-price algorithm for a simultaneous pick-up and delivery problem. Working Paper, Article presented at the EURO/INFORMS Meeting, 2003. |
| [12] | Tang, F. A.; Ferreira Filho, V. J.M.; Galvão, R. D., Determinação de rotas para empresas de entrega expressa (“Design of routes for express delivery companies”), Journal of the Brazilian OR Society (Pesquisa Operacional), 17, 107-135 (1997) |
| [13] | Savelsbergh, M. W.P.; Sol, M., The general pickup and delivery problem, Transportation Science, 29, 17-29 (1995) · Zbl 0826.90049 |
| [14] | Psaraftis, H., A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem, Transportation Science, 14, 130-154 (1980) |
| [15] | Psaraftis, H., An exact algorithm for the single vehicle many-to-many dial-a-ride problem with time windows, Transportation Science, 17, 351-360 (1983) |
| [16] | Desrosiers, J.; Dumas, Y.; Soumis, F., A dynamic programing solution of a large scale single vehicle dial-a-ride problem with time windows, American Journal of Mathematics and Management Science, 6, 301-326 (1986) · Zbl 0632.90087 |
| [17] | Psaraftis, H., K-interchange procedures for local search in a precedence-constrained routing problem, European Journal of Operational Research, 13, 391-402 (1983) · Zbl 0505.90045 |
| [18] | Sexton, T.; Bodin, L., Optimizing single vehicle many-to-many operations with desired delivery timesI. Scheduling, Transportation Science, 19, 378-410 (1985) · Zbl 0608.90043 |
| [19] | Sexton, T.; Bodin, L., Optimizing single vehicle many-to-many operations with desired delivery timesII. Routing, Transportation Science, 19, 411-435 (1985) · Zbl 0618.90042 |
| [20] | Sexton, T.; Choi, Y., Pickup and delivery of partial loads with time windows, American Journal of Mathematics and Management Science, 6, 369-398 (1986) · Zbl 0633.90029 |
| [21] | Van der Bruggen, L. J.J.; Lenstra, J. K.; Schuur, P. C., Variable-depth search for the single-vehicle pickup and delivery problem with time windows, Transportation Science, 27, 298-311 (1993) · Zbl 0788.90017 |
| [22] | Madsen O, Ravn H, Rygaard JR. REBUS, A system for dynamic vehicle routing for the Copenhagen Fire Fighting Company. Research Report 2/1993, IMSOR, Lyngby, Denmark, 1993.; Madsen O, Ravn H, Rygaard JR. REBUS, A system for dynamic vehicle routing for the Copenhagen Fire Fighting Company. Research Report 2/1993, IMSOR, Lyngby, Denmark, 1993. |
| [23] | Roy S, Rousseau JM, Lapalme G, Ferland JA. Routing and scheduling for the transportation of disabled persons—the algorithm. Report TP 5596E, Transport Development Center, Montréal, Canada, 1984.; Roy S, Rousseau JM, Lapalme G, Ferland JA. Routing and scheduling for the transportation of disabled persons—the algorithm. Report TP 5596E, Transport Development Center, Montréal, Canada, 1984. |
| [24] | Roy S, Rousseau JM, Lapalme G, Ferland JA. Routing and scheduling for the transportation of disabled persons—the tests. Report TP 5596E, Transport Development Center, Montréal, Canada, 1984.; Roy S, Rousseau JM, Lapalme G, Ferland JA. Routing and scheduling for the transportation of disabled persons—the tests. Report TP 5596E, Transport Development Center, Montréal, Canada, 1984. |
| [25] | Jaw, J. 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) |
| [26] | Desrosiers J, Dumas Y, Soumis F, Taillefer S, Villeneuve D. An algorithm for mini-clustering in handicapped transport. Cahiers du GERARD Report G-91-02, École des Hautes Études Commerciales, Montréal, Canada, 1991.; Desrosiers J, Dumas Y, Soumis F, Taillefer S, Villeneuve D. An algorithm for mini-clustering in handicapped transport. Cahiers du GERARD Report G-91-02, École des Hautes Études Commerciales, Montréal, Canada, 1991. |
| [27] | Ioachim, I.; Desrosiers, J.; Dumas, Y.; Solomon, M. M.; Villeneuve, D., A request clustering algorithm for door-to-door handicapped transportation, Transportation Science, 29, 63-78 (1995) · Zbl 0826.90045 |
| [28] | 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 |
| [29] | Gendreau, M.; Hertz, A.; Laporte, G., The traveling salesman problem with backhauls, Computers and Operations Research, 23, 501-508 (1996) · Zbl 0847.90135 |
| [30] | Deif I, Bodin LD. Extension of the Clarke and Wright algorithm for solving the vehicle routing with backhauling. Proceedings of the Babson Conference on Software Uses in Transportation and Logistics Management, Babson Park, MA, 1984.; Deif I, Bodin LD. Extension of the Clarke and Wright algorithm for solving the vehicle routing with backhauling. Proceedings of the Babson Conference on Software Uses in Transportation and Logistics Management, Babson Park, MA, 1984. |
| [31] | Toth, P.; Vigo, D., An exact algorithm for the vehicle routing problem with backhauls, Transportation Science, 31, 372-385 (1997) · Zbl 0919.90057 |
| [32] | Mingozzi, A.; Giorgi, S., An exact method for the vehicle routing problem with backhauls, Transportation Science, 33, 315-329 (1999) · Zbl 1004.90016 |
| [33] | Gélinas, S.; Desrochers, M.; Desrosiers, J.; Solomon, M. M., A new branching strategy for time constrained routing problems with application to backhauling, Annals of Operations Research, 61, 91-110 (1995) · Zbl 0839.90029 |
| [34] | Duhamel, C.; Potvin, J. Y.; Rousseau, J. M., A tabu search heuristic for the vehicle routing problem with backhauls and time windows, Transportation Science, 31, 49-59 (1997) · Zbl 0888.90053 |
| [35] | Mosheiov, G., The traveling salesman problem with pick-up and delivery, European Journal of Operational Research, 79, 299-310 (1994) · Zbl 0815.90135 |
| [36] | Mosheiov, G., Vehicle routing with pick-up and deliverytour partitioning heuristics, Computers and Industrial Engineering, 34, 669-684 (1998) |
| [37] | Gavish B, Graves S. The travelling salesman problem and related problems. Working Paper 7905, Graduate School of Management, University of Rochester, NY, USA, 1979.; Gavish B, Graves S. The travelling salesman problem and related problems. Working Paper 7905, Graduate School of Management, University of Rochester, NY, USA, 1979. |
| [38] | Anily, S.; Mosheiov, G., The traveling salesman problem with delivery and backhauls, Operations Research Letters, 16, 11-18 (1994) · Zbl 0814.90119 |
| [39] | Gendreau, M.; Laporte, G.; Vigo, D., Heuristics for the traveling salesman problem with pickup and delivery, Computers and Operations Research, 26, 699-714 (1999) · Zbl 0957.90069 |
| [40] | Solomon, M. M., Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research, 35, 254-265 (1987) · Zbl 0625.90047 |
| [41] | Gehring H, Homberger J. A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. In: Miettinen K, Mäkelä M, Toivanen J, editors. Proceedings of EUROGEN99, vol. A2(S), Springer, Berlin, 1999, pp. 57-64.; Gehring H, Homberger J. A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. In: Miettinen K, Mäkelä M, Toivanen J, editors. Proceedings of EUROGEN99, vol. A2(S), Springer, Berlin, 1999, pp. 57-64. |
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.
