论文部分内容阅读
针对n次连续的交通需求依次到达出发点选择路径到目的地去的问题,本文从占线与竞争策略的角度出发,研究流量是任意可分的情形下交通流量分配,采用系统最优策略分配交通需求,即每次分配流量后都能使得当前网络上所有用户花费费用总和最小。借助于变分不等式对系统最优策略进行了竞争分析,特别地,当路阻函数是系数非负的线性函数时,证明该策略是4-竞争的;当路阻函数是系数非负、度数至多是d的多项式函数时,该策略是(d+)d+1-竞争的,同时给出系统最优策略竞争比的下界是5/3。
Aiming at the problem that n successive traffic demands arrive at the starting point and the destination is chosen, the paper studies the traffic flow distribution under any separable situation from the perspective of busyness and competition strategy, and allocates the traffic demand with the optimal system strategy , That is, each time after the allocation of traffic can make all users on the current network to spend the sum of the minimum. The optimal strategy of the system is analyzed by means of variational inequalities. Especially when the resistance function is a linear function with non-negative coefficients, it is proved that the strategy is 4-competitive. When the resistance function is nonnegative, The strategy is (d +) d + 1-converse at most polynomial functions of d, and the lower bound of the optimal system strategy competition ratio is 5/3.