×

A matheuristic for the truck and trailer routing problem. (English) Zbl 1317.90057

Summary: In the truck and trailer routing problems (TTRPs) a fleet of trucks and trailers serves a set of customers. Some customers with accessibility constraints must be served just by truck, while others can be served either by truck or by a complete vehicle (a truck pulling a trailer). We propose a simple, yet effective, two-phase matheuristic that uses the routes of the local optima of a hybrid \(\mathrm{GRASP}\times\mathrm{ILS}\) as columns in a set-partitioning formulation of the TTRP. Using this matheuristic we solved both the classical TTRP with fixed fleet and the new variant with unlimited fleet. This matheuristic outperforms state-of-the-art methods both in terms of solution quality and computing time. While the best variant of the matheuristic found new best-known solutions for several test instances from the literature, the fastest variant of the matheuristic achieved results of comparable quality to those of all previous method from the literature with an average speed-up of at least 2.5.

MSC:

90B06 Transportation, logistics and supply chain management
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alvarenga, G.; Mateus, G. R.; Detomi, G., A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows, Computers and Operations Research, 34, 6, 1561-1584 (2007) · Zbl 1163.90357
[2] Arbex Valle, C.; Conegundes Martinez, L.; Salles da Cunha, A.; Mateus, G. R., Heuristic and exact algorithms for a min-max selective vehicle routing problem, Computers and Operations Research, 38, 7, 1054-1065 (2011) · Zbl 1205.90059
[3] Archetti, C.; Speranza, M. G.; Savelsbergh, M. W.P., An optimization-based heuristic for the split delivery vehicle routing problem, Transportation Science, 42, 1, 22-31 (2008)
[4] Baldacci, R.; Mingozzi, A.; Roberti, R., Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints, European Journal of Operational Research, 218, 1, 1-6 (2012) · Zbl 1244.90001
[5] Ball, M. O., Heuristics based on mathematical programming, Surveys in Operations Research and Management Science, 16, 1, 21-38 (2011)
[6] Beasley, J. E., Route-first cluster-second methods for vehicle routing, Omega, 11, 403-408 (1983)
[8] Bodin, L.; Mingozzi, A.; Baldacci, R.; Ball, M., The rollon-rolloff vehicle routing problem, Transportation Science, 34, 3, 271-288 (2000) · Zbl 1004.90017
[9] Bräysy, O.; Gendreau, M., Vehicle routing problem with time windows, Part I: route construction and local search algorithms, Transportation Science, 39, 1, 104-118 (2005)
[10] Caramia, M.; Guerriero, F., A heuristic approach for the truck and trailer routing problem, Journal of the Operational Research Society, 61, 1168-1180 (2010) · Zbl 1193.90037
[11] Caramia, M.; Guerriero, F., A milk collection problem with incompatibility constraints, Interfaces, 40, 2, 130-143 (2010)
[12] Chao, I.-M., A tabu search method for the truck and trailer routing problem, Computers and Operations Research, 29, 33-51 (2002) · Zbl 1026.90102
[13] Christofides, N.; Mingozzi, A.; Toth, P., The vehicle routing problem, (Christofides, N.; Mingozzi, A.; Toth, P.; Sandi, C., Combinatorial Optimization (1979), Wiley), 315-338
[14] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., Introduction to Algorithms (2001), The MIT Press: The MIT Press Cambridge · Zbl 1047.68161
[15] Del Pia, A.; Filippi, C., A variable neighborhood descent algorithm for a real waste collection problem with mobile depots, International Transactions in Operational Research, 13, 2, 125-141 (2006) · Zbl 1127.90391
[16] Derigs, U.; Pullmann, M.; Vogel, U., Truck and trailer routing - problems, heuristics and computational experience, Computers and Operations Research, 40, 2, 536-546 (2013) · Zbl 1349.90083
[21] Drexl, M., Branch-and-price and heuristic column generation for the generalized truck-and-trailer routing problem, Journal of Quantitative Methods for Economics and Business Administration, 12, 5-38 (2011)
[22] Drexl, M., Applications of the vehicle routing problem with trailers and transshipments, European Journal of Operational Research, 227, 2, 275-283 (2012)
[23] Feillet, D., A tutorial on column generation and branch-and-price for vehicle routing problems, 4OR-Quarterly Journal of Operations Research, 8, 4, 407-424 (2010) · Zbl 1208.90016
[24] Festa, P.; Resende, M. G.C., GRASP: basic components and enhancements, Telecommunication Systems, 46, 3, 253-271 (2010)
[25] Festa, P.; Resende, M. G.C., Hybrid GRASP heuristics, (Abraham, A.; Hassanien, A.-E.; Siarry, P.; Engelbrecht, A., Foundations of Computational Intelligence, vol. 3 (2010), Springer), 75-100
[26] Gendreau, M.; Potvin, J.-Y.; Bräysy, O.; Hasle, G.; Løkketangen, A., Metaheuristics for the vehicle routing problem and its extensions: a categorized bibliography, (Golden, B.; Raghavan, S.; Wasil, E., The Vehicle Routing Problem: Latest Advances and New Challenges (2008), Springer), 143-170 · Zbl 1187.90001
[27] Gerdessen, J. C., Vehicle routing problem with trailers, European Journal of Operational Research, 93, 135-147 (1996) · Zbl 0912.90117
[28] Gonzalez-Feliu, J., Two-echelon freight transport optimisation: unifying concepts via a systematic review, Working Papers on Operations Management, 2, 1, 18-30 (2011)
[29] Groër, C.; Golden, B.; Wasil, E., A library of local search heuristics for the vehicle routing problem, Mathematical Programming Computation, 2, 2, 79-101 (2010) · Zbl 1230.90033
[30] Hansen, P.; Mladenovic, N., Variable neighbourhood search: principles and applications, European Journal of Operational Research, 130, 449-467 (2001) · Zbl 0981.90063
[33] Jourdan, L.; Basseur, M.; Talbi, E.-G., Hybridizing exact methods and metaheuristics: a taxonomy, European Journal of Operational Research, 199, 3, 620-629 (2009) · Zbl 1176.90499
[34] Kelly, J. P.; Xu, J., A set-partitioning-based heuristic for the vehicle routing problem, INFORMS Journal on Computing, 11, 2, 161-172 (1999) · Zbl 1092.90503
[35] Laporte, G.; Semet, F., Classical heuristics for the capacitated VRP, (Toth, P.; Vigo, D., The Vehicle Routing Problem (2002), SIAM), 109-128 · Zbl 1076.90549
[36] Levy, L.; Bodin, L., Scheduling of local delivery carriers for the United States Postal Service, (Dror, M., Arc Routing: Theory, Solutions and Applications (2000), Kluwer), 419-442 · Zbl 0982.90009
[37] Lin, C., A vehicle routing problem with pickup and delivery time windows, and coordination of transportable resources, Computers and Operations Research, 38, 11, 1596-1609 (2011) · Zbl 1210.90024
[38] Lin, S.-W.; Yu, V. F.; Chou, S.-Y., Solving the truck and trailer routing problem based on a simulated annealing heuristic, Computers and Operations Research, 36, 5, 1683-1692 (2009) · Zbl 1177.90079
[39] Lin, S.-W.; Yu, V. F.; Chou, S.-Y., A note on the truck and trailer routing problem, Expert Systems with Applications, 37, 1, 899-903 (2010)
[40] Lin, S.-W.; Yu, V. F.; Lu, C.-C., A simulated annealing heuristic for the truck and trailer routing problem with time windows, Expert Systems with Applications, 38, 12, 15244-15252 (2011)
[41] Lourenço, H.; Martin, O.; Stützle, T., Iterated local search, (Glover, F.; Kochenberger, G., Handbook of Metaheuristics (2003), Kluwer), 321-353 · Zbl 1116.90412
[42] Mendoza, J. E.; Villegas, J. G., A multi-space sampling heuristic for the vehicle routing problem with stochastic demands, Optimization Letters (2012)
[43] Parragh, S. N.; Cordeau, J.-F.; Doerner, K. F.; Hartl, R. F., Models and algorithms for the heterogeneous dial-a-ride problem with driver-related constraints, OR Spectrum, 34, 3, 593-633 (2012) · Zbl 1244.90147
[44] Pillac, V.; Guéret, C.; Medaglia, A. L., A parallel matheuristic for the technician routing and scheduling problem, Optimization Letters (2012) · Zbl 1280.90013
[46] Pirkwieser, S.; Raidl, G. R., Multiple variable neighborhood search enriched with ILP techniques for the periodic vehicle routing problem with time windows, (Blesa, M.; Blum, C.; Di Gaspero, L.; Roli, A.; Sampels, M.; Schaerf, A., Hybrid Metaheuristics. Hybrid Metaheuristics, Lecture Notes in Computer Science, vol. 5818 (2009), Springer: Springer Berlin/Heidelberg), 45-59
[47] Pirkwieser, S.; Raidl, G. R., Variable neighborhood search coupled with ILP-based very large neighborhood searches for the (periodic) location-routing problem, (Blesa, M.; Blum, C.; Raidl, G.; Roli, A.; Sampels, M., Hybrid Metaheuristics. Hybrid Metaheuristics, Lecture Notes in Computer Science, vol. 6373 (2010), Springer: Springer Berlin/Heidelberg), 174-189
[48] Prins, C., A GRASP×evolutionary local search hybrid for the vehicle routing problem, (Pereira, F. B.; Tavares, J., Bio-inspired Algorithms for the Vehicle Routing Problem (2009), Springer), 35-53
[49] Pureza, V.; Morabito, R.; Reimann, M., Vehicle routing with multiple deliverymen: modeling and heuristic approaches for the VRPTW, European Journal of Operational Research, 218, 3, 636-647 (2012) · Zbl 1244.90047
[50] Resende, M. G.C., Metaheuristic hybridization with greedy randomized adaptive search procedures, (Chen, Z.-L.; Raghavan, S., TutORials in Operations Research (2008), INFORMS), 295-319
[51] Resende, M. G.C.; Ribeiro, C. C., Greedy randomized adaptive search procedures: Advances and applications, (Gendreau, M.; Potvin, J.-Y., Handbook of Metaheuristics (2010), Springer), 281-317
[52] Resende, M. G.C.; Ribeiro, C. C.; Glover, F.; Martí, R., Scatter search and path-relinking: fundamentals, advances, and applications, (Gendreau, M.; Potvin, J. Y., Handbook of Metaheuristics (2010), Springer), 87-107
[53] Rochat, Y.; Taillard, E., Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics, 1, 1, 147-167 (1995) · Zbl 0857.90032
[54] Santos, L.; Martins, S.; Plastino, A., Applications of the DMGRASP heuristic: a survey, International Transactions in Operational Research, 15, 4, 387-416 (2008) · Zbl 1157.90015
[56] Scheuerer, S., A tabu search heuristic for the truck and trailer routing problem, Computers and Operations Research, 33, 894-909 (2006) · Zbl 1079.90116
[57] Semet, F., A two-phase algorithm for the partial accessibility constrained vehicle routing problem, Annals of Operations Research, 61, 45-65 (1995) · Zbl 0845.90045
[58] Semet, F.; Taillard, E., Solving real-life vehicle routing problems efficiently using tabu search, Annals of Operations Research, 41, 469-488 (1993) · Zbl 0775.90156
[59] Subramanian, A.; Vaz Penna, P. H.; Uchoa, E.; Ochi, L. S., A Hybrid algorithm for the heterogeneous fleet vehicle routing problem, European Journal of Operational Research, 221, 2, 285-295 (2012) · Zbl 1253.90054
[60] Subramanian, A.; Uchoa, E.; Ochi, L. S., A hybrid algorithm for a class of vehicle routing problems, Computers and Operations Research (2013) · Zbl 1348.90132
[61] Taillard, E., A heuristic column generation method for the heterogeneous fleet, VRP. RAIRO, 33, 1, 1-14 (1999) · Zbl 0992.90008
[62] Tan, K.; Chew, Y.; Lee, L., A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems, European Journal of Operational Research, 172, 3, 855-885 (2006) · Zbl 1111.90021
[65] Villegas, J. G.; Prins, C.; Prodhon, C.; Medaglia, A. L.; Velasco, N., GRASP/VND and multi-start evolutionary local search for the single truck and trailer routing problem with satellite depots, Engineering Applications of Artificial Intelligence, 23, 5, 780-794 (2010)
[67] Villegas, J. G.; Prins, C.; Prodhon, C.; Medaglia, A. L.; Velasco, N., A GRASP with evolutionary path relinking for the truck and trailer routing problem, Computers and Operations Research, 38, 9, 1319-1334 (2011) · Zbl 1208.90024
[69] Villegas, J. G., Vehicle routing problems with trailers -Ph.D. Thesis Abstract, 4-OR - A Quarterly Journal of Operations Research, 10, 3, 317-318 (2012)
[71] Yu, V. F.; Lin, T.; Lu, C. C., An ant colony system for solving the truck and trailer routing problem, Journal of the Chinese Institute of Transportation, 23, 2, 199-218 (2011), (in Chinese)
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.