Heuristic Algorithms for the Maximum Benefit Chinese Postman Problem
| Autor: | Wen-chi Chiu, 邱文琪 |
|---|---|
| Rok vydání: | 1999 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 87 The Maximum Benefit Chinese Postman Problem (MBCPP) is a practical generalization of the classical Chinese Postman Problem (CPP), which has many real-world applications. The MBCPP has been shown more complex than the Traveling Salesman Problem (TSP). Therefore, it is difficult to solve the problem exactly within the reasonable time. In this paper, we first review an exact solution procedure proposed by Malandraki and Daskin [1]. Then, we introduce two heuristic algorithms called farthest neighbor and maximum benefit insertion algorithm to obtain MBCPP's initial solutions. We also apply tabu search to improve the initial solutions. The proposed algorithms are tested and the solution performances are analyzed. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|