A Memetic Algorithm for the Mixed Capacitated General Routing Problem with Route Balancing

Lately there has been an increase of research on the Mixed Capacitated General Routing Problem (MCGRP) – a generalization of the Capacitated Vehicle Routing Problem and the Capacitated Arc Routing Problem. Although it is an important aspect of real-life VRPs, route balancing has drawn surprisingly little attention in the literature. A VRP solution, however close to optimal regarding travel cost, will often be considered useless in practice if the variation in duration, cost, or workload between routes is large. We investigate a bi-criteria MCGRP with Route Balancing (MCGRP-RB) where total cost is one criterion and route balance the second. As route balance objective we minimize the difference in cost between the longest and the shortest route. Our approach is true bi-criteria optimization, and our goal is to find good approximations to the Pareto front in reasonable time. To this end we propose a memetic algorithm with two crossover operators and three mutation operators. All non-dominated solutions are kept in an archive. Separate archives are maintained for solutions that have high quality for one of the objective functions to enforce longitudinal diversity. Further, for each individual a rank is computed, which effectively creates several fronts of different quality. A computational study shows that the method is able to produce the exact Pareto front for small instances. For larger instances, it yields new dominating solutions for several standard MCGRP test instances. At the conference, detailed results will be presented and compared, both to approximations produced by a competing metaheuristic, and to exact Pareto fronts.