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.
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.