论文部分内容阅读
针对快递服务网络结构上的非对称性以及可提前获知待服务需求的位置和释放时间的特征,将预知信息引入可返回原点的非对称TSP问题中,提出以服务总成本最小为目标的带有预知信息的在线Homing ATSP问题.分析了该问题竞争比的下界,并且在一般网络图上设计了SSdd(α)算法和PAH-dd算法,分析了算法各自的竞争比.结果表明在线车采取适时等待策略比采取zealous策略更优;并且预知信息越多,在线算法的竞争性能越优.
Aiming at asymmetric structure of courier service network as well as the location and release time characteristics of service to be served in advance, the prediction information can be introduced into the problem of asymmetric TSP that can return to the origin. Aiming at the problem that the total cost of service The Homing ATSP problem of predicting information is analyzed.The lower bound of the competition ratio of the problem is analyzed and the SSdd (α) algorithm and the PAH-dd algorithm are designed on the general network graph, and the competition ratios of the algorithms are analyzed.The results show that the on- Waiting for the strategy is better than taking the zealous strategy. And the more information is foreseen, the better the competition performance of the online algorithm.