Online Traffic Distribution Based on System Optimal Strategy
Bing Su · Systems Engineering · 2009
This paper explores the issue of arriving at the starting point in file to choose the route to the destination under n sequential traffic demands.From the point of view of online and competitive strategy,we define flow as the distribution of traffic volume in arbitrarily divisible situations.A system optimal strategy is put forward to assign traffic demand under the assumption that every assignment of flow will be able to minimize the total sum of all on-line users' expenses.The System optimal strategy is analyzed by resorting to variational inequality;the strategy is 4-competitive if the road impedance function is linear function with nonnegative coefficient,and is(d+1)d+1-competitive if the road impedance function is the polynomial function with nonnegative coefficient and the most degree d,meanwhile,a lower bound on the competitive ratio of system optimization strategy 5/3 is given.