基于服務(wù)時(shí)間約束的在線(xiàn)旅行商問(wèn)題研究.pdf

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

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

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

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

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