To main content

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

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.

Category

Academic lecture

Client

  • Research Council of Norway (RCN) / 246825

Language

English

Author(s)

Affiliation

  • SINTEF Digital / Mathematics and Cybernetics
  • SINTEF
  • 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

06.06.2016 - 08.06.2016

Organizer

École des mines de Nantes

Year

2016

View this publication at Cristin