zbMATH — the first resource for mathematics

Examples
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.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
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)
Solving the truck and trailer routing problem based on a simulated annealing heuristic. (English) Zbl 1177.90079
Summary: We consider the application of a simulated annealing (SA) heuristic to the truck and trailer routing problem (TTRP), a variant of the vehicle routing problem (VRP). In the TTRP, some customers can be serviced by either a complete vehicle (that is, a truck pulling a trailer) or a single truck, while others can only be serviced by a single truck for various reasons. SA has seen widespread applications to various combinatorial optimization problems, including the VRP. However, to our best knowledge, it has not been applied to the TTRP. So far, all the best known results for benchmark TTRP instances were obtained using tabu search (TS). We applied SA to the TTRP and obtained 17 best solutions to the 21 benchmark TTRP benchmark problems, including 11 new best solutions. Moreover, the computational time required by the proposed SA heuristic is less than those reported in prior studies. The results suggest that SA is competitive with TS on solving the TTRP.

MSC:
90B20Traffic problems
90C59Approximation methods and heuristics
Software:
VRP
WorldCat.org
Full Text: DOI
References:
[1] Dantzig, G. B.; Ramser, J. H.: The truck dispatching problem, Management science 6, 80-91 (1959) · Zbl 0995.90560 · doi:10.1287/mnsc.6.1.80
[2] Gillett, B.; Miller, L.: 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
[3] Bodin, L.; Golden, B. L.; Assad, A.; Ball, M. O.: Routing and scheduling of vehicles and crews: the state of the art, Computers and operations research 10, 62-212 (1983)
[4] Laporte, G.; Nobert, Y.: Exact algorithms for the vehicle routing problem, Surveys in combinatorial optimization 31, 147-184 (1987) · Zbl 0611.90055
[5] , Vehicle routing: methods and studies (1988) · Zbl 0638.00043
[6] Laporte, G.: The vehicle routing problem: an overview of exact and approximate algorithms, European journal of operational research 59, 345-358 (1992) · Zbl 0761.90034 · doi:10.1016/0377-2217(92)90192-C
[7] Van Breedam, A.: Improvement heuristics for the vehicle routing problem based on simulated annealing, European journal of operational research 86, 480-490 (1995) · Zbl 0914.90107 · doi:10.1016/0377-2217(94)00064-J
[8] Laporte, G.; Gendreau, M.; Potvin, J. Y.; Semet, F.: Classical and modern heuristics for the vehicle routing problem, International transactions in operational research 7, No. 4 -- 5, 285-300 (2000)
[9] Toth, P.; Vigo, D.: The vehicle routing problem, (2002) · Zbl 0979.00026 · doi:10.1137/1.9780898718515
[10] Gerdessen, J. C.: Vehicle routing problem with trailers, European journal of operational research 93, No. 1, 135-147 (1996) · Zbl 0912.90117 · doi:10.1016/0377-2217(95)00175-1
[11] 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
[12] Hoff A. Heuristics for Rich Vehicle Routing Problems. Ph.D. Thesis. Molde University College, 2006.
[13] Filipec M, Skrlec D, Krajcar S. An efficient implementation of genetic algorithms for constrained vehicle routing problem. IEEE International Conference on Systems, Man, and Cybernetics, October 11 -- 14, 1998, San Diego, CA, USA:2231-2236.
[14] Chin AJ, Kit HW, Lim A. A new GA approach for the vehicle routing problem. 11th IEEE International Conference on Tools with Artificial Intelligence, November 8 -- 10, 1999, Chicago, Illinois, USA:307-311.
[15] Cordeau, J. F.; Gendreau, M.; Laporte, G.; Potvin, J. Y.; Semet, F.: A guide to vehicle routing heuristics, Journal of the operational research society 53, No. 5, 512-522 (2002) · Zbl 1099.90506 · doi:10.1057/palgrave/jors/2601319
[16] Baker, B. M.; Ayechew, M. A.: A genetic algorithm for the vehicle routing problem, Computers and operations research 30, 787-800 (2003) · Zbl 1026.90013 · doi:10.1016/S0305-0548(02)00051-5
[17] Mazzeo, S.; Loiseau, I.: An ant colony algorithm for the capacitated vehicle routing, Electronic notes in discrete mathematics 18, 181-186 (2004) · Zbl 1075.90568 · http://www.sciencedirect.com/science/journal/15710653
[18] Chao, I. M.: A tabu search method for the truck and trailer routing problem, Computers and operations research 29, No. 1, 33-51 (2002) · Zbl 1026.90102 · doi:10.1016/S0305-0548(00)00056-3
[19] Scheuerer, S.: A tabu search heuristic for the truck and trailer routing problem, Computers and operations research 33, 894-909 (2006) · Zbl 1079.90116 · doi:10.1016/j.cor.2004.08.002
[20] Scheuerer S. Neue Tabusuche-Heuristiken für die logistische Tourenplanung bei restringierendem Anhängereinsatz, mehreren Depots und Planungsperioden. Ph.D. Thesis. School of Business, University of Regensburg, Germany; 2004 [in German]. \langle http://www.opus-bayern.de/uni-regensburg/volltexte/2004/376/\rangle .
[21] 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
[22] Drexl M. A branch-and-price algorithm for the truck-and-trailer routing problem. Technical report. RWTH Aachen University, Germany; 2007. \langle http://www.dpor.rwth-aachen.de/de/publikationen/pdf/or_2006-06.pdf\rangle .
[23] Drexl M. On Some Generalized Routing Problems. Ph.D. Thesis. RWTH Aachen University, Germany; 2007. \langle http://darwin.bth.rwth-aachen.de/opus3/volltexte/2007/2091/pdf/Drexl_Michael.pdf\rangle . · Zbl 1209.90238
[24] Fisher, M. L.; Jaikumar, R.: Generalized assignment heuristic for vehicle routing, Networks 11, No. 2, 109-124 (1981)
[25] Gendreau, M.; Hertz, A.; Laporte, G.: Tabu search heuristic for the vehicle routing problem, Management science 40, No. 10, 1276-1290 (1994) · Zbl 0822.90053 · doi:10.1287/mnsc.40.10.1276
[26] Bodin, L.; Levy, L.: Scheduling of local delivery carrier routes for the united states postal service, Arc routing: theory, solutions, and applications, 419-442 (2000) · Zbl 0982.90009
[27] Nag, B.; Golden, B. L.; Assad, A.: Vehicle routing with site dependencies, Vehicle routing: methods and studies. Studies in management science and systems 16, 149-159 (1988)
[28] Rochat, Y.; Semet, F.: A tabu search approach for delivering pet food and flour in Switzerland, Journal of operational research society 45, No. 11, 1233-1246 (1994) · Zbl 0812.90044
[29] Chao, I. M.; Golden, B. L.; Wasil, E. A.: A new algorithm for the site-dependent vehicle routing problem, Advances in computational and stochastic optimization, logic programming, and heuristic search, 301-312 (1998) · Zbl 0898.68034
[30] Chao, I. M.; Golden, B. L.; Wasil, E. A.: A computational study of a new heuristic for the site-dependent vehicle routing problem, Information systems and operational research 37, No. 3, 319-336 (1999)
[31] Drexl M. The Vehicle Routing Problem with Trailers and Transshipments. Odysseus 2006, Third International Workshop on Freight Transportation and Logistics, May 23 -- 26, 2006, Altea, Spain.
[32] Abramson, D.: Constructing school timetables using simulated annealing: sequential and parallel algorithms, Management science 37, 98-113 (1991)
[33] Chwif, L.; Barretto, M. R. P.; Moscato, L. A.: A solution to the facility layout problem using simulated annealing, Computers in industry 36, 125-132 (1998)
[34] Jayaraman, V.; Ross, A.: A simulated annealing methodology to distribution network design and management, European journal of operational research 144, 629-645 (2003) · Zbl 1012.90531 · doi:10.1016/S0377-2217(02)00153-4
[35] Lim, A.; Rodrigues, B.; Zhang, X.: A simulated annealing and Hill-climbing algorithm for the traveling tournament problem, European journal of operational research 174, 1459-1478 (2006) · Zbl 1103.90042 · doi:10.1016/j.ejor.2005.02.065
[36] Jr., A. R. Mckendall; Shan, J.; Kuppusamy, S.: Simulated annealing heuristics for the dynamic facility layout problem, Computers and operations research 33, 2431-2444 (2006) · Zbl 1086.90037 · doi:10.1016/j.cor.2005.02.021
[37] Lin, S. W.; Chou, S. Y.; Chen, S. C.: Meta-heuristic approaches for minimizing total earliness and tardiness penalties of single-machine scheduling with a common due date, Journal of heuristics 13, 151-165 (2007)
[38] Kim, K. H.; Moon, K. C.: Berth scheduling by simulated annealing, Transportation research part B 37, 542-560 (2003)
[39] Jr., T. J. Candalino; Kobza, J. E.; Jacobson, S. H.: Designing optimal aviation baggage screening strategies using simulated annealing, Computers and operations research 31, 1753-1767 (2004) · Zbl 1073.90577 · doi:10.1016/S0305-0548(03)00118-7
[40] Lee, D. H.; Cao, Z.; Meng, Q.: Scheduling of two-transtainer systems for loading outbound containers in port container terminals with simulated annealing algorithm, International journal of production economics 107, 115-124 (2007)
[41] Metropolis, N.; Rosenbluth, A. W.; Rosenbluth, M. N.; Teller, A. H.; Teller, E.: Equations of state calculations by fast computing machines, Journal of chemical physics 21, 1087-1092 (1953)
[42] Kirkpatrick, S.; Jr., C. D. Gelatt; Vecchi, M. P.: Optimization by simulated annealing, Science 220, 671-680 (1983) · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[43] Christofides, N.; Mingozzi, A.; Toth, P.: The vehicle routing problem, Combinatorial optimization, 315-338 (1979) · Zbl 0413.90075