1、針對現(xiàn)實(shí)中的快餐送餐，快遞收件員取件以及出租車等上門服務(wù)中存在的提前預(yù)訂和顧客等待心理，探討了基于服務(wù)時(shí)間約束的在線旅行商問題；并分別根據(jù)服務(wù)目標(biāo)是最小化成本，最大化利潤還是綜合考慮兩種目標(biāo)的情形下對問題進(jìn)行了分析。論文主要做了以下四方面的工作：
　　1）研究了基于預(yù)知信息的在線Nomadic旅行商問題。針對現(xiàn)實(shí)中服務(wù)人員進(jìn)行服務(wù)之后不必返回出發(fā)點(diǎn)的現(xiàn)象，將服務(wù)預(yù)訂通過預(yù)知信息引入到旅行商問題當(dāng)中，探討了當(dāng)服務(wù)器的目標(biāo)為使成本盡可

2、能小在線旅行商問題，并且對問題進(jìn)行了競爭分析。通過構(gòu)建特殊的網(wǎng)絡(luò)結(jié)構(gòu)給出了問題的下界，并且分別在直線網(wǎng)絡(luò)上設(shè)計(jì)了ENO?dd算法，分析了算法的競爭比；在一般網(wǎng)絡(luò)上設(shè)計(jì)了GTR?dd算法，給出了算法的競爭比。通過比較分析發(fā)現(xiàn)，在線服務(wù)器的競爭性能與預(yù)知信息具有正向關(guān)系。同時(shí)預(yù)知信息量的多少還控制著問題的占線性。
　　2）研究了基于服務(wù)選擇和時(shí)間約束的在線旅行商問題。考慮到現(xiàn)實(shí)中的顧客等待服務(wù)的等待心理以及顧客滿意度，將服務(wù)時(shí)間約束引

3、入到具有服務(wù)選擇性的在線旅行商問題中。旅行商如果沒有在規(guī)定的時(shí)間約束內(nèi)對服務(wù)請求進(jìn)行服務(wù)，則會產(chǎn)生懲罰。現(xiàn)實(shí)中懲罰可以表現(xiàn)為名譽(yù)受損或者是服務(wù)費(fèi)用增加等，此懲罰進(jìn)入到服務(wù)器的服務(wù)成本。在線服務(wù)器的目標(biāo)為使服務(wù)成本盡可能小。通過對該問題在一般網(wǎng)絡(luò)上的分析發(fā)現(xiàn)，不存在具有常數(shù)競爭比的確定性和隨機(jī)性在線算法。因此對網(wǎng)絡(luò)進(jìn)行了限制，考慮線段網(wǎng)絡(luò)上該問題的下界并且設(shè)計(jì)了Conjecture算法，給出了算法的競爭比。
　　3）研究了基于預(yù)知信

4、息和服務(wù)時(shí)間約束的在線旅行商問題?？紤]到等待服務(wù)的顧客等待心理以及服務(wù)的提前預(yù)訂，將服務(wù)時(shí)間約束引入到基于預(yù)知信息的在線旅行商問題當(dāng)中。服務(wù)器的服務(wù)目標(biāo)為盡可能多的在服務(wù)時(shí)間約束內(nèi)服務(wù)需求。通過在一般網(wǎng)絡(luò)上對問題的分析發(fā)現(xiàn)不存在具有常數(shù)競爭比的在線算法，因而分別考慮了網(wǎng)絡(luò)為一條線段以及網(wǎng)絡(luò)為均勻度量空間的情形。在線段網(wǎng)絡(luò)上給出了問題的下界，設(shè)計(jì)了RePlan算法并且給出了算法的競爭比；在均勻度量空間上給出了問題的下界，設(shè)計(jì)了貪婪算法并且

5、分析了算法的競爭比。通過比較分析發(fā)現(xiàn)，預(yù)知信息雖然可以提高在線服務(wù)器的競爭性能，但是在線服務(wù)器的表現(xiàn)還要受到網(wǎng)絡(luò)結(jié)構(gòu)的影響。
　　4）研究了基于服務(wù)時(shí)間約束的在線Prize-Collecting旅行商問題。由于現(xiàn)實(shí)生活中考慮單一目標(biāo)的情形比較少，大多數(shù)的服務(wù)人員或者企業(yè)都希望增加利潤的同時(shí)減少服務(wù)成本，本部分結(jié)合顧客等待心理，將服務(wù)時(shí)間約束引入到在線 Prize-Collecting旅行商問題中。通過在一般網(wǎng)絡(luò)上的分析發(fā)現(xiàn)，不存在