本文關鍵詞：基于服務時間約束的在線旅行商問題研究　出處：《西安交通大學》2017年博士論文　論文類型：學位論文

  更多相關文章： 服務時間約束 旅行商問題 在線算法 競爭分析

【摘要】：針對現(xiàn)實中的快餐送餐,快遞收件員取件以及出租車等上門服務中存在的提前預訂和顧客等待心理,探討了基于服務時間約束的在線旅行商問題;并分別根據(jù)服務目標是最小化成本,最大化利潤還是綜合考慮兩種目標的情形下對問題進行了分析。論文主要做了以下四方面的工作:1)研究了基于預知信息的在線Nomadic旅行商問題。針對現(xiàn)實中服務人員進行服務之后不必返回出發(fā)點的現(xiàn)象,將服務預訂通過預知信息引入到旅行商問題當中,探討了當服務器的目標為使成本盡可能小在線旅行商問題,并且對問題進行了競爭分析。通過構建特殊的網(wǎng)絡結(jié)構給出了問題的下界,并且分別在直線網(wǎng)絡上設計了ENO-dd算法,分析了算法的競爭比;在一般網(wǎng)絡上設計了GTR-dd算法,給出了算法的競爭比。通過比較分析發(fā)現(xiàn),在線服務器的競爭性能與預知信息具有正向關系。同時預知信息量的多少還控制著問題的占線性。2)研究了基于服務選擇和時間約束的在線旅行商問題�？紤]到現(xiàn)實中的顧客等待服務的等待心理以及顧客滿意度,將服務時間約束引入到具有服務選擇性的在線旅行商問題中。旅行商如果沒有在規(guī)定的時間約束內(nèi)對服務請求進行服務,則會產(chǎn)生懲罰�，F(xiàn)實中懲罰可以表現(xiàn)為名譽受損或者是服務費用增加等,此懲罰進入到服務器的服務成本。在線服務器的目標為使服務成本盡可能小。通過對該問題在一般網(wǎng)絡上的分析發(fā)現(xiàn),不存在具有常數(shù)競爭比的確定性和隨機性在線算法。因此對網(wǎng)絡進行了限制,考慮線段網(wǎng)絡上該問題的下界并且設計了Conjecture算法,給出了算法的競爭比。3)研究了基于預知信息和服務時間約束的在線旅行商問題�？紤]到等待服務的顧客等待心理以及服務的提前預訂,將服務時間約束引入到基于預知信息的在線旅行商問題當中。服務器的服務目標為盡可能多的在服務時間約束內(nèi)服務需求。通過在一般網(wǎng)絡上對問題的分析發(fā)現(xiàn)不存在具有常數(shù)競爭比的在線算法,因而分別考慮了網(wǎng)絡為一條線段以及網(wǎng)絡為均勻度量空間的情形。在線段網(wǎng)絡上給出了問題的下界,設計了RePlan算法并且給出了算法的競爭比;在均勻度量空間上給出了問題的下界,設計了貪婪算法并且分析了算法的競爭比。通過比較分析發(fā)現(xiàn),預知信息雖然可以提高在線服務器的競爭性能,但是在線服務器的表現(xiàn)還要受到網(wǎng)絡結(jié)構的影響。4)研究了基于服務時間約束的在線Prize-Collecting旅行商問題。由于現(xiàn)實生活中考慮單一目標的情形比較少,大多數(shù)的服務人員或者企業(yè)都希望增加利潤的同時減少服務成本,本部分結(jié)合顧客等待心理,將服務時間約束引入到在線Prize-Collecting旅行商問題中。通過在一般網(wǎng)絡上的分析發(fā)現(xiàn),不存在具有常數(shù)競爭比的在線策略,因而對網(wǎng)絡進行了限制。在線段網(wǎng)絡上分析了問題的下界,設計了CMC算法并且分析了算法的競爭比;在均勻度量空間上分析了問題的下界,設計了CGA算法并且給出了算法的競爭比。本文的研究成果,一方面可以為現(xiàn)實生活中的快餐送餐,快遞取件,出租車等上門服務提供指導,使其提高服務效率,提升顧客滿意度;另一方面由于綜合考慮了多種目標函數(shù)下的基于服務時間約束的在線旅行商問題,因此可以豐富在線旅行商問題的研究。
【學位授予單位】：西安交通大學
【學位級別】：博士
【學位授予年份】：2017
【分類號】：F224;F724.6;F592.6

