论文部分内容阅读
本学位论文旨在从算法设计与分析的角度研究车辆调度问题(Vehicle Scheduling Problem, VSP)、分群旅行商问题(Clustered Traveling Salesman Problem, CTSP)和在线旅行商问题(Online Traveling Salesman Problem, OLTSP)等一些路线问题。全文共分五章。第一章首先介绍本文问题的研究背景,其次引入本文涉及的一些基本概念,然后给出本文问题的数学描述,最后综述本文问题及相关问题的研究现状。第二章考虑树形和圈形网络上含释放时间和服务时间约束的单机VSP问题,目标为极小化时间表长。探讨该问题的两种形式：返回型和不返回型。返回型时间表长定义为机器服务完所有客户后返回其初始出发位置的时间,不返回型时间表长则定义为所有客户的最大完工时间。当网络结构为树时,对返回型和不返回型单机VSP问题分别给出了一个9/5和一个27/14一近似算法；当网络结构为圈时,对单机VSP问题的两种形式分别给出了一个12/7一近似算法。第三章考虑线形网络上含释放时间和服务时间约束的单机分群VSP问题。若干客户分布在一条直线上,它们被划分成若干个连续子集,每个子集称为一个群。一台机器服务所有客户,且要求每个子集内的客户连续服务。问题目标亦为极小化时间表长。对每个客户服务时间为零的情形,证明了两种形式均可在O(n2)时间内解决。对每个客户服务时间任意的情形,就返回型和不返回型,分别给出了一个16/9和一个13/7一近似算法。第四章考虑CTSP问题。给定一个完全无向图,其顶点集被划分成若干个子集。探讨该问题的两种形式：返回型和不返回型,其目标分别是计算一条最短环游和一条最短路,使得该环游和该路经过所有顶点,且每个子集内的顶点连续经过。对旅行商进入和离开每个子集的顶点均可以在其内任意选择的情形,就返回型和不返回型形式,分别给出了一个13/6和一个33/14一近似算法。第五章考虑在线QATSP (Quota Asymmetric TSP)和在线MATSP (Multiple Asymmetric TSP)(?)司题。问题的输入由一个拟度量空间和一个以在线形式出现的请求序列组成,其中每个请求由释放时间、空间位置和权重唯一指定。在线QATSP问题的目标是,极小化机器服务了某些请求,使得它们的权重之和至少为预先给定的某个配额,且返回到其初始出发位置的时间；在线MATSP问题(此时有多台机器,且每个请求仅由释放时间和空间位置指定)的目标是,极小化所有请求均被服务完且所有机器都已返回到其初始出发位置的时间。探讨这两个问题的下界与在线算法。对在线QATSP问题,证明了其下界为2,并给出了一个(1+ρ)一竞争比算法,其中ρ为求解相应无释放时间离线问题的近似比；对在线MATSP问题,证明了其下界为3+(?)/2≈2.618,并给出了一个竞争比算法,其中ρ如前定义。