【摘要】 针对n次连续的交通需求依次到达出发点选择路径到目的地去的问题,本文从占线与竞争策略的角度出发,研究流量是任意可分的情形下交通流量分配,采用系统最优策略分配交通需求,即每次分配流量后都能使得当前网络上所有用户花费费用总和最小。借助于变分不等式对系统最优策略进行了竞争分析,特别地,当路阻函数是系数非负的线性函数时,证明该策略是4-竞争的;当路阻函数是系数非负、度数至多是d的多项式函数时,该策略是(d+)d+1-竞争的,同时给出系统最优策略竞争比的下界是5/3。更多还原

【Abstract】 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.更多还原