traffic assignment

33 Views Asked by At

Here are $m$ cities $C_1,\cdots,C_m$. The road connecting $V_i$ and $V_j$ is denoted as $E(i,j)$. Now there are $n$ trains $T_1,\cdots,T_n$. For each train $T_i$, it corresponds to two parameters: $P_i$ and $L_i$. $P_i$ is the path, indicating the route line of $T_i$ (the start city, the terminal city and the intermediate cities therein). $L_i$ is the time duration when $T_i$ stops at each city it pass by. Moreover, for each city $V_i$, it can accommondate at most $B_i$ trains simultaneously.

The problem is that we need to assign the start time for each train, in order to minimize the total duration as much as possible when all trains arrive at their terminal cities.

I wonder what kind of problem it is (so that I can carry out survey by myself). If possible, can anyone provide some algorithms possibly solving this problem? Many thanks!