A Lagrangean decomposition for tunnel interdiction in hazmat transportation

According to the ADR 2007 all European tunnels have to be classified into five categories limiting more and more restrictively the passage of vehicles carrying hazardous materials (hazmats): from class A where the transport of all hazmats is allowed, to class E where none of them can pass, considering in the intermediate classes the restrictions on explosive, toxic and inflammable materials. The ADR 2007 states that the competent authority has to assign the road tunnel to one of the five categories. On the other hand, each carrier is free to travel in the resulting road network along a minimum cost route. We aim at a decision support model to decide which tunnels to interdict to which types of hazmats so as to minimize the total transportation risk. Despite a single-level formulation has been developed, it cannot be used to solve realworld tunnel interdiction instances because the huge number of variables. In this work, we develop a Lagrangean decomposition approach for the single-level formulation and a Lagrangean heuristic. Thus the original problem is reduced to the solution of a large number of MILPs of smaller size that can be solved with any state-of-the-art MILP solver.