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

【摘要】：針對快遞服務(wù)網(wǎng)絡(luò)結(jié)構(gòu)上的非對稱性以及可提前獲知待服務(wù)需求的位置和釋放時(shí)間的特征,將預(yù)知信息引入可返回原點(diǎn)的非對稱TSP問題中,提出以服務(wù)總成本最小為目標(biāo)的帶有預(yù)知信息的在線Homing ATSP問題.分析了該問題競爭比的下界,并且在一般網(wǎng)絡(luò)圖上設(shè)計(jì)了SSdd(α)算法和PAH-dd算法,分析了算法各自的競爭比.結(jié)果表明在線車采取適時(shí)等待策略比采取zealous策略更優(yōu);并且預(yù)知信息越多,在線算法的競爭性能越優(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.
【作者單位】： 西安交通大學(xué)管理學(xué)院;西安工業(yè)大學(xué)經(jīng)濟(jì)管理學(xué)院;西安交通大學(xué)機(jī)械制造系統(tǒng)工程國家重點(diǎn)實(shí)驗(yàn)室;
【基金】：國家自然科學(xué)基金(61221063,71071123) 長江學(xué)者和創(chuàng)新團(tuán)隊(duì)發(fā)展計(jì)劃(IRT1173)
【分類號】：TP393.01

【參考文獻(xiàn)】

相關(guān)期刊論文 前1條

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

【共引文獻(xiàn)】

相關(guān)期刊論文 前2條

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

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

相關(guān)會議論文 前1條

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

相關(guān)博士學(xué)位論文 前4條

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

2 包曉光;一些路線問題的算法設(shè)計(jì)與分析[D];華東理工大學(xué);2012年

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

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

相關(guān)碩士學(xué)位論文 前2條

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

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

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

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

2 王明岳;;目標(biāo)可移動(dòng)的直線搜索問題的在線算法研究[J];計(jì)算機(jī)工程與科學(xué);2008年12期

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

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

5 呂淑平;方興杰;;基于獨(dú)立分量分析的自適應(yīng)在線算法[J];計(jì)算機(jī)應(yīng)用研究;2010年11期

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

7 賀文武;;在線核學(xué)習(xí)的一般形式探討[J];福建工程學(xué)院學(xué)報(bào);2010年04期

8 仵博;吳敏;佘錦華;;基于點(diǎn)的POMDPs在線值迭代算法[J];軟件學(xué)報(bào);2013年01期

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

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

相關(guān)會議論文 前4條

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

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

3 石永強(qiáng);張國川;;工件尺寸不同的單臺批處理機(jī)加工在線問題[A];中國運(yùn)籌學(xué)會第七屆學(xué)術(shù)交流會論文集（上卷）[C];2004年

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

相關(guān)博士學(xué)位論文 前3條

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

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

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

相關(guān)碩士學(xué)位論文 前7條

1 張韜;帶前瞻的在線最大化問題[D];復(fù)旦大學(xué);2008年

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

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

4 劉幼珠;基于在線算法的進(jìn)口設(shè)備投資決策研究[D];華南理工大學(xué);2014年

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

6 王明岳;m射線路徑上移動(dòng)目標(biāo)搜索的在線算法研究[D];復(fù)旦大學(xué);2009年

7 高文君;序列標(biāo)注的在線算法研究[D];復(fù)旦大學(xué);2011年

，

本文編號：1574828