Design And Analysis Of Exact Algorithms And Heuristics For The Min-Max Cycle Cover Problem

The Cycle Cover problem is a classical combinatorial optimization problem,which has attracted much attention from researchers in recent years.The problem finds wide applications in many fields such as wireless sensor networks,logistics systems,and vehicle scheduling.For example,the Cycle Cover problem can help to collect sensor data by using mobile receivers in wireless sensor networks,and to plan disaster rescue path of UAV(Unmanned Aerial Vehicle),etc.These application problems can be reduced to different types of the Cycle Cover problem.In general,the Cycle Cover problem can be divided into two types,that is,the Min-Max Cycle Cover problem and the Minimum Cycle Cover problem.This thesis focuses on the Min-Max Cycle Cover Problem(MMCCP).At the current time,the existing research for MMCCP mainly focuses on the aspect of approximation algorithms,lacking the results of exact algorithms.In this thesis,we give the first non-trivial exact algorithm for MMCCP.The first part of the thesis is about the design and analysis of exact algorithms for the MMCCP problem.According to the combinatorial characteristics of MMCCP,the thesis designs the first non-trivial exact algorithm for MMCCP,based on the dynamic programming strategy.The time complexity of the algorithm is O*(3n),The algorithm uses two stages to find an optimal solution to MMCCP.In the first stage,the algorithm performs the preprocessing of the problem input.In the second stage,the algorithm finds an optimal solution to the problem.The thesis proves that the time complexity of the above dynamic programming algorithm is 0*(3n),which is significantly better than the time complexity O*(knn!)of the enumeration algorithm for MMCCP based on the brute force search strategy.Meanwhile,the thesis also designs an exact algorithm for MMCCP based on the branch-and-bound strategy.In the worst case,the branchand-bound algorithm will search the entire state space,resulting in the worst-case time complexity 0*(2(k-1)n).Although the time complexity of the branch-and-bound algorithm is worse than that of the dynamic programming algorithm,the branch-andbound algorithm usually has much better practical performance relative to its theoretical worst-case time complexity.This is because the branch-and-bound algorithm adopts the pruning strategy,and the worst-case scenario of "no pruning at all" is almost impossible to happen in practice.Finally,the proposed dynamic programming algorithm is extended to deal with the single-rooted MMCCP problem and the rooted MMCCP problem.The second part of the thesis is about the design of several heuristic algorithms for MMCCP and their experimental evaluation.The disadvantage of exact algorithms is that they can only solve the problem in practice when the input size of the problem is small.When the problem’s input size becomes large,"combinatorial explosion" will occur,making it impossible for an exact algorithm to find an optimal solution in a practically acceptable time.Therefore,when dealing with large scale problems,heuristic algorithms are usually used to find approximate solutions.In the thesis,a general framework for designing heuristic algorithms for MMCCP is presented.According to this framework,four heuristic algorithms for MMCCP are designed.Inspired by the exact algorithm for MMCCP presented in the first part of the thesis,the solving procedure of the heuristic algorithms for MMCCP is also divided into two stages.The first stage is set partitioning stage,which divides all the n vertices in the input graph into k subsets.The second stage is the solving stage,which finds a shortest TSP tour for each subset obtained in the first stage.By using different classical algorithms in these two stages,several types of heuristic algorithms for MMCCP can be obtained.Finally,the thesis evaluates the performance of the above heuristic algorithms by using the control variable method on randomly generated instances.Experimental results show that the heuristic algorithms have good practical performance,validating the effect of the heuristic rules proposed in the set partitioning stage.