【相似文獻】

相關期刊論文 前10條

1 楊國興;;一種多出發(fā)點多旅行商問題到旅行商問題的轉(zhuǎn)換[J];系統(tǒng)工程理論方法應用;1993年03期

2 蘇麗杰,聶義勇;現(xiàn)實旅行商問題[J];小型微型計算機系統(tǒng);2005年04期

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

4 馬良,王龍德;旅行商問題在航標巡檢中的應用[J];運籌與管理;1993年02期

5 楊忠,鮑明,張阿舟;求解中國旅行商問題的新結(jié)果[J];數(shù)據(jù)采集與處理;1993年03期

6 高尚;解旅行商問題的混沌蟻群算法[J];系統(tǒng)工程理論與實踐;2005年09期

7 李妍峰;李軍;高自友;;時變網(wǎng)絡環(huán)境下旅行商問題研究[J];系統(tǒng)工程學報;2010年05期

8 張德富;顧衛(wèi)剛;;解旅行商問題的一種有效方法[J];南京大學學報(自然科學版);1993年02期

9 趙玲,劉三陽;基于幾何結(jié)構的求解旅行商問題的蟻群算法[J];蘇州科技學院學報;2005年03期

10 郭靖揚;;旅行商問題概述[J];大眾科技;2006年08期

相關會議論文 前10條

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

2 張雷;鄭維敏;;廣義旅行商問題、放映員問題和一類調(diào)度模型[A];1996年中國控制會議論文集[C];1996年

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

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

5 李大衛(wèi);王夢光;;熱軋調(diào)度與多旅行商問題[A];1996年中國控制會議論文集[C];1996年

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

7 馮純伯;蔣珉;;應用模擬電場法解旅行商問題[A];1993年控制理論及其應用年會論文集[C];1993年

8 李麗;程玉榮;牛奔;;離散人工蜂群算法求解旅行商問題[A];第十三屆中國管理科學學術年會論文集[C];2011年

9 孫啟瑞;李俊;丁健;戴先中;;新型訪問域部分重疊的多旅行商問題的GA求解[A];2013年中國智能自動化學術會議論文集（第四分冊）[C];2013年

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

相關博士學位論文 前4條

1 張夢穎;不確定因素下路徑規(guī)劃問題研究[D];中國科學技術大學;2016年

2 溫新剛;基于服務時間約束的在線旅行商問題研究[D];西安交通大學;2017年

3 譚陽;求解廣義旅行商問題的若干進化算法研究[D];華南理工大學;2013年

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

相關碩士學位論文 前10條

1 劉欣欣;旅行商問題的基因片段插入算法研究[D];閩南師范大學;2015年

2 陳玲;基于PSO-GA混合算法的時間優(yōu)化的旅行商問題的研究[D];合肥工業(yè)大學;2015年

3 趙麗娜;帶油耗的單商品取送貨旅行商問題研究[D];沈陽師范大學;2016年

4 毛巍;一種新的改進人工蜂群算法及其在旅行商問題中的應用[D];四川理工學院;2016年

5 盧雨瀟;基于多頭絨泡菌模型的優(yōu)化蟻群算法及其在旅行商問題中的運用[D];西南大學;2016年

6 肖聰;農(nóng)產(chǎn)品配送中的流旅行商問題及啟發(fā)式算法的研究[D];吉林農(nóng)業(yè)大學;2016年

7 孫文成;基于多目標方法的旅行商問題復雜度研究[D];大連理工大學;2016年

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

9 黃厚生;求解旅行商問題的新方法研究[D];天津大學;2005年

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

，

本文編號：1323771