Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1245.90010
Reiter, Peter; Gutjahr, Walter J.
Exact hybrid algorithms for solving a bi-objective vehicle routing problem. (English)
[J] CEJOR, Cent. Eur. J. Oper. Res. 20, No. 1, 19-43 (2012). ISSN 1435-246X; ISSN 1613-9178/e

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 $\varepsilon$-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 2000:: *90B06 Transportation, logistics
90C27 Combinatorial programming
90C29 Multi-objective programming, etc.
90B10 Flows in networks
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Keywords: capacitated vehicle routing problem; distance constraints; multiobjective combinatorial optimization; branch-and-cut; {\tt TSPLIB}

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]