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

【摘要】：為了在自然災害之后通過應急車輛盡快地將應急物資送到受災點,針對每個受災點在發(fā)出需求信號后,不能盡快被應急車輛服務,從而導致受災點的情形進一步惡化的情形,提出了帶有線性懲罰的在線旅行商問題。通過設計最壞序列證明了該問題在一般網絡上不存在確定性和隨機性的在線算法。針對需求點僅在線段上的情形,分析了問題的下界、設計了推測后再移動策略,并證明了當單個需求點的最大懲罰值大于等于8時,該算法為最優(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.
【作者單位】： 重慶郵電大學經濟管理學院;西安交通大學管理學院;西安交通大學機械制造系統(tǒng)工程國家重點實驗室;重慶交通大學管理學院;
【基金】：重慶市社會科學規(guī)劃博士基金資助項目(2014BS108,2016BS085) 重慶市教委科技基金資助項目(KJ1600525) 陜西省自然科學基礎研究計劃資助項目(2015JM7372) 重慶郵電大學文峰創(chuàng)新創(chuàng)業(yè)基金資助項目(WF201406)~~
【分類號】：TP301.6

【相似文獻】

相關期刊論文 前10條

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

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

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

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

5 江賀;張憲超;陳國良;;有向黑白旅行商問題[J];計算機學報;2007年03期

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

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

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

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

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

相關會議論文 前7條

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

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

3 張輝;王錫淮;肖健梅;;基于改進蟻群算法的旅行商問題[A];2007中國控制與決策學術年會論文集[C];2007年

4 劉春波;潘豐;楊丹;;基于改進的蟻群算法在中國旅行商問題中的求解[A];2007中國控制與決策學術年會論文集[C];2007年

5 韓愛麗;朱大銘;;旅行商問題的一種新DNA編碼方案[A];2006年全國理論計算機科學學術年會論文集[C];2006年

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

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

相關博士學位論文 前1條

1 王剛;兩類圈問題的算法研究[D];國防科學技術大學;2013年

相關碩士學位論文 前10條

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

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

3 高峰;求解多目標旅行商問題的進化算法研究[D];華東師范大學;2013年

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

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

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

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

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

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

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

，

本文編號：2011364