一些路线问题的算法设计与分析
|
摘要
本学位论文旨在从算法设计与分析的角度研究车辆调度问题(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,并给出了一个竞争比算法,其中ρ如前定义。
This thesis aims to study some routing problems, focusing on the design and anal-ysis of algorithms for the vehicle scheduling problem, the clustered traveling salesman problem, the online traveling salesman problem and so on. It consists of five chapters.
In Chapter1, we introduce the background, some preliminary concepts, the formu-lations and a review about the routing problems.
In Chapter2, we consider the single vehicle scheduling problem with release and service time requirements on a tree or a cycle. The objective is to minimize the makespan. Two versions of the problem are considered. In the tour-version the makespan means the time when the vehicle returns to its initial location after serving all customers. While in the path-version the makespan refers to the maximum completion time of all customers. For the problem on a tree, we present a9/5-approximation algorithm for the tour-version and a27/14-approximation algorithm for the path-version. For the problem on a cycle, we present12/7-approximation algorithms for both versions.
In Chapter3, we discuss the single vehicle scheduling problem in which some cus-tomers with release and service time requirements, are located at the vertices of a line, and a vehicle, initially waiting at some vertex, has to serve all the customers. The cus-tomers are partitioned into several consecutive clusters, and the customers in each cluster must be served consecutively. The objective is to minimize the makespan. In the case where the service time of each customer is zero, we show that both versions can be solved in O(n2) time. In the case where the service time of each customer is given arbitrarily, we present a16/9-approximation algorithm for the tour-version and a13/7-approximation algorithm for the path-version.
In Chapter4, we address the clustered traveling salesman problem. Given a weighted undirected graph, the vertex set is partitioned into several clusters. Two kinds of objec-tives are considered. One is finding a shortest tour, the other is finding a shortest path, such that all vertices are visited and the vertices of each cluster are visited consecutively. Supposing that no starting and ending vertices of any cluster are specified, We present a13/6-approximation algorithm for the tour objective and a33/14-approximation algo- rithm for the path objective.
In Chapter5, we treat the online quota asymmetric traveling salesman problem (OL-QATSP, for short) and online multiple asymmetric traveling salesman problem (OL-MATSP, for short). The inputs of the problems consist of a quasi-metric space and a sequence of requests, where each request is specified by a release time, a point in the space and a weight. For the OL-QATSP, the objective is to minimize the time when the server has served some requests with the total weight at least a given quota, and returned to its initial location. We prove that the lower bound of the problem is2and present a (1+ρ)-competitive algorithm, where ρ is the approximation ratio of the corresponding offline problem without release times. For the OL-MATSP, in which a crew of servers are given and the requests do not have weight, the objective is to minimize the time by which all requests have been severed and all servers have returned to their initial location. We prove that the lower bound of the problem is3+(?)/2≈2.618and present a (1+ρ+2ρ/1+(?))-competitive algorithm, where the definition of ρ is similar to the previous one.
第一章首先介绍本文问题的研究背景,其次引入本文涉及的一些基本概念,然后给出本文问题的数学描述,最后综述本文问题及相关问题的研究现状。
第二章考虑树形和圈形网络上含释放时间和服务时间约束的单机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,并给出了一个竞争比算法,其中ρ如前定义。
This thesis aims to study some routing problems, focusing on the design and anal-ysis of algorithms for the vehicle scheduling problem, the clustered traveling salesman problem, the online traveling salesman problem and so on. It consists of five chapters.
In Chapter1, we introduce the background, some preliminary concepts, the formu-lations and a review about the routing problems.
In Chapter2, we consider the single vehicle scheduling problem with release and service time requirements on a tree or a cycle. The objective is to minimize the makespan. Two versions of the problem are considered. In the tour-version the makespan means the time when the vehicle returns to its initial location after serving all customers. While in the path-version the makespan refers to the maximum completion time of all customers. For the problem on a tree, we present a9/5-approximation algorithm for the tour-version and a27/14-approximation algorithm for the path-version. For the problem on a cycle, we present12/7-approximation algorithms for both versions.
In Chapter3, we discuss the single vehicle scheduling problem in which some cus-tomers with release and service time requirements, are located at the vertices of a line, and a vehicle, initially waiting at some vertex, has to serve all the customers. The cus-tomers are partitioned into several consecutive clusters, and the customers in each cluster must be served consecutively. The objective is to minimize the makespan. In the case where the service time of each customer is zero, we show that both versions can be solved in O(n2) time. In the case where the service time of each customer is given arbitrarily, we present a16/9-approximation algorithm for the tour-version and a13/7-approximation algorithm for the path-version.
In Chapter4, we address the clustered traveling salesman problem. Given a weighted undirected graph, the vertex set is partitioned into several clusters. Two kinds of objec-tives are considered. One is finding a shortest tour, the other is finding a shortest path, such that all vertices are visited and the vertices of each cluster are visited consecutively. Supposing that no starting and ending vertices of any cluster are specified, We present a13/6-approximation algorithm for the tour objective and a33/14-approximation algo- rithm for the path objective.
In Chapter5, we treat the online quota asymmetric traveling salesman problem (OL-QATSP, for short) and online multiple asymmetric traveling salesman problem (OL-MATSP, for short). The inputs of the problems consist of a quasi-metric space and a sequence of requests, where each request is specified by a release time, a point in the space and a weight. For the OL-QATSP, the objective is to minimize the time when the server has served some requests with the total weight at least a given quota, and returned to its initial location. We prove that the lower bound of the problem is2and present a (1+ρ)-competitive algorithm, where ρ is the approximation ratio of the corresponding offline problem without release times. For the OL-MATSP, in which a crew of servers are given and the requests do not have weight, the objective is to minimize the time by which all requests have been severed and all servers have returned to their initial location. We prove that the lower bound of the problem is3+(?)/2≈2.618and present a (1+ρ+2ρ/1+(?))-competitive algorithm, where the definition of ρ is similar to the previous one.
引文
[1]K. Menger, Das botenproblem. Ergebnisse Eines Mathematischen Kolloquiums, 1932,2:11-12.
[2]S.M. Johnson, Optimal two-and three-stage production schedules with setup times included. Naval Research Logistics Quarterly,1954,1:61-68.
[3]G.B. Dantzig, J.H. Ramser, The truck dispatching problem. Management Science, 1959,6:80-91.
[4]P. Brucker, Scheduling Algorithms. Springer,1995.
[5]M. Pinedo, Scheduling:Theory, Algorithms, and Systems. Springer,2001
[6]B. Chen, C.N. Potts, G.J. Woeginger, A review of machine scheduling:Complexity, algorithms and approximability. In:D.-Z. Du, P.M. Pardalos (eds.), Handbook of Combinatorial Optimization, Kluwer Academic Publisher,1998,3:21-169.
[7]唐国春,张峰,罗守成,刘丽丽,现代排序论,上海科学普及出版社,2003.
[8]C.H. Papadimitriou, K. Steiglitz, Combinatorial optimization:Algorithms and com-plexity. Prentice Hall, Englewood Cliffs,1982.
[9]S. Cook, The complexity of theorem proving procedures. In:Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, ACM-Press, New York,1971, 151-158.
[10]M.R. Garey, D.S. Johnson, Computers and intractability:A guide to the theory of NP-completeness. Freeman, San Francisco,1979.
[11]刑文训,谢金星,现代最优化算法(第二版),清华大学出版社,2005.
[12]H. Psaraftis, M. Solomon, T. Magnanti, T.-U. Kim, Routing and scheduling on a shoreline with release times. Management Science,1990,36:212-223.
[13]Y. Karuno, H. Nagamochi, T. Ibaraki, Vehicle scheduling on a tree with release and handling times. Annals of Operations Research,1997,69:193-207.
[14]Y. Karuno, H. Nagamochi, T. Ibaraki, Vehicle scheduling on a tree to minimize maximum lateness. Journal of Operations Research Society of Japan,1996,39:345-355.
[15]J.N. Tsitsiklis, Special cases of traveling salesman and repairman problems with time windows. Networks,1992,22:263-282.
[16]M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research,1987,35:254-265.
[17]B. Golden, S. Raghavan, E. Wasil (eds.), The vehicle routing problem:Latest ad-vances and new challenges. Springer,2008.
[18]J.A. Chisman, The clustered traveling salesman problem. Computers & Operations Research,1975,2:115-119.
[19]A. Weintraub, J. Aboud, C. Fernandez, G. Laporte, E. Ramirez, An emergency vehicle dispatching system for an electric utility in Chile. Journal of the Operational Research Society,1999,50:690-699.
[20]CM Liu, Clustering techniques for stock location and order-picking in a distribution center. Computers & Operationns Research,1999,26:989-1002.
[21]H. Hwang, M Lee, Order batching algorithms for a man-on-board automated stor-age and retrieval system. Engineering Costs and Production Economics,1988,13: 285-294.
[22]G. Gutin, A. Punnen (eds.), The traveling salesman problem and its variations. Kluwer Academic Publisher,2002.
[23]G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie, M. Talamo, Algorithms for the on-line traveling salesman. Algorithmica,2001,29:560-581.
[24]P. Jaillet, M. Wagner, Generalized online routing:New competitive ratios, resource augmentation and asymptotic analyses. Operations Research,2008,56:745-757.
[25]Y. Karuno, H. Nagamochi, T. Ibaraki, Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks. Networks,2002,39:203-209.
[26]D.R. Gaur, A. Gupta, R. Krishnamurti, A5/3-approximation algorithm for scheduling vehicles on a path with release and handling times. Information Processing Letters, 2003,86:87-91.
[27]B. Bhattacharya, P. Carmi, Y. Hu, Q. Shi, Single vehicle scheduling problems on path/tree/cycle networks with release and handling times. Lecture Notes in Com-puter Science,2008,5369:800-811.
[28]W. Yu, Z. Liu, Single-vehicle scheduling problems with release and service times on a line. Networks,2011,57:128-134.
[29]W. Yu, Z. Liu, Vehicle routing problems on a line-shaped network with release time constraints. Operations Research Letters,2009,37:85-88.
[30]Y. Karuno, H. Nagamochi,2-Approximation algorithms for the multi-vehicle schedul-ing problem on a path with release and handling times. Discrete Applied Mathemat-ics,2003,129:433-447.
[31]Y. Karuno, H. Nagamochi, An approximability result of the multi-vehicle scheduling problem on a path with release and handling times. Theoretical Computer Science, 2004,312:267-280.
[32]F. Afrati, S. Cosmadakis, C.H. Papadimitriou, G. Papageorgiou, N. Papakostanti-nou, The complexity of the traveling repairman problem. Informatique Theorique et Applications,1986,20:79-87.
[33]G.H. Young, C. Chen, Single-vehicle scheduling with time window constraints. Jour-nal of Scheduling,1999,2:175-187.
[34]I. Averbakh, O. Berman, Routing and location-routing p-delivery men problems on a path. Transportation Science,1994,28:162-166.
[3-5]D. Simchi-Levi, O. Berman, Minimizing the total flow time of n jobs on a network. ⅡE Transactions,1991,23:236-244.
[36]B. Wu, Polynomial time algorithms for some minimum latency problems. Information Processing Letters,2000,75:225-229.
[37]A. Garcia, P. Jodra, J. Tejel, An efficient algorithm for on-line searching of minima in Monge path-decomposable tridimensional arrays. Information Processing Letters, 1998,68:3-9.
[38]A. Garcia, P. Jodra, J. Tejel, A note on the traveling repairman problem. Networks, 2002,40:27-31.
[39]S. Coene, F.C.R. Spieksma, Profit-based latency problems on the line. Operations Research Letters,2008,36:333-337.
[40]H. Nagamochi, K. Mochizuki, T. Ibaraki, Complexity of the single vehicle scheduling problems on a graphs. Information Systems and Operations Research,1997,35:256-276.
[41]J.E. Augustine, S. Seiden, Linear time approximation schemes for vehicle scheduling problems. Theoretical Computer Science,2004,324:147-160.
[42]B. Bhattacharya, Y. Hu, Approximation algorithms for the multi-vehicle scheduling problem. Lecture Notes in Computer Science,2010,6507:192-205.
[43]I. Averbakh, O. Berman, A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree. Discrete Applied Mathematics,1996,68:17-32.
[44]I. Averbakh, O. Berman, (p-1)/(p+1)-approximate algorithm for p-traveling sales-men problems on a tree with minmax objective. Discrete Applied Mathematics,1997, 75:201-216.
[45]H. Nagamochi, K. Okada, A faster 2-approximation algorithm for the minmax ptrav-eling salesmen problem on a tree. Discrete Applied Mathematics,2004,140:103-114.
[46]H. Nagamochi, K. Okada, Polynomial time 2-approximation algorithms for the min-max subtree cover problem. Lecture Notes in Computer Science,2003,2906:138-147.
[47]E. Minieka, The delivery man problem on a tree network. Annals of Operations Research,1989,18:261-266.
[48]R. Sitters, The minimum latency problem is NP-hard for weighted trees. In:Proceed-ings of the 9th Conference on Integer Programming and Combinatorial Optimization (IPCO), Lecture Notes in Computer Science,2002,2337:230-239.
[49]I. Averbakh, O. Berman, Sales-delivery man problems on treelike networks. Net-works,1995,25:45-58.
[50]N. Guttmann-Beck, R. Hassin, S. Khuller, B. Raghavachari, Approximation algo-rithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica,2000,28:422-437.
[51]E. Arkin, R. Hassin, L. Klein, Restricted delivery problems on a network. Network, 1997,29:205-216.
[52]S. Anily, J. Bramel, A. Hertz, A5/3-approximation algorithm for the clustered travel-ing salesman tour and path problems. Operations Research Letters,1999,24:29-35.
[53]N. Christofides, Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh,1976.
[54]J. A. Hoogeveen, Analysis of Christofides'heuristic:Some paths are more difficult than cycles. Operations Research Letters,1991,10:291-295.
[55]M. Gendreau, G. Laporte, A. Hertz, An approximation algorithm for the traveling salesman problem with backhauls. Operations Research,1997,45:639-641.
[56]B. Awerbuch, Y. Azar, A. Blum, S. Vempala, New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. SIAM Journal on Computing, 1998,28:254-262.
[57]G. Ausiello, S. Leonardi, A. Marchetti-Spaccamela, On salesmen, repairmen, spiders, and other traveling agents. In:G. Bongiovanni, G. Gambosi, R. Petreschi (eds.), in: Proceedings of the 4th Italian Conference on Algorithms and Complexity, Lecture Notes in Computer Science,2000,1767:1-16.
[58]G.N. Frederickson, M.S. Hecht, C.E. Kim, Approximation algorithms for some rout-ing problems. SLAM Journal on Computing,1978,7:178-193.
[59]A.M. Frieze, G. Galbiati, F. Mamoli, On the worst-case performance of some algo-rithms for the asymmetric traveling salesman problem. Networks,1982,12:23-39.
[60]H. Kaplan, M. Lewenstein, N. Shafrir, M. Sviridenko, Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. Journal of the Association for Computing Machinery,2005,52:602-626.
[61]A.M. Frieze, An extension of Christofides heuristic to the k-person travelling sales-man problem. Discrete Applied Mathematics,1983,6:79-83.
[62]S. Rathinam, R. Sengupta, S. Darbha, A resource allocation algorithm for multi-vehicle systems with non holonomic constraints. IEEE Transactions on Automation Science and Engineering,2006,4:98-104.
[63]Z. Xu, L. Xu, B. Rodrigues, An analysis of the extende Christofides heuristic for the k-depot TSP. Operations Research Letters,2011, doi:10.1016/j.orl.2011.03.002.
[64]H.A. Eiselt, M. Gendreau, G. Laporte, Arc routing problems, part Ⅰ:The Chinese postman problem. Operations Research,1995,43:231-242.
[65]H.A. Eiselt, M. Gendreau, G. Laporte Arc routing problems, part Ⅱ:The rural postman problem. Operations Research,1995,43:399-414.
[66]G.N. Frederickson, Approximation algorithms for some postman problems. Journal of the Association for Computing Machinery,1979,26:538-554.
[67]P. Jaillet, M. R. Wagner, Online routing problems:Value of advanced information as improved competitive ratios. Transportation Science,2006,40:200-210.
[68]G. Ausiello, M. Demange, L. Laura, V. Paschos, Algorithms for the on-line quota traveling salesman problem. Information Processing Letters,2004,92:89-94.
[69]N. Ascheuer, S.O. Krumke, J. Rambau, Online dial-a-ride problems:Minimizing the completion time. In:H. Reichel, S. Tison (eds.), in:Proceedings of the 17th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science,2000,1770:639-650.
[70]M. Lipmann, On-line routing problems. PhD Thesis, Technische Universiteit Eind-hoven,2003.
[71]M. Blom, S.O. Krumke, W.E. de Paepe, L. Stougie, The online TSP against fair adversaries. INFORMS Journal on Computing,2001,13:138-148.
[72]若干网络排序问题的算法和复杂性研究,博士论文,华东理工大学应用数学研究所,2010.
[73]V. Bonifaci, Models and algorithms for online server routing. PhD thesis, Technische Universiteit Eindhoven,2007.
[74]G. Ausiello, V. Bonifaci, L. Laura, The on-line asymmetric traveling salesman prob-lem. Journal of Discrete Algorithms,2008,6:290-298.
[75]V. Bonifaci, M. Lipmann, L. Stougie, Online multi-server dial-a-ride problems. Tech-nical Report 02-06, Department of Computer and Systems Science, University of Rome "La Sapienza", Rome, Italy,2006.
[76]V. Bonifaci, L. Stougie, On-line k-server routing problems. Theory of Computing Systems,2009,45:470-485.
[77]E. Feuersteina, L. Stougie, On-line single-server dial-a-ride problems. Thoretical Computer Science,2001,268:91-105.
[78]S.O. Krumke, W.E. de Paepe, D. Poensgen, L. Stougie, News from the on-line trav-eling repairman. Theoretical Computer Science,2003,295:279-294.
[79]S.O. Krumke, W.E. de Paepe, D. Poensgen, L. Stougie, Erratum to "News from the online traveling repairman" [Theoret. Comput. Sci.295 (1-3) (2003) 279-294]. Theoretical Computer Science,2006,352:347-348.
[80]S.O. Krumke, Online optimization:Competitive analysis and beyond. Habilitation Thesis, Technical University of Berlin,2001.
[81]S.O. Krumke, W.E. de Paepe, D. Poensgen, M. Lipmann, A. Marchetti-Spaccamela, L. Stougie, On minimizing the maximum flow time in the online dial-a-ride prob-lem. In:T. Erlebach, G. Persiano (eds.), in:Proceedings of the 3rd Workshop on Approximation and Online Algorithms, Lecture Notes in Computer Science,2006, 3879:258-269.
[82]S.O. Krumke, L. Laura, M. Lipmann, A. Marchetti-Spaccamela, W.E. de Paepe, D. Poensgen, L. Stougie, Non-abusiveness helps:an O(1)-competitive algorithm for minimizing the maximum flow time in the online traveling salesman problem. In:K. Jansen, S. Leonardi, V.V. Vazirani (eds.), in:Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, Lecture Notes in Computer Science,2002,2462:200-214.
D. Hauptmeier, S.O. Krumke, J. Rambau, The online dial-a-ride problem under reasonable load. In:G. Bongiovanni, G. Gambosi, R. Petreschi (eds.), in:Proceed-ings of the 4th Italian Conference on Algorithms and Complexity, Lecture Notes in Computer Science,2000,1767:125-136.
[84]M. Lipmann, X. Lu, W.E. de Paepe, R.A. Sitters, L. Stougie, On-line dial-aride problems under a restricted information model. Algorithmica,2004,40:319-329.
[85]G. Laporte, U. Palekar, Some applications of the clustered travelling salesman prob-lem. Journal of the Operational Research Society,2002,53:972-976.
[86]E.L. Lawler, J.K. Lenstra, A. Rinnooy Kan, D.B. Shmoys, The traveling salesman problem:A guided tour of combinatorial optimization. Wiley, Chichester,1985.
[87]B. Korte, J. Vygen, Combinatorial Optimization:Theory and Algorithms (3rd Edi-tion). Springer,2006.
[88]S. Sahni, T.F. Gonzalez, P-complete approximation problems. Journal of the Asso-ciation for Computing Machinery,1976,23:555-565.
[89]G. Ausiello, V. Bonifaci, L. Laura, The online prize-collecting traveling salesman problem. Information Processing Letters,2008,107:199-204.
[90]P. Jaillet, X. Lu, Online traveling salesman problems with service flexibility. Net-works,2011,58:137-146.
[2]S.M. Johnson, Optimal two-and three-stage production schedules with setup times included. Naval Research Logistics Quarterly,1954,1:61-68.
[3]G.B. Dantzig, J.H. Ramser, The truck dispatching problem. Management Science, 1959,6:80-91.
[4]P. Brucker, Scheduling Algorithms. Springer,1995.
[5]M. Pinedo, Scheduling:Theory, Algorithms, and Systems. Springer,2001
[6]B. Chen, C.N. Potts, G.J. Woeginger, A review of machine scheduling:Complexity, algorithms and approximability. In:D.-Z. Du, P.M. Pardalos (eds.), Handbook of Combinatorial Optimization, Kluwer Academic Publisher,1998,3:21-169.
[7]唐国春,张峰,罗守成,刘丽丽,现代排序论,上海科学普及出版社,2003.
[8]C.H. Papadimitriou, K. Steiglitz, Combinatorial optimization:Algorithms and com-plexity. Prentice Hall, Englewood Cliffs,1982.
[9]S. Cook, The complexity of theorem proving procedures. In:Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, ACM-Press, New York,1971, 151-158.
[10]M.R. Garey, D.S. Johnson, Computers and intractability:A guide to the theory of NP-completeness. Freeman, San Francisco,1979.
[11]刑文训,谢金星,现代最优化算法(第二版),清华大学出版社,2005.
[12]H. Psaraftis, M. Solomon, T. Magnanti, T.-U. Kim, Routing and scheduling on a shoreline with release times. Management Science,1990,36:212-223.
[13]Y. Karuno, H. Nagamochi, T. Ibaraki, Vehicle scheduling on a tree with release and handling times. Annals of Operations Research,1997,69:193-207.
[14]Y. Karuno, H. Nagamochi, T. Ibaraki, Vehicle scheduling on a tree to minimize maximum lateness. Journal of Operations Research Society of Japan,1996,39:345-355.
[15]J.N. Tsitsiklis, Special cases of traveling salesman and repairman problems with time windows. Networks,1992,22:263-282.
[16]M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research,1987,35:254-265.
[17]B. Golden, S. Raghavan, E. Wasil (eds.), The vehicle routing problem:Latest ad-vances and new challenges. Springer,2008.
[18]J.A. Chisman, The clustered traveling salesman problem. Computers & Operations Research,1975,2:115-119.
[19]A. Weintraub, J. Aboud, C. Fernandez, G. Laporte, E. Ramirez, An emergency vehicle dispatching system for an electric utility in Chile. Journal of the Operational Research Society,1999,50:690-699.
[20]CM Liu, Clustering techniques for stock location and order-picking in a distribution center. Computers & Operationns Research,1999,26:989-1002.
[21]H. Hwang, M Lee, Order batching algorithms for a man-on-board automated stor-age and retrieval system. Engineering Costs and Production Economics,1988,13: 285-294.
[22]G. Gutin, A. Punnen (eds.), The traveling salesman problem and its variations. Kluwer Academic Publisher,2002.
[23]G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie, M. Talamo, Algorithms for the on-line traveling salesman. Algorithmica,2001,29:560-581.
[24]P. Jaillet, M. Wagner, Generalized online routing:New competitive ratios, resource augmentation and asymptotic analyses. Operations Research,2008,56:745-757.
[25]Y. Karuno, H. Nagamochi, T. Ibaraki, Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks. Networks,2002,39:203-209.
[26]D.R. Gaur, A. Gupta, R. Krishnamurti, A5/3-approximation algorithm for scheduling vehicles on a path with release and handling times. Information Processing Letters, 2003,86:87-91.
[27]B. Bhattacharya, P. Carmi, Y. Hu, Q. Shi, Single vehicle scheduling problems on path/tree/cycle networks with release and handling times. Lecture Notes in Com-puter Science,2008,5369:800-811.
[28]W. Yu, Z. Liu, Single-vehicle scheduling problems with release and service times on a line. Networks,2011,57:128-134.
[29]W. Yu, Z. Liu, Vehicle routing problems on a line-shaped network with release time constraints. Operations Research Letters,2009,37:85-88.
[30]Y. Karuno, H. Nagamochi,2-Approximation algorithms for the multi-vehicle schedul-ing problem on a path with release and handling times. Discrete Applied Mathemat-ics,2003,129:433-447.
[31]Y. Karuno, H. Nagamochi, An approximability result of the multi-vehicle scheduling problem on a path with release and handling times. Theoretical Computer Science, 2004,312:267-280.
[32]F. Afrati, S. Cosmadakis, C.H. Papadimitriou, G. Papageorgiou, N. Papakostanti-nou, The complexity of the traveling repairman problem. Informatique Theorique et Applications,1986,20:79-87.
[33]G.H. Young, C. Chen, Single-vehicle scheduling with time window constraints. Jour-nal of Scheduling,1999,2:175-187.
[34]I. Averbakh, O. Berman, Routing and location-routing p-delivery men problems on a path. Transportation Science,1994,28:162-166.
[3-5]D. Simchi-Levi, O. Berman, Minimizing the total flow time of n jobs on a network. ⅡE Transactions,1991,23:236-244.
[36]B. Wu, Polynomial time algorithms for some minimum latency problems. Information Processing Letters,2000,75:225-229.
[37]A. Garcia, P. Jodra, J. Tejel, An efficient algorithm for on-line searching of minima in Monge path-decomposable tridimensional arrays. Information Processing Letters, 1998,68:3-9.
[38]A. Garcia, P. Jodra, J. Tejel, A note on the traveling repairman problem. Networks, 2002,40:27-31.
[39]S. Coene, F.C.R. Spieksma, Profit-based latency problems on the line. Operations Research Letters,2008,36:333-337.
[40]H. Nagamochi, K. Mochizuki, T. Ibaraki, Complexity of the single vehicle scheduling problems on a graphs. Information Systems and Operations Research,1997,35:256-276.
[41]J.E. Augustine, S. Seiden, Linear time approximation schemes for vehicle scheduling problems. Theoretical Computer Science,2004,324:147-160.
[42]B. Bhattacharya, Y. Hu, Approximation algorithms for the multi-vehicle scheduling problem. Lecture Notes in Computer Science,2010,6507:192-205.
[43]I. Averbakh, O. Berman, A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree. Discrete Applied Mathematics,1996,68:17-32.
[44]I. Averbakh, O. Berman, (p-1)/(p+1)-approximate algorithm for p-traveling sales-men problems on a tree with minmax objective. Discrete Applied Mathematics,1997, 75:201-216.
[45]H. Nagamochi, K. Okada, A faster 2-approximation algorithm for the minmax ptrav-eling salesmen problem on a tree. Discrete Applied Mathematics,2004,140:103-114.
[46]H. Nagamochi, K. Okada, Polynomial time 2-approximation algorithms for the min-max subtree cover problem. Lecture Notes in Computer Science,2003,2906:138-147.
[47]E. Minieka, The delivery man problem on a tree network. Annals of Operations Research,1989,18:261-266.
[48]R. Sitters, The minimum latency problem is NP-hard for weighted trees. In:Proceed-ings of the 9th Conference on Integer Programming and Combinatorial Optimization (IPCO), Lecture Notes in Computer Science,2002,2337:230-239.
[49]I. Averbakh, O. Berman, Sales-delivery man problems on treelike networks. Net-works,1995,25:45-58.
[50]N. Guttmann-Beck, R. Hassin, S. Khuller, B. Raghavachari, Approximation algo-rithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica,2000,28:422-437.
[51]E. Arkin, R. Hassin, L. Klein, Restricted delivery problems on a network. Network, 1997,29:205-216.
[52]S. Anily, J. Bramel, A. Hertz, A5/3-approximation algorithm for the clustered travel-ing salesman tour and path problems. Operations Research Letters,1999,24:29-35.
[53]N. Christofides, Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh,1976.
[54]J. A. Hoogeveen, Analysis of Christofides'heuristic:Some paths are more difficult than cycles. Operations Research Letters,1991,10:291-295.
[55]M. Gendreau, G. Laporte, A. Hertz, An approximation algorithm for the traveling salesman problem with backhauls. Operations Research,1997,45:639-641.
[56]B. Awerbuch, Y. Azar, A. Blum, S. Vempala, New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. SIAM Journal on Computing, 1998,28:254-262.
[57]G. Ausiello, S. Leonardi, A. Marchetti-Spaccamela, On salesmen, repairmen, spiders, and other traveling agents. In:G. Bongiovanni, G. Gambosi, R. Petreschi (eds.), in: Proceedings of the 4th Italian Conference on Algorithms and Complexity, Lecture Notes in Computer Science,2000,1767:1-16.
[58]G.N. Frederickson, M.S. Hecht, C.E. Kim, Approximation algorithms for some rout-ing problems. SLAM Journal on Computing,1978,7:178-193.
[59]A.M. Frieze, G. Galbiati, F. Mamoli, On the worst-case performance of some algo-rithms for the asymmetric traveling salesman problem. Networks,1982,12:23-39.
[60]H. Kaplan, M. Lewenstein, N. Shafrir, M. Sviridenko, Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs. Journal of the Association for Computing Machinery,2005,52:602-626.
[61]A.M. Frieze, An extension of Christofides heuristic to the k-person travelling sales-man problem. Discrete Applied Mathematics,1983,6:79-83.
[62]S. Rathinam, R. Sengupta, S. Darbha, A resource allocation algorithm for multi-vehicle systems with non holonomic constraints. IEEE Transactions on Automation Science and Engineering,2006,4:98-104.
[63]Z. Xu, L. Xu, B. Rodrigues, An analysis of the extende Christofides heuristic for the k-depot TSP. Operations Research Letters,2011, doi:10.1016/j.orl.2011.03.002.
[64]H.A. Eiselt, M. Gendreau, G. Laporte, Arc routing problems, part Ⅰ:The Chinese postman problem. Operations Research,1995,43:231-242.
[65]H.A. Eiselt, M. Gendreau, G. Laporte Arc routing problems, part Ⅱ:The rural postman problem. Operations Research,1995,43:399-414.
[66]G.N. Frederickson, Approximation algorithms for some postman problems. Journal of the Association for Computing Machinery,1979,26:538-554.
[67]P. Jaillet, M. R. Wagner, Online routing problems:Value of advanced information as improved competitive ratios. Transportation Science,2006,40:200-210.
[68]G. Ausiello, M. Demange, L. Laura, V. Paschos, Algorithms for the on-line quota traveling salesman problem. Information Processing Letters,2004,92:89-94.
[69]N. Ascheuer, S.O. Krumke, J. Rambau, Online dial-a-ride problems:Minimizing the completion time. In:H. Reichel, S. Tison (eds.), in:Proceedings of the 17th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science,2000,1770:639-650.
[70]M. Lipmann, On-line routing problems. PhD Thesis, Technische Universiteit Eind-hoven,2003.
[71]M. Blom, S.O. Krumke, W.E. de Paepe, L. Stougie, The online TSP against fair adversaries. INFORMS Journal on Computing,2001,13:138-148.
[72]若干网络排序问题的算法和复杂性研究,博士论文,华东理工大学应用数学研究所,2010.
[73]V. Bonifaci, Models and algorithms for online server routing. PhD thesis, Technische Universiteit Eindhoven,2007.
[74]G. Ausiello, V. Bonifaci, L. Laura, The on-line asymmetric traveling salesman prob-lem. Journal of Discrete Algorithms,2008,6:290-298.
[75]V. Bonifaci, M. Lipmann, L. Stougie, Online multi-server dial-a-ride problems. Tech-nical Report 02-06, Department of Computer and Systems Science, University of Rome "La Sapienza", Rome, Italy,2006.
[76]V. Bonifaci, L. Stougie, On-line k-server routing problems. Theory of Computing Systems,2009,45:470-485.
[77]E. Feuersteina, L. Stougie, On-line single-server dial-a-ride problems. Thoretical Computer Science,2001,268:91-105.
[78]S.O. Krumke, W.E. de Paepe, D. Poensgen, L. Stougie, News from the on-line trav-eling repairman. Theoretical Computer Science,2003,295:279-294.
[79]S.O. Krumke, W.E. de Paepe, D. Poensgen, L. Stougie, Erratum to "News from the online traveling repairman" [Theoret. Comput. Sci.295 (1-3) (2003) 279-294]. Theoretical Computer Science,2006,352:347-348.
[80]S.O. Krumke, Online optimization:Competitive analysis and beyond. Habilitation Thesis, Technical University of Berlin,2001.
[81]S.O. Krumke, W.E. de Paepe, D. Poensgen, M. Lipmann, A. Marchetti-Spaccamela, L. Stougie, On minimizing the maximum flow time in the online dial-a-ride prob-lem. In:T. Erlebach, G. Persiano (eds.), in:Proceedings of the 3rd Workshop on Approximation and Online Algorithms, Lecture Notes in Computer Science,2006, 3879:258-269.
[82]S.O. Krumke, L. Laura, M. Lipmann, A. Marchetti-Spaccamela, W.E. de Paepe, D. Poensgen, L. Stougie, Non-abusiveness helps:an O(1)-competitive algorithm for minimizing the maximum flow time in the online traveling salesman problem. In:K. Jansen, S. Leonardi, V.V. Vazirani (eds.), in:Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, Lecture Notes in Computer Science,2002,2462:200-214.
D. Hauptmeier, S.O. Krumke, J. Rambau, The online dial-a-ride problem under reasonable load. In:G. Bongiovanni, G. Gambosi, R. Petreschi (eds.), in:Proceed-ings of the 4th Italian Conference on Algorithms and Complexity, Lecture Notes in Computer Science,2000,1767:125-136.
[84]M. Lipmann, X. Lu, W.E. de Paepe, R.A. Sitters, L. Stougie, On-line dial-aride problems under a restricted information model. Algorithmica,2004,40:319-329.
[85]G. Laporte, U. Palekar, Some applications of the clustered travelling salesman prob-lem. Journal of the Operational Research Society,2002,53:972-976.
[86]E.L. Lawler, J.K. Lenstra, A. Rinnooy Kan, D.B. Shmoys, The traveling salesman problem:A guided tour of combinatorial optimization. Wiley, Chichester,1985.
[87]B. Korte, J. Vygen, Combinatorial Optimization:Theory and Algorithms (3rd Edi-tion). Springer,2006.
[88]S. Sahni, T.F. Gonzalez, P-complete approximation problems. Journal of the Asso-ciation for Computing Machinery,1976,23:555-565.
[89]G. Ausiello, V. Bonifaci, L. Laura, The online prize-collecting traveling salesman problem. Information Processing Letters,2008,107:199-204.
[90]P. Jaillet, X. Lu, Online traveling salesman problems with service flexibility. Net-works,2011,58:137-146.