本文選題：旅行商問題　切入點：預知信息　出處：《系統(tǒng)工程理論與實踐》2015年02期 　論文類型：期刊論文

【摘要】：針對快遞服務網(wǎng)絡結構上的非對稱性以及可提前獲知待服務需求的位置和釋放時間的特征,將預知信息引入可返回原點的非對稱TSP問題中,提出以服務總成本最小為目標的帶有預知信息的在線Homing ATSP問題.分析了該問題競爭比的下界,并且在一般網(wǎng)絡圖上設計了SSdd(α)算法和PAH-dd算法,分析了算法各自的競爭比.結果表明在線車采取適時等待策略比采取zealous策略更優(yōu);并且預知信息越多,在線算法的競爭性能越優(yōu).
[Abstract]:In view of the asymmetry in the network structure of express delivery service and the characteristics of knowing the location and release time of the need for service in advance, the predictive information is introduced into the asymmetric TSP problem which can return to the origin. This paper presents an online Homing ATSP problem with predictive information aiming at the minimum total service cost, analyzes the lower bound of the competition ratio of the problem, and designs the SSdd- (偽) algorithm and the PAH-dd algorithm on the general network diagram. The results show that the in-time waiting strategy is better than the zealous strategy, and the more information is predicted, the better the competitive performance of the online algorithm is.
【作者單位】： 西安交通大學管理學院;西安工業(yè)大學經(jīng)濟管理學院;西安交通大學機械制造系統(tǒng)工程國家重點實驗室;
【基金】：國家自然科學基金(61221063,71071123) 長江學者和創(chuàng)新團隊發(fā)展計劃(IRT1173)
【分類號】：TP393.01

【參考文獻】

相關期刊論文 前1條

1 溫新剛;徐寅峰;丁黎黎;;基于預知信息的占線Nomadic TSP問題[J];系統(tǒng)工程理論與實踐;2013年11期

【共引文獻】

相關期刊論文 前2條

1 馬衛(wèi)民;董丹丹;王珂;;基于特殊路徑的局內(nèi)車輛路徑問題混合策略研究[J];運籌與管理;2011年05期

2 溫新剛;徐寅峰;丁黎黎;;基于預知信息的占線Nomadic TSP問題[J];系統(tǒng)工程理論與實踐;2013年11期

相關會議論文 前1條

1 ;Dial-a-Ride Problem with Time-Windows and On-Line Algorithms[A];中國運籌學會第七屆學術交流會論文集（上卷）[C];2004年

相關博士學位論文 前4條

1 余煒;若干網(wǎng)絡排序問題的算法和復雜性研究[D];華東理工大學;2010年

2 包曉光;一些路線問題的算法設計與分析[D];華東理工大學;2012年

3 周潔;車輛調(diào)度問題的算法及復雜性[D];華東師范大學;2013年

4 于波;快運網(wǎng)絡構建及快運車輛配載配送優(yōu)化研究[D];大連海事大學;2013年

相關碩士學位論文 前2條

1 賀朝新;動態(tài)TSP遺傳算法研究[D];中南民族大學;2010年

2 楊鳴;動態(tài)多目標TSP演化算法研究[D];中國地質(zhì)大學;2008年

【相似文獻】

相關期刊論文 前10條

1 龔元浩;楊晨暉;;基于感知評價的三維信號識別的一種在線算法[J];計算機工程與科學;2009年05期

2 王明岳;;目標可移動的直線搜索問題的在線算法研究[J];計算機工程與科學;2008年12期

3 仵博;吳敏;;基于Monte Carlo粒子濾波的POMDPs在線算法[J];控制與決策;2013年06期

4 王洪濤;鄒鶴良;李達強;何國淵;;基于左右手運動想象的在線算法設計與應用[J];數(shù)據(jù)采集與處理;2013年06期

5 呂淑平;方興杰;;基于獨立分量分析的自適應在線算法[J];計算機應用研究;2010年11期

6 帥典勛;在可編程序的邏輯陣列(PLA)中交叉點故障定位的一種在線算法[J];計算機工程;1984年06期

7 賀文武;;在線核學習的一般形式探討[J];福建工程學院學報;2010年04期

8 仵博;吳敏;佘錦華;;基于點的POMDPs在線值迭代算法[J];軟件學報;2013年01期

9 肖鳴宇;沈正翔;;帶有多折扣選項的滑雪租賃問題的在線和離線算法[J];軟件學報;2014年05期

10 余建軍;吳春明;;支持接入控制的虛擬網(wǎng)映射近似算法[J];電子與信息學報;2014年05期

相關會議論文 前4條

1 柏慶國;張玉忠;;有尺寸的單機在線分批排序[A];中國運籌學會第七屆學術交流會論文集（中卷）[C];2004年

2 何宇新;韓志剛;;多層遞階方法時變參數(shù)估值最佳初值和最佳跟蹤的在線算法[A];1992年中國控制與決策學術年會論文集[C];1992年

3 石永強;張國川;;工件尺寸不同的單臺批處理機加工在線問題[A];中國運籌學會第七屆學術交流會論文集（上卷）[C];2004年

4 尹煥平;孫宗海;;基于自然梯度的支持向量回歸在線算法[A];2009中國控制與決策會議論文集（3）[C];2009年

相關博士學位論文 前3條

1 李文杰;具有交貨期或友好釋放時間的在線排序研究[D];鄭州大學;2014年

2 農(nóng)慶琴;在線排序與路由安排[D];鄭州大學;2006年

3 黃禹瀟;面向復雜診斷貝葉斯網(wǎng)實時推理問題的離線、在線算法的研究[D];吉林大學;2012年

相關碩士學位論文 前7條

1 張韜;帶前瞻的在線最大化問題[D];復旦大學;2008年

2 吳用;平行機覆蓋問題的半在線算法研究[D];浙江大學;2006年

3 高潔;批容量有界的單機分批列表在線排序[D];鄭州大學;2011年

4 劉幼珠;基于在線算法的進口設備投資決策研究[D];華南理工大學;2014年

5 馬平娟;兩類單機批容量有界的分批在線排序[D];鄭州大學;2012年

6 王明岳;m射線路徑上移動目標搜索的在線算法研究[D];復旦大學;2009年

7 高文君;序列標注的在線算法研究[D];復旦大學;2011年

，

本文編號：1574828