  The Capacitated Arc Routing Problem (CARP) occurs in applications like urban
waste collection or winter gritting. It is usually defined in literature on an
undirected graph , with a set of nodes and a set of edges. A fleet of identical
vehicles of capacity is based at a depot node. Each edge has a cost (length)
and a demand (e.g. an amount of waste), and it may be traversed any number of
times. The edges with non-zero demands or tasks require service by a vehicle.
The goal is to determine a set of vehicle trips (routes) of minimum total cost,
such that each trip starts and ends at the depot, each task is serviced by one
single trip, and the total demand handled by any vehicle does not exceed . To
the best of our knowledge the best published method is a memetic algorithm
first introduced in 2001. This article provides a new extension of the NSGA II
(Non-dominated Sorting Genetic Algorithm) template to comply with the
stochastic sight of the CARP. The main contribution is: - to introduce
mathematical expression to evaluate both cost and duration of the longest trip
and also standard deviation of these two criteria. - to use a NGA-II template
to optimize simultaneously the cost and the duration of the longest trip
including standard deviation. The numerical experiments managed on the thee
well-known benchmark sets of DeArmon, Belenguer and Benavent and Eglese, prove
it is possible to obtain robust solutions in four simultaneous criteria in
rather short computation times.
