發(fā)布時(shí)間：2018-06-12 22:51

  本文選題：旅行商問題 + 線性懲罰��； 參考：《計(jì)算機(jī)集成制造系統(tǒng)》2017年04期

【摘要】：為了在自然災(zāi)害之后通過應(yīng)急車輛盡快地將應(yīng)急物資送到受災(zāi)點(diǎn),針對(duì)每個(gè)受災(zāi)點(diǎn)在發(fā)出需求信號(hào)后,不能盡快被應(yīng)急車輛服務(wù),從而導(dǎo)致受災(zāi)點(diǎn)的情形進(jìn)一步惡化的情形,提出了帶有線性懲罰的在線旅行商問題。通過設(shè)計(jì)最壞序列證明了該問題在一般網(wǎng)絡(luò)上不存在確定性和隨機(jī)性的在線算法。針對(duì)需求點(diǎn)僅在線段上的情形,分析了問題的下界、設(shè)計(jì)了推測(cè)后再移動(dòng)策略,并證明了當(dāng)單個(gè)需求點(diǎn)的最大懲罰值大于等于8時(shí),該算法為最優(yōu)算法。
[Abstract]:In order to deliver emergency supplies to the disaster site as soon as possible through emergency vehicles after a natural disaster, the emergency vehicle service cannot be served as soon as possible after each disaster site has issued a demand signal, thus leading to a further deterioration of the situation at the disaster site. An online traveling salesman problem with linear penalty is proposed. By designing worst-case sequences, it is proved that there are no deterministic and stochastic online algorithms for this problem in general networks. For the case that the demand point is only on the line segment, this paper analyzes the lower bound of the problem, designs a speculative removing strategy, and proves that the algorithm is an optimal algorithm when the maximum penalty value of a single demand point is greater than or equal to 8.
【作者單位】： 重慶郵電大學(xué)經(jīng)濟(jì)管理學(xué)院;西安交通大學(xué)管理學(xué)院;西安交通大學(xué)機(jī)械制造系統(tǒng)工程國(guó)家重點(diǎn)實(shí)驗(yàn)室;重慶交通大學(xué)管理學(xué)院;
【基金】：重慶市社會(huì)科學(xué)規(guī)劃博士基金資助項(xiàng)目(2014BS108,2016BS085) 重慶市教委科技基金資助項(xiàng)目(KJ1600525) 陜西省自然科學(xué)基礎(chǔ)研究計(jì)劃資助項(xiàng)目(2015JM7372) 重慶郵電大學(xué)文峰創(chuàng)新創(chuàng)業(yè)基金資助項(xiàng)目(WF201406)~~
【分類號(hào)】：TP301.6

【相似文獻(xiàn)】

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

1 王大志;汪定偉;閆楊;;一類多旅行商問題的計(jì)算及仿真分析[J];系統(tǒng)仿真學(xué)報(bào);2009年20期

2 莫愿斌;劉賀同;王勤;;旅行商問題的綜述教學(xué)研究[J];中國(guó)科教創(chuàng)新導(dǎo)刊;2008年08期

3 顧大權(quán);徐四林;袁媛;汪晉;;求解旅行商問題的一個(gè)有效算法[J];解放軍理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年02期

4 陳文蘭;戴樹貴;;旅行商問題算法研究綜述[J];滁州學(xué)院學(xué)報(bào);2006年03期

5 江賀;張憲超;陳國(guó)良;;有向黑白旅行商問題[J];計(jì)算機(jī)學(xué)報(bào);2007年03期

6 管琳;白艷萍;;用分支定界算法求解旅行商問題[J];中北大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年02期

7 黃可為;汪定偉;;熱軋計(jì)劃中的多旅行商問題及其計(jì)算方法[J];計(jì)算機(jī)應(yīng)用研究;2007年07期

8 張敏;金琴玲;;旅行商問題的一種新解法[J];重慶職業(yè)技術(shù)學(xué)院學(xué)報(bào);2008年01期

9 高春濤;;求解旅行商問題的幾種解法[J];邊疆經(jīng)濟(jì)與文化;2010年05期

10 劉冠佳;劉水強(qiáng);;一類多出發(fā)點(diǎn)多旅行商問題規(guī)劃算法[J];山東理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年02期

相關(guān)會(huì)議論文 前7條

1 馮純伯;;旅行商問題的一種解法[A];1991年控制理論及其應(yīng)用年會(huì)論文集（下）[C];1991年

2 胡巧華;吳懷宇;陳喬禮;陳媛;;一種求解旅行商問題的啟發(fā)交叉算子的研究[A];第25屆中國(guó)控制會(huì)議論文集（中冊(cè)）[C];2006年

3 張輝;王錫淮;肖健梅;;基于改進(jìn)蟻群算法的旅行商問題[A];2007中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集[C];2007年

4 劉春波;潘豐;楊丹;;基于改進(jìn)的蟻群算法在中國(guó)旅行商問題中的求解[A];2007中國(guó)控制與決策學(xué)術(shù)年會(huì)論文集[C];2007年

5 韓愛麗;朱大銘;;旅行商問題的一種新DNA編碼方案[A];2006年全國(guó)理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會(huì)論文集[C];2006年

6 賈亞軍;叢爽;;粒子群與模擬退火的混合算法求解旅行商問題[A];'2010系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)會(huì)議論文集[C];2010年

7 董亞非;譚剛軍;張社民;;基于粘貼系統(tǒng)求解TSP問題[A];提高全民科學(xué)素質(zhì)、建設(shè)創(chuàng)新型國(guó)家——2006中國(guó)科協(xié)年會(huì)論文集（下冊(cè)）[C];2006年

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

1 王剛;兩類圈問題的算法研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2013年

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

1 徐東鎮(zhèn);蟻群算法及其在廣義旅行商問題求解中的應(yīng)用[D];合肥工業(yè)大學(xué);2007年

2 王玲麗;隨機(jī)存儲(chǔ)下的有容量限制的廣義旅行商問題[D];上海交通大學(xué);2012年

3 高峰;求解多目標(biāo)旅行商問題的進(jìn)化算法研究[D];華東師范大學(xué);2013年

4 覃錦華;求解旅行商問題的進(jìn)化算法[D];西安電子科技大學(xué);2008年

5 李天龍;基于自組織優(yōu)化算法的多旅行商問題的求解與應(yīng)用[D];浙江大學(xué);2010年

6 南小康;樹算法求解旅行商問題[D];蘭州大學(xué);2008年

7 劉仁洪;一種改進(jìn)的蟻群算法求解旅行商問題[D];山東大學(xué);2008年

8 胡平;群集智能算法在不確定旅行商問題中的應(yīng)用研究[D];吉林大學(xué);2007年

9 李國(guó)寧;基于捕食搜索的蟻群算法及其在旅行商問題中的應(yīng)用研究[D];華南理工大學(xué);2010年

10 吳曉維;求解旅行商問題和非線性方程組的蟻群算法[D];陜西師范大學(xué);2008年

，

本文編號(hào)：2011364