An Approximate Algorithm for Solving Metric Traveling Salesman Problems: An Application for Manipulator Path Planning
| Autor: | Tseng, Yen-Che, 曾彥哲 |
|---|---|
| Rok vydání: | 2019 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 107 This research considers metric traveling salesman problems. The objective is to find a minimal cost tour visited each nodes exactly once in a graph. We develop the transformation method to reduce the problem size of the original graph. To solve the problem, we group adjacent nodes as required edges and the connection of vertexes at different required edges is viewed as non-required edge. The problem turns to find a shortest closed walk to traverse required edges and is modeled as a rural postman problem. We demonstrate the applicable of the proposed method by solving dies picking problems for LED sorters. The computational result shows that our approach significantly reduces the problem size and obtains quality solutions for real-world problem instances. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|