# 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)
New mathematical models of the generalized vehicle routing problem and extensions. (English) Zbl 1236.90019
Summary: The generalized vehicle routing problem (GVRP) is an extension of the vehicle routing problem (VRP) and was introduced by Ghiani and Improta. The GVRP is the problem of designing optimal delivery or collection routes from a given depot to a number of predefined, mutually exclusive and exhaustive node-sets (clusters) which includes exactly one node from each cluster, subject to capacity restrictions. The aim of this paper is to provide two new models of the GVRP based on integer programming. The first model, called the node formulation is similar to the Kara-Bektaş formulation, but produces a stronger lower bound. The second one, called the flow formulation, is completely new. We show as well that under specific circumstances the proposed models of the GVRP reduces to the well known routing problems. Finally, the GVRP is extended for the case in which the vertices of any cluster of each tour are contiguous. This case is defined as the clustered generalized vehicle routing problem and both of the proposed formulations of GVRP are adapted to clustered case.

##### MSC:
 90B06 Transportation, logistics 90C10 Integer programming
Full Text:
##### References:
 [1] Ghiani, G.; Improta, G.: An efficient transformation of the generalized vehicle routing problem, Eur. J. Oper. res. 122, 11-17 (2000) · Zbl 0968.90010 · doi:10.1016/S0377-2217(99)00073-9 [2] I. Kara, T. Bektaş, Integer linear programming formulation of the generalized vehicle routing problem, in: Proc. of the 5th EURO/INFORMS Joint International Meeting, 2003. [3] Laporte, G.; Osman, I. H.: Routing problems: a bibliography, Ann. oper. Res. 61, 227-262 (1995) · Zbl 0839.90032 · doi:10.1007/BF02098290 [4] Laporte, G.: What you should know about the vehicle routing problem, Naval res. Log. 54, 811-819 (2007) · Zbl 1135.90308 · doi:10.1002/nav.20261 [5] , Handbooks in operations research and management science 8 (1995) [6] Laporte, G.; Nobert, Y.: Generalized traveling salesman through n sets of nodes: an integer programming approach, Infor 21, 61-75 (1983) · Zbl 0524.90069 [7] Noon, C. E.; Bean, J. C.: A Lagrangian based approach for the asymmetric generalized traveling salesman problem, Oper. res. 39, 623-632 (1991) · Zbl 0741.90086 · doi:10.1287/opre.39.4.623 [8] Fischetti, M.; Salazar, J. J.; Toth, P.: The symmetric generalized traveling salesman polytope, Networks 26, 113-123 (1995) · Zbl 0856.90116 · doi:10.1002/net.3230260206 [9] Fischetti, M.; Salazar, J. J.; Toth, P.: A branch-and-cut algorithm for the symmetric generalized traveling salesman problem, Oper. res. 45, 378-394 (1997) · Zbl 0893.90164 · doi:10.1287/opre.45.3.378 [10] Pop, P. C.: New integer programming formulations of the generalized traveling salesman problem, Am. J. Appl. sci. 4, No. 11, 932-937 (2007) [11] P.C. Pop, C.M. Pintea, I. Zelina, D. Dumitrescu, Solving the generalized vehicle routing problem with an ACS-based algorithm, American Institute of Physics (AIP), Conference Proceedings: BICS 2008, vol. 1117, no. 1, 2009, pp. 157 -- 162. [12] P.C. Pop, O. Matei, C. Pop Sitar, C. Chira, A genetic algorithm for solving the generalized vehicle routing problem, in: E.S. Corchado Rodriguez et al. (Ed.) Proc. of HAIS 2010, Part II, Lecture Notes in Artificial Intelligence, vol. 6077, pp. 119 -- 126, 2010. [13] Laporte, G.; Chapleau, S.; Landry, P. E.; Mercure, H.: An algorithm for the design of mail box collection routes in urban areas, Transp. res. B 23, 271-280 (1989) [14] Feillet, D.; Dejax, P.; Gendreau, M.: Traveling salesman problems with profits, Transp. sci. 39, 188-205 (2005) [15] R. Baldacci, E. Bartolini, G. Laporte, Some applications of the Generalized Vehicle Routing Problem, Le Cahiers du GERAD, G-2008-82, 2008. · Zbl 1193.90036 [16] Desrochers, M.; Laporte, G.: Improvements and extensions to the Miller -- Tucker -- zemlin subtour elimination constraints, Oper. res. Lett. 10, 27-36 (1991) · Zbl 0723.90081 · doi:10.1016/0167-6377(91)90083-2 [17] Kara, I.; Laporte, G.; Bektaş, T.: A note on the lifted Miller -- Tucker -- zemlin subtour elimination constraints for the capacitated vehicle routing problem, Eur. J. Oper. res. 158, 793-795 (2004) · Zbl 1061.90020 · doi:10.1016/S0377-2217(03)00377-1 [18] Laporte, G.; Palekar, U.: Some applications of the clustered traveling salesman problem, J. oper. Res. soc. 53, 972-976 (2002) · Zbl 1139.90425 · doi:10.1057/palgrave.jors.2601420 [19] Ding, C.; Cheng, Y.; He, M.: Two-level genetic algorithm for clustered traveling salesman problem with application in large-scale tsps, Tsinghua sci. Technol. 12, No. 4, 459-465 (2007) · Zbl 1174.90863 · doi:10.1016/S1007-0214(07)70068-8 [20] Araque, J. R.; Kudva, G.; Morin, T. L.; Pekny, J. F.: A branch and cut algorithm for vehicle routing problem, Ann. oper. Res. 50, 37-59 (1994) · Zbl 0815.90062 · doi:10.1007/BF02085634 [21] A. Hertz, G. Laporte, M. Mittaz, A tabu search heuristic for the capacitated arc routing problem, Working Paper 96-08, Department de Mathematiques, Ecole Polytechnique Federal de Lausanne, 1996. · Zbl 1106.90384