The route expropriation problem

This paper considers the problem of selecting obnoxious routes (e.g., routes used to transport hazardous material) on a transportation network assuming that population centers on or outside the network within a certain distance from the selected routes can be expropriated at a given price. The objective is to select the routes so as to minimize the total weighted transportation and expropriation costs. For the single-flow problem, a polynomial algorithm is developed. For the multiple-flow problem, a branch-and-price algorithm using column generation is developed and its efficiency is tested with computational experiments.