摘要：针对城市快递揽件服务过程中，需求事先无法预知并且每个需求服务时长不确定的情形．提出具有服务时长的在线TSP问题．分别在一般网络图上和直线上证明了此问题的竞争比下界进而在一般网络上给出PAH-ST算法，在直线上给出PQR—ST算法，并对算法进行了竞争性能分析．本文提出模型是在线TSP问题的一般形式，结论可以为快递车辆的实时调度决策提供依据．

关键词：旅行商问题 服务时长 在线算法 竞争比 

单位：西安交通大学管理学院 西安710049 西安工业大学经济管理学院 西安710032 机械制造系统工程国家重点实验室 西安710049