Cristin-resultat-ID: 1146422
Sist endret: 12. august 2014, 13:01
Resultat
Vitenskapelig foredrag
2014

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

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

Presentasjon

Navn på arrangementet: The third meeting of the EURO Working Group on Vehicle Routing and Logistics Optimization (VeRoLog 2014)
Sted: Oslo
Dato fra: 22. juni 2014
Dato til: 25. juni 2014

Arrangør:

Arrangørnavn: SINTEF, Høgskolen i Molde, NTNU, NHH

Om resultatet

Vitenskapelig foredrag
Publiseringsår: 2014

Beskrivelse Beskrivelse

Tittel

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

Sammendrag

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.

Bidragsytere

Ingvild Lyckander

  • Tilknyttet:
    Forfatter
    ved Norges teknisk-naturvitenskapelige universitet

Markus Grasmair

  • Tilknyttet:
    Forfatter
    ved Institutt for matematiske fag ved Norges teknisk-naturvitenskapelige universitet

Elin Espeland Halvorsen-Weare

  • Tilknyttet:
    Forfatter
    ved Energi og transport ved SINTEF Ocean

Geir Hasle

  • Tilknyttet:
    Forfatter
    ved Mathematics and Cybernetics ved SINTEF AS
1 - 4 av 4