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)
Exact hybrid algorithms for solving a bi-objective vehicle routing problem. (English) Zbl 1245.90010
Summary: The paper investigates a capacitated vehicle routing problem with two objectives: (1) minimization of total travel cost and (2) minimization of the length of the longest route. We present algorithmic variants for the exact determination of the Pareto-optimal solutions of this bi-objective problem. Our approach is based on the adaptive ε-constraint method. For solving the resulting single-objective subproblems, we apply a branch-and-cut technique, using (among others) a novel implementation of Held-Karp-type bounds. Incumbent solutions are generated by means of a single-objective genetic algorithm and, alternatively, by the multi-objective NSGA-II algorithm. Experimental results for a benchmark of 54 test instances from the TSPLIB are reported.
MSC:
90B06Transportation, logistics
90C27Combinatorial optimization
90C29Multi-objective programming; goal programming
90B10Network models, deterministic (optimization)
90C57Polyhedral combinatorics, branch-and-bound, branch-and-cut
Software:
VRP
References:
[1]Achuthan NR, Caccetta L, Hill SP (1996) A new subtour elimination constraint for the vehicle routing problem. Eur J Oper Res 91: 573–586 · Zbl 0924.90057 · doi:10.1016/0377-2217(94)00332-7
[2]Ascheuer N, Fischetti M, Grötschl M (2000) A polyhedral study of the asymmetric traveling salesman problem with time windows. Networks 36(2): 69–79 · doi:10.1002/1097-0037(200009)36:2<69::AID-NET1>3.0.CO;2-Q
[3]Ascheuer N, Fischetti M, Grötschl M (2001) Solving the asymmetric travelling salesman problem with time windows by branch-and-cut. Math Program 90: 475–506 · doi:10.1007/PL00011432
[4]Augerat P, Belenguer JM, Benavant E, Corberán A, Naddef D (1999) Seperating capacity inequalities in the CVRP using tabu search. Eur J Oper Res 106: 546–557 · Zbl 0991.90028 · doi:10.1016/S0377-2217(97)00290-7
[5]Baldacci R, Hadjiconstantinou E, Mingozzi A (2004) An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Oper Res 52(5): 723–738 · Zbl 1165.90353 · doi:10.1287/opre.1040.0111
[6]Bektas T (2006) The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34(3): 209–219 · doi:10.1016/j.omega.2004.10.004
[7]Bérubé J-F, Gendreau M, Potvin J-Y (2009) An exact ϵ-constraint method for bi-objective combinatorial problems: application to the traveling salesman problem with profits. Eur J Oper Res 194: 39–50 · Zbl 1179.90274 · doi:10.1016/j.ejor.2007.12.014
[8]Chu F, Labadi N, Prins C (2006) A scatter search for the periodic capacitated arc routing problem. Eur J Oper Res 169(2): 586–605 · Zbl 1079.90028 · doi:10.1016/j.ejor.2004.08.017
[9]Deb K, Goel T (2001) Controlled elitist non-dominated sorting genetic algorithms for better convergence. In: First international conference on evolutionary multi-criterion optimization (EMO-2001)
[10]Deb K, Jain S (2002) Running performance metrics for evolutionary multi-objective optimization. KanGAL Report, 2002004
[11]Deb K, Pratap A, Meyarivan T (2000a) Constrained test problems for multi-objective evolutionary optimization. In: First international conference on evolutionary multi-criterion optimization, Springer, pp 284–298
[12]Deb K, Pratap A, Agarwal S, Meyarivan T (2000) A fast elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6: 182–197 · doi:10.1109/4235.996017
[13]Fukasawa R, Longo H, Lysegaard J, Poggide Aragao M, Reis M, Uchoa E, Werneck R (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math Program 106(3): 491–511 · Zbl 1094.90050 · doi:10.1007/s10107-005-0644-x
[14]Haimes Y, Lasdon L, Wismer D (1971) On a bicriterion formulation of the problems of integrated system identification and system optimization. IEEE Trans Syst Man Cybern 1: 296–297 · Zbl 0224.93016 · doi:10.1109/TSMC.1971.4308298
[15]Held M, Karp RM (1970) The traveling salesman problem and minimum spanning trees. Oper Res 18: 1135–1162
[16]Jozefowiez N, Semet F, Talbi EG (2002) Parallel and hybrid models for multi-objective optimization: application to the vehicle routing problem. In: Guervos J (eds) Parallel problem solving from nature–PPSN VII, LNCS. Springer, Granada
[17]Jozefowiez N, Semet F, Talbi EG (2006) Enhancements of NSGA-II and its application to the vehicle routing problem with route balancing. In: Talbi E (eds) Proceedings of the 7th international conference artificial evolution-EA 2005, number 3871 in LNCS, Springer, pp 131–142
[18]Jozefowiez N, Semet F, Talbi EG (2008) Multi-objective vehicle routing problems. Eur J Oper Res 189(2): 293–309 · Zbl 1148.90338 · doi:10.1016/j.ejor.2007.05.055
[19]Laporte G, Desrochers M, Nobert Y (1984) Two exact algorithms for the distance constrained vehicle routing problem. Networks 14: 161–172 · Zbl 0538.90093 · doi:10.1002/net.3230140113
[20]Laporte G, Mercure H, Nobert Y (1986) An exact algorithm for the asymmetrical capacitated vehicle routing problem. Networks 16
[21]Laumanns M, Thiele L, Zitzler E (2006) An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method. Eur J Oper Res 169(3)
[22]Lysgaard J (2003) CVRPSEP: A package of seperations routines for the capacitated vehicle routing problem. http://www.hha.dk/lys
[23]Lysgaard J, Letchford AN, Eglese RW (2003) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math Program 100: 2004
[24]Pasia JM, Doerner KF, Hartl RF, Reimann M (2007a) Solving a bi-objetive vehicle routing problem by pareto-ant colony optimization, vol 4638 of LNCS, pp 187–191. SLS 2007
[25]Pasia JM, Doerner KF, Hartl RF, Reimann M (2007b) A population-based local search for solving a bi-objective vehicle routing problem, vol 4446 of LNCS, pp 166–175. EvoCOP
[26]Prins C (2004) A simple and effective evolutionary algorithm for the vehicle routing problem. Comput Oper Res 31: 1985–2002 · Zbl 1100.90504 · doi:10.1016/S0305-0548(03)00158-8
[27]Ralphs TK, Saltzman M, Wiecek M (2004) An improved algorithm for biobjective integer programming and its application to network routing problems. Ann Oper Res
[28]Toth P, Vigo D (eds) (2001) The vehicle routing problem, vol 9 of SIAM monographs on discrete mathematics and applications, SIAM
[29]Tricoire F, Doerner KF, Hartl RF, Iori M (2009) Heuristic and exact algorithms for the multi-pile vehicle routing problem. Submitted to OR Spectrum
[30]Valenzuela CL, Jones AJ (1997) Estimating the Held-Karp lower bound for the geometric TSP. Eur J Oper Res 102(1): 157–175 · Zbl 0948.90034 · doi:10.1016/S0377-2217(96)00214-7
[31]Volgenant T, Jonker R (1982) A branch and bound algorithm for the symmetric traveling salesman problem based on 1-tree relaxation. Eur J Oper Res 9: 83–89 · Zbl 0471.90088 · doi:10.1016/0377-2217(82)90015-7
[32]Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms-a comparative case study. Lect Notes Comput Sci 292–304
[33]Zitzler E, Thiele L, Laumanns M, Fonseca CM, da Fonseca VG (2003) Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evol Comput 7(2): 117–132 · doi:10.1109/TEVC.2003.810758
[34]Zitzler E, Brockhoff D, Thiele L (2007) The hypervolume indicator revisited: on the design of pareto-compliant indicators via weighted integration. Lect Notes Comput Sci 4403: 862 · doi:10.1007/978-3-540-70928-2_64