Approximation algoirithms for route optimization problems : exploiting geometric structures and application to large scale problems

点击翻译按钮获取中文摘要

Starting from the polynomial time approximation scheme of Arora for the traveling salesman problem in the plane, we aimed at applying this theoretical result to practical solution methods and investigated a number of approaches. Main achievements are summarized as follows.(1) Efficient implementation of Arora's dynamic programming : based on the observation that each subproblem in his dynamic programming formulation can be compactly represented by a binary string based on the one-to-one correspondence between subproblems and well-formed parenthesis, we developed a fast scheme that maps a subproblem to its child subproblems. Using this scheme, we achieved two orders of magnitude speed up over a naive implementation. This enabled us to experiment on various uses of Aroras scheme.(2) Introducing the concept of Catalan decomposition and developing a dynamic programming scheme based on it : We replaced the rectangular decomposition of Arora by a topological decomposition of a graph and applied the implementation scheme of (1).(3) Development of alternating cycles contribution method : Given a tour to be improved (principal tour) and other tours for references (contributing tours), we extract the difference between the principal tour and each contributing tour in the form of a set of alternating cycles. We than select some of these alternating cycles, merge them with the principal tour and obtain the optimal tour in the resulting graph, hoping to get an improvement over the principal tour. The selection of alternating cycles is based on the flip gain of each cycle and the tractability of the resulting graph when all the selected cycles are added to the principal tour.(4) Development of boosted chained Lin-Kernihan heuristic : We applied the methods of (2) and (3) to the chained Lin-Kernighan heuristic and obtained a significant performance improvement.