Program > By author > Sanchis José. M.

Experiments with different formulations for the Capacitated Arc Routing Problem
Enrique Benavent  1@  , Jose M. Belenguer  1@  , Angel Corberán  1@  , Isaac Plana  1@  , José. M. Sanchis  2@  
1 : Universidad de Valencia
2 : UNIVERSIDAD POLITECNICA DE VALENCIA

In this talk we analyze two different integer programming formulations for the Capacitated Arc Routing Problem defined on an undirected graph (CARP). One formulation uses directed variables while the other uses non-directed variables.

For each formulation, a branch-and-cut algorithm has been implemented to solve the CARP optimally. All families of known valid inequalities for this problem and for the Rural Postman Problem, which is a particular case of the CARP, have been considered and their corresponding separation algorithms have been implemented.

Preliminary computational results will be presented.


Online user: 1