Journées de l'optimisation 2007 Optimizations days

The Capacitated Arc Routing Problem (CARP) consists of determining a set of least cost capacitated vehicle routes servicing a set of arcs. The undirected CARP is formulated as a pure binary linear integer problem. Valid inequalities are generated and the problem is solved by branch-and-cut. All the benchmark instances proposed by DeArmon and Benavent et al. can be solved without any branching, for the first time ever.

We describe a branch-and-cut-and-price algorithm for the vehicle routing problem with two-dimensional loading constraints. This problem extends the classical vehicle routing problem by considering that items demanded by the customer must be packed into the space available in the vehicle serving the customer, together with other items delivered by the vehicle.

A guided cooperative-search mechanism identifies promising patterns in previously identified solutions and the global search while controlling the diversification and intensification phases. The mechanism is based on the solution warehouse strategy, in which several search processes cooperate by asynchronously exchanging information on the best solutions identified. Each of the independent processes implements a different search, a metaheuristic such as evolutionary algorithm, a tabu search, a random search or a post-optimization procedure. Patterns of elements in promising and unpromising solutions are identified and used to guide the search. We propose an enhancement to the cooperative search with a dynamic guidance mechanism to orient the search by controlling automatically the diversification and intensification phases. The variation in entropy of the solution warehouse is used as a metric to control these phases and to prevent premature convergence. No attempt has been made to calibrate the individual search methods, the parallel cooperative method or the dynamic guidance mechanism. The results obtained on a set of selected test problems of the vehicle routing problem with time windows shows that the dynamically guided cooperative search performs better than other cooperatives methods. It identifies solutions of comparable quality to those obtained by the best methods in the literature and finds one new best result. Keywords : parallel cooperative search, dynamic guidance, entropy, vehicle routing with time windows

The Capacitated Arc Routing Problem (CARP) is a well known NP-hard problem. In this talk we discuss the use of several flow based formulations for an extended mixed CARP. These formulations are evaluated over a set of benchmark problems.