Exact hybrid algorithms for solving a bi‐objective vehicle routing problem

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.