系统工程理论与实践
繫統工程理論與實踐
계통공정이론여실천
Systems Engineering—Theory & Practice
2015年
2期
381~387
,共null页
马军平 徐寅峰 温新刚 张惠丽
馬軍平 徐寅峰 溫新剛 張惠麗
마군평 서인봉 온신강 장혜려
旅行商问题 预知信息 非对称网络 在线算法
旅行商問題 預知信息 非對稱網絡 在線算法
여행상문제 예지신식 비대칭망락 재선산법
travelling salesman problem; advanced information; asymmetric network; online algorithm
针对快递服务网络结构上的非对称性以及可提前获知待服务需求的位置和释放时间的特征, 将预知信息引入可返回原点的非对称TSP问题中, 提出以服务总成本最小为目标的带有预知信息的在线Homing ATSP问题. 分析了该问题竞争比的下界, 并且在一般网络图上设计了 SS-dd（α） 算法和PAH-dd算法, 分析了算法各自的竞争比. 结果表明在线车采取适时等待策略比采取zealous策略更优; 并且预知信息越多, 在线算法的竞争性能越优.
針對快遞服務網絡結構上的非對稱性以及可提前穫知待服務需求的位置和釋放時間的特徵, 將預知信息引入可返迴原點的非對稱TSP問題中, 提齣以服務總成本最小為目標的帶有預知信息的在線Homing ATSP問題. 分析瞭該問題競爭比的下界, 併且在一般網絡圖上設計瞭 SS-dd（α） 算法和PAH-dd算法, 分析瞭算法各自的競爭比. 結果錶明在線車採取適時等待策略比採取zealous策略更優; 併且預知信息越多, 在線算法的競爭性能越優.
침대쾌체복무망락결구상적비대칭성이급가제전획지대복무수구적위치화석방시간적특정, 장예지신식인입가반회원점적비대칭TSP문제중, 제출이복무총성본최소위목표적대유예지신식적재선Homing ATSP문제. 분석료해문제경쟁비적하계, 병차재일반망락도상설계료 SS-dd（α） 산법화PAH-dd산법, 분석료산법각자적경쟁비. 결과표명재선차채취괄시등대책략비채취zealous책략경우; 병차예지신식월다, 재선산법적경쟁성능월우.
Based on the asymmetry of courier service network and the situation in which the location and release time of requests could be known in advance, this paper introduced the advanced information to homing asymmetric TSP, proposed the online homing ATSP with advanced information. A lower bound was given, SS-dd（α） algorithm and PAH-dd algorithm were presented for general metric space. Competitive analysis were given to the two algorithms respectively. The result indicated that the strategy of waiting when necessary has an advantage over zealous strategy, and, the more advanced information, the better the online algorithms perform.
