Lower and upper bounds for location-arc routing problems with vehicle capacity constraints

This paper addresses multi-depot location arc routing problems with vehicle capacity constraints. Two mixed integer programming models are presented for single and multi-depot problems. Relaxing these formulations leads to other integer programming models whose solutions provide good lower bounds for the total cost. A powerful insertion heuristic has been developed for solving the underlying capacitated arc routing problem. This heuristic is used together with a novel location–allocation heuristic to solve the problem within a simulated annealing framework. Extensive computational results demonstrate that the proposed algorithm can find high quality solutions. We also show that the potential cost saving resulting from adding location decisions to the capacitated arc routing problem is significant.

► A location-arc routing problem with capacity constraints is formulated. ► The average cost saving due to changing the location of a central depot is 13.82%. ► The maximum saving from location improvement happens to be 56.54%. ► When the allowable number of locations increases, the marginal saving decreases. ► As the vehicle capacity is more limited, the problem becomes more difficult.