發(fā)布時間：2017-12-23 11:58

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

  更多相關(guān)文章： 服務(wù)時間約束 旅行商問題 在線算法 競爭分析

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

【相似文獻】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號：1323771