To main content

A Hybrid Metaheuristic for a multi-objective Mixed Capacitated General Routing Problem

Abstract

The Mixed Capacitated General Routing Problem (MCGRP) is a generalization of the Capacitated Vehicle Routing Problem (CVRP) and the Capacitated Arc Routing Problem (CARP). It is defined on a mixed graph, and tasks may be located on nodes, edges, and arcs. A homogeneous fleet of capacitated vehicles is based in a special node called the depot. The aim of the problem is to generate a set of vehicle routes, starting and ending at the depot, such that every task is serviced exactly once and the total demand serviced by each vehicle does not exceed the vehicle capacity. The objective is to minimize the total travel cost. The general definition of the problem makes MCGRP more suited than the CVRP and the CARP for modeling certain real-life cases. Examples are waste collection and newspaper delivery. In the modeling of dense urban areas, demand on housing streets may be aggregated and represented as tasks on links. Larger facilities, like hospital and apartment buildings, and other isolated demand locations, are more adequately represented as nodes.

In contrast to the usual formulation of the MCGRP as a standard optimization problem, we study multi-objective variants of the MCGRP, where total route cost is still minimized, but additional objective component(s) must be optimized at the same time. For instance, it can be important to balance the work load of the different vehicles. Our approach is to find a set of Pareto optimal solutions, called a Pareto front. We propose metaheuristics that find high quality approximations to the Pareto front for multi-objective MCGRPs. The major challenges in solving multi-objective problems are to achieve diversity along the Pareto front and convergence towards optimal solutions while keeping the running time of the algorithm low. We present results from experiments on multi-objective versions of standard benchmarks for the MCGRP.

Category

Academic lecture

Client

  • Research Council of Norway (RCN) / 205298
  • Research Council of Norway (RCN) / 217108

Language

English

Author(s)

  • Ingvild Lyckander
  • Markus Grasmair
  • Elin Espeland Halvorsen-Weare
  • Geir Hasle

Affiliation

  • Norwegian University of Science and Technology
  • SINTEF Ocean / Energi og transport
  • SINTEF Digital / Mathematics and Cybernetics

Presented at

The third meeting of the EURO Working Group on Vehicle Routing and Logistics Optimization (VeRoLog 2014)

Place

Oslo

Date

22.06.2014 - 25.06.2014

Organizer

SINTEF, Høgskolen i Molde, NTNU, NHH

Year

2014

View this publication at Cristin