Exact hybrid algorithms for solving a bi-objective vehicle routing problem |
| |
Authors: | Peter Reiter Walter J Gutjahr |
| |
Institution: | (1) Department of Statistics and Decision Support Systems, University of Vienna, Universitaetsstr. 5/9, 1010 Vienna, Austria |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|