旅行商问题的几个变形的近似算法研究

The traveling salesman problem (TSP) is a fundamental combinatorial optimization problem, it and its variations have a wide application in many fields. Therefore, the study on it has important theoretical value and practical significance. Based on our previous work, this project researches on the following several variations of the TSP: .(1) The clustered TSP (CTSP). In this problem the vertex set is partitioned into several clusters, and the vertices of each cluster must be visited consecutively..(2) CTSP with release and service time constraints. Here each customer has a release time before which it cannot be served, and a service time which the server has to spend in serving the customer..(3) Online CTSP. In the case of an online CTSP, decider receives the requests in an on-line way and needs to update scheduled route in an on-line way during the trip..(4) The multiple TSP. In this case, there are a number of salesmen to visit the cities. The objective is to compute a separate tour for each salesman such that the maximum tour length of all salesmen is minimized. .For the problems (1) (4), we will propose better approximation algorithms. For the problems (2) (3), which have been not studied by researchers now, we will establish reasonable mathematical models and design approximation algorithms with considerable ratios.

旅行商问题是一个基本的组合优化问题，它和它的变形在诸多领域都有着广泛应用，对其进行研究具有重要的理论价值和实际意义。本课题拟在申请人前期工作的基础上，考虑旅行商问题的几个变形：（1）分群旅行商问题。在该问题中，顶点集被划分成若干个子集（群），每个子集（群）内的顶点要求连续经过。（2）带释放时间和服务时间限制的分群旅行商问题。在该问题中，每个客户有一个释放时间，在此之前服务者不能服务该客户，同时，服务者在服务每个客户时需花费一定的服务时间。（3）在线分群旅行商问题。在该问题中，请求以实时在线的形式出现，决策者需要根据实时接收到的请求信息更新路线安排。（4）多旅行商问题。在该问题中，旅行商的个数由一个增加到多个，目标函数为极小化最长环游的长度。对问题（1）（4），拟设计性能比更好的近似算法；问题（2）（3）是我们新提出的，拟结合实际建立合理的数学模型并给出较好的求解算法。

旅行商问题是一个基本的组合优化问题，它和它的变形在诸多领域都有着广泛应用，对其进行研究具有重要的理论价值和实际意义。本课题对旅行商问题的几个变形开展了研究，具体如下：.（1）分群旅行商问题。在该问题中，顶点集被划分成若干个子集，问题的要求是计算一个环游，使得每个顶点恰好经过一次且每个子集内的顶点连续经过。.（2）单台车辆分群调度问题。在该问题中，每个顶点有一个释放时间和一个服务时间。前者的含义是每个顶点仅能在该时刻及以后方可被服务，后者的含义是每个顶点被服务时需花费一定的服务时间。.（3）多旅行商问题。在该问题中，旅行商的个数由一个增加到多个。问题的要求是计算k个环游，使得顶点集或边集等服务对象被这些环游覆盖。.对问题(1)，当旅行商个数为k时，就所有环游起点相同的情形，给出首个(2ρ+1/2-1/k)-近似算法；就所有环游起点可以任意的情形，给出首个6ρ-近似算法，这里ρ表示求解分群旅行商问题的近似比。.对问题(2)，当网络结构为线型时，给出一个7/4-近似算法，改进现有文献中的结果；当网络结构为圈型和星型时，分别首次给出一个13/7-和一个5/3-近似算法。.对问题(3)，当网络结构为无向加权图、覆盖对象为该图的整个顶点集、每个圈长不超过λ时，就目标函数为极小化圈的个数的情形，一是给出一个O(n^5)的32/7-近似算法，改进现有文献中的结果，二是给出一个新的线性规划松弛并证明其整性间隙不超过6；就目标函数为极小化所有圈长总和再加上γ倍圈的个数的情形，给出一个5-近似算法并证明其整性间隙介于2和25之间。.对问题(3)，当网络结构为无向加权图、目标函数为极小化最大圈长的情形，就覆盖对象为部分边集时，给出首个6-近似算法；就覆盖对象为整个边集时，给出首个4-近似算法。.对问题(3)，当网络结构为混合加权图、目标函数为极小化最大圈长的情形，就覆盖对象为该混合图的弧集时，给出首个37/5-近似算法；就覆盖对象为该混合图的部分边集与整个弧集时，给出首个min{33/5,(12+21α)/(2+3α)}-近似算法。