基于服務時間約束的在線旅行商問題研究.pdf

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

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

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

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

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