Problem Decomposition for Traffic Diversions

摘要

When a major road traffic intersection is blocked, vehicles should be diverted from the incoming roads in such a way as to avoid the roads on the diversions from also becoming over-congested. Assuming different diversions may use partly the same roads, the challenge is to satisfy the following traffic flow constraint: ensure that even in the worst case scenario, the diversions can accommodate the same volume of traffic as the blocked intersection. The number of diversions increases quadratically with the number of roads at the intersection. Moreover any road may be used by any subset of the diversions - thus the number of worst cases can grow exponentially with the number of diversions. This paper investigates two different approaches to the problem, describes their implementation on the hybrid MIP/CP software platform ECL~iPS~e, and presents benchmark results on a set of test cases.