zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
A GRASP with evolutionary path relinking for the truck and trailer routing problem. (English) Zbl 1208.90024
Summary: In the truck and trailer routing problem (TTRP) a heterogeneous fleet composed of trucks and trailers has to serve a set of customers, some only accessible by truck and others accessible with a truck pulling a trailer. This problem is solved using a route-first, cluster-second procedure embedded within a hybrid metaheuristic based on a greedy randomized adaptive search procedure (GRASP), a variable neighborhood search (VNS) and a path relinking (PR). We test PR as a post-optimization procedure, as an intensification mechanism, and within evolutionary path relinking (EvPR). Numerical experiments show that all the variants of the proposed GRASP with path relinking outperform all previously published methods. Remarkably, GRASP with EvPR obtains average gaps to best-known solutions of less than 1% and provides several new best solutions.

90B06Transportation, logistics
90C35Programming involving graphs or networks
90C59Approximation methods and heuristics
VRP; Tabu search
Full Text: DOI
[1] Beasley, J. E.: Route-first cluster-second methods for vehicle routing, Omega 11, 403-408 (1983)
[2] Bixby, R.: Solving real-world linear programs: a decade and more of progress, Operations research 50, No. 1, 3-15 (2002) · Zbl 1163.90643 · doi:10.1287/opre.
[3] Boudia, M.; Louly, M.; Prins, C.: A reactive GRASP and path relinking for a combined production-distribution problem, Computers & operations research 34, No. 11, 3402-3419 (2007) · Zbl 1163.90317 · doi:10.1016/j.cor.2006.02.005
[4] Campos, V.; Laguna, M.; Martí, R.: Context-independent scatter and tabu search for permutation problems, INFORMS journal on computing 17, No. 1, 111-122 (2005) · Zbl 1239.90109
[5] 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 · doi:10.1057/jors.2009.59
[6] Caramia, M.; Guerriero, F.: A milk collection problem with incompatibility constraints, Interfaces 40, No. 2, 130-143 (2010)
[7] Chao, I. -M.: A tabu search method for the truck and trailer routing problem, Computers & operations research 29, 33-51 (2002) · Zbl 1026.90102 · doi:10.1016/S0305-0548(00)00056-3
[8] Conover, W.: Practical nonparametric statistics, (1998)
[9] Cordeau, J. -F.; Gendreau, M.; Laporte, G.: A tabu search heuristic for periodic and multi-depot vehicle routing problems, Networks 30, 105-119 (1997) · Zbl 0885.90037 · doi:10.1002/(SICI)1097-0037(199709)30:2<105::AID-NET5>3.0.CO;2-G · http://www3.interscience.wiley.com/cgi-bin/jtoc?ID=32046
[10] Desrosiers, J.; Soumis, F.; Desrochers, M.: Routing with time windows by column generation, Networks 14, No. 4, 545-565 (1984) · Zbl 0571.90088 · doi:10.1002/net.3230140406
[11] Dongarra JJ. Performance of various computers using standard linear equations software. Technical Report CS89-95, University of Tennessee, Computer Science; 2009.
[12] Dongarra JJ, Wade R, McMahan P. Linpack benchmark--Java version. \langlehttp://www.netlib.org/benchmark/linpackjava/ angle; 2010.
[13] Drexl M. On some generalized routing problems. PhD thesis, Faculty of Business and Economics, RWTH Aachen University; 2007. · Zbl 1209.90238
[14] Duhamel, C.; Lacomme, P.; Prins, C.; Prodhon, C.: A GRASP X ELS approach for the capacitated location-routing problem, Computers & operations research 37, No. 11, 1912-1923 (2010) · Zbl 1188.90026 · doi:10.1016/j.cor.2009.07.004
[15] Ehrgott, M.: Multicriteria optimization, (2000) · Zbl 0956.90039
[16] El-Fallahi, A.; Prins, C.; Wolfler-Calvo, R.: A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem, Computers & operations research 35, 1725-1741 (2008) · Zbl 1211.90031 · doi:10.1016/j.cor.2006.10.006
[17] Feo, T. A.; Resende, M. G. C.: Greedy randomized adaptive search procedures, Journal of global optimization 6, No. 2, 109-133 (1995) · Zbl 0822.90110 · doi:10.1007/BF01096763
[18] Flood, M. M.: The traveling-salesman problem, Operations research 4, No. 1, 61-75 (1956)
[19] García, S.; Molina, D.; Lozano, M.; Herrera, F.: A study on the use of non-parametric tests for analyzing the evolutionary algorithms’s behaviour: a case study on the CEC’ 2005 special session on real parameter optimization, Journal of heuristics 15, 617-644 (2009) · Zbl 1191.68828 · doi:10.1007/s10732-008-9080-4
[20] 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, The vehicle routing problem: latest advances and new challenges, 143-170 (2008) · Zbl 1187.90001
[21] Gerdessen, J. C.: Vehicle routing problem with trailers, European journal of operational research 93, 135-147 (1996) · Zbl 0912.90117 · doi:10.1016/0377-2217(95)00175-1
[22] Gillett, B. E.; Miller, L. R.: A heuristic algorithm for the vehicle-dispatch problem, Operations research 22, No. 2, 340-349 (1974) · Zbl 0274.90013 · doi:10.1287/opre.22.2.340
[23] Glover, F.; Laguna, M.: Tabu search, (1997) · Zbl 0930.90083
[24] Golden, B. L.; Raghavan, S.; Wasil, E.: The vehicle routing problem: latest advances and new challenges, (2008) · Zbl 1142.90004
[25] Hansen, P.; Mladenovic, N.: Variable neighbourhood search: principles and applications, European journal of operational research 130, 449-467 (2001) · Zbl 0981.90063 · doi:10.1016/S0377-2217(00)00100-4
[26] Hashimoto H, Yagiura M. A path relinking approach with an adaptive mechanism to control parameters for the vehicle routing problem with time windows. In van Hemert JI, Cotta C, editors, EvoCOP, Lecture notes in computer science, vol. 4972. Springer; 2008. p 254--65.
[27] Ho, S. C.; Gendreau, M.: Path relinking for the vehicle routing problem, Journal of heuristics 12, 55-72 (2006) · Zbl 1122.90068 · doi:10.1007/s10732-006-4192-1
[28] Hoff A, Løkketangen A. A tabu search approach for milk collection in western Norway using trucks and trailers. In TRISTAN VI: The sixth triennial symposium on transportation analysis. Phuket, Tailand; June 10--15, 2007.
[29] Laguna, M.; Marti, R.: GRASP and path relinking for 2-layer straight line crossing minimization, INFORMS journal on computing 11, No. 1, 44-52 (1999) · Zbl 1092.90544 · doi:10.1287/ijoc.11.1.44
[30] Laporte, G.: What you should know about the vehicle routing problem, Naval research logistics 54, 811-819 (2007) · Zbl 1135.90308 · doi:10.1002/nav.20261
[31] Lin, S-W.; Yu, V. F.; Chou, S-Y: A note on the truck and trailer routing problem, Expert systems with applications 37, No. 1, 899-903 (2010)
[32] Lin, S. -W.; Yu, V. F.; Chou, S. -Y.: Solving the truck and trailer routing problem based on a simulated annealing heuristic, Computers & operations research 36, No. 5, 1683-1692 (2009) · Zbl 1177.90079 · doi:10.1016/j.cor.2008.04.005
[33] Or I. Traveling salesman-type combinatorial optimization problems and their relation to the logistics of regional blood banking. PhD thesis, Department of Industrial Engineering and Management Science, Northwestern University, Evanston, IL; 1976.
[34] Parragh, S. N.; Doerner, K. F.; Hartl, R. F.; Gandibleux, X.: A heuristic two-phase solution approach for the multi-objective dial-a-ride problem, Networks 54, No. 4, 227-242 (2009) · Zbl 1204.90096 · doi:10.1002/net.20335
[35] Prins, C.: A simple and effective evolutionary algorithm for the vehicle routing problem, Computers & operations research 31, 1985-2002 (2004) · Zbl 1100.90504 · doi:10.1016/S0305-0548(03)00158-8
[36] Prins, C.: A GRASP X evolutionary local search hybrid for the vehicle routing problem, Bio-inspired algorithms for the vehicle routing problem, 35-53 (2009)
[37] Prins, C.: Two memetic algorithms for heterogeneous fleet vehicle routing problems, Engineering applications of artificial intelligence 22, 916-928 (2009)
[38] Prins, C.; Prodhon, C.; Wolfler-Calvo, R.: Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking, 4OR--A quarterly journal of operations research 4, 221-238 (2006) · Zbl 1125.90316 · doi:10.1007/s10288-006-0001-9
[39] Reghioui, M.; Prins, C.; Labadi, N.: GRASP with path relinking for the capacitated arc routing problem with time windows, Evoworkshops, lecture notes in computer science 4448, 722-731 (2007)
[40] Resende, M. G. C.; Martí, R.; Gallego, M.; Duarte, A.: GRASP and path relinking for the maxmin diversity problem, Computers & operations research 37, No. 3, 498-508 (2010) · Zbl 1173.90521
[41] Resende, M. G. C.; Ribeiro, C. C.: GRASP with path-relinking: recent advances and applications, Metaheuristics: progress as real problem solvers, 29-63 (2005)
[42] Resende MGC, Ribeiro CC. GRASP. AT&T Labs Research Technical Report, 2008.
[43] Resende MGC, Ribeiro CC. Greedy randomized adaptive search procedures: advances and applications. In: Gendreau M, Potvin J-Y, editors, Handbook of metaheuristics, 2nd ed., Springer; 2010, p. 281--317.
[44] Resende, M. G. C.; Werneck, R. F.: A hybrid heuristic for the p-median problem, Journal of heuristics 10, 59-88 (2004) · Zbl 1069.68600 · doi:10.1023/B:HEUR.0000019986.96257.50
[45] Scheuerer, S.: A tabu search heuristic for the truck and trailer routing problem, Computers & operations research 33, 894-909 (2006) · Zbl 1079.90116 · doi:10.1016/j.cor.2004.08.002
[46] Schiavinotto, T.; Stutzle, T.: A review of metrics on permutations for search landscape analysis, Computers & operations research 34, No. 10, 3143-3153 (2007) · Zbl 1185.90115 · doi:10.1016/j.cor.2005.11.022
[47] 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 · doi:10.1007/BF02098281
[48] 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 · doi:10.1007/BF02023006
[49] Sörensen, K.: Distance measures based on the edit distance for permutation-type representations, Journal of heuristics 13, No. 1, 35-47 (2006)
[50] Sörensen, K.; Sevaux, M.: A practical approach for robust and flexible vehicle routing using metaheuristics and Monte Carlo sampling, Journal of mathematical modelling and algorithms 8, No. 4, 387-407 (2009) · Zbl 1180.90059 · doi:10.1007/s10852-009-9113-5
[51] Sörensen K, Sevaux M. Distance-based path relinking for the vehicle routing problem. In: TRISTAN VII: seventh triennial symposium on transportation analysis. Tromsø, Norway, June 20--25, 2010. p. 744--7.
[52] Souffriau, W.; Vansteenwegen, P.; Berghe, G. Vanden; Vanoudheusden, D.: A path relinking approach for the team orienteering problem, Computers & operations research 37, No. 11, 1853-1859 (2010) · Zbl 1188.90221
[53] Toth, P.; Vigo, D.: The vehicle routing problem, (2002) · Zbl 0979.00026 · doi:10.1137/1.9780898718515
[54] 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, No. 5, 780-794 (2010)