To main content

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

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

Category
Conference lecture and academic presentation
Abstract
Lately there has been increasing 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.
Client
  • Norges forskningsråd / 246825
Language
English
Author(s)
Affiliation
  • SINTEF Digital / Mathematics and Cybernetics
  • SINTEF
  • SINTEF Ocean / SINTEF Ocean
  • Norwegian University of Science and Technology
Presented at
VeRoLog 2016 - The fifth meeting of the EURO Working Group on Vehicle Routing and Logistics optimization
Place
Nantes
Date
05.06.2016 - 07.06.2016
Organizer
École des mines de Nantes
Year
2016