针对现实中的快餐送餐,快递收件员取件以及出租车等上门服务中存在的提前预订和顾客等待心理,探讨了基于服务时间约束的在线旅行商问题;并分别根据服务目标是最小化成本,最大化利润还是综合考虑两种目标的情形下对问题进行了分析。论文主要做了以下四方面的工作:1)研究了基于预知信息的在线Nomadic旅行商问题。针对现实中服务人员进行服务之后不必返回出发点的现象,将服务预订通过预知信息引入到旅行商问题当中,探讨了当服务器的目标为使成本尽可能小在线旅行商问题,并且对问题进行了竞争分析。通过构建特殊的网络结构给出了问题的下界,并且分别在直线网络上设计了ENO-dd算法,分析了算法的竞争比;在一般网络上设计了GTR-dd算法,给出了算法的竞争比。通过比较分析发现,在线服务器的竞争性能与预知信息具有正向关系。同时预知信息量的多少还控制着问题的占线性。2)研究了基于服务选择和时间约束的在线旅行商问题。考虑到现实中的顾客等待服务的等待心理以及顾客满意度,将服务时间约束引入到具有服务选择性的在线旅行商问题中。旅行商如果没有在规定的时间约束内对服务请求进行服务,则会产生惩罚。现实中惩罚可以表现为名誉受损或者是服务费用增加等,此惩罚进入到服务器的服务成本。在线服务器的目标为使服务成本尽可能小。通过对该问题在一般网络上的分析发现,不存在具有常数竞争比的确定性和随机性在线算法。因此对网络进行了限制,考虑线段网络上该问题的下界并且设计了Conjecture算法,给出了算法的竞争比。3)研究了基于预知信息和服务时间约束的在线旅行商问题。考虑到等待服务的顾客等待心理以及服务的提前预订,将服务时间约束引入到基于预知信息的在线旅行商问题当中。服务器的服务目标为尽可能多的在服务时间约束内服务需求。通过在一般网络上对问题的分析发现不存在具有常数竞争比的在线算法,因而分别考虑了网络为一条线段以及网络为均匀度量空间的情形。在线段网络上给出了问题的下界,设计了RePlan算法并且给出了算法的竞争比;在均匀度量空间上给出了问题的下界,设计了贪婪算法并且分析了算法的竞争比。通过比较分析发现,预知信息虽然可以提高在线服务器的竞争性能,但是在线服务器的表现还要受到网络结构的影响。4)研究了基于服务时间约束的在线Prize-Collecting旅行商问题。由于现实生活中考虑单一目标的情形比较少,大多数的服务人员或者企业都希望增加利润的同时减少服务成本,本部分结合顾客等待心理,将服务时间约束引入到在线Prize-Collecting旅行商问题中。通过在一般网络上的分析发现,不存在具有常数竞争比的在线策略,因而对网络进行了限制。在线段网络上分析了问题的下界,设计了CMC算法并且分析了算法的竞争比;在均匀度量空间上分析了问题的下界,设计了CGA算法并且给出了算法的竞争比。本文的研究成果,一方面可以为现实生活中的快餐送餐,快递取件,出租车等上门服务提供指导,使其提高服务效率,提升顾客满意度;另一方面由于综合考虑了多种目标函数下的基于服务时间约束的在线旅行商问题,因此可以丰富在线旅行商问题的研究。