最大效益中國郵差問題之啟發式解法

Abstract

最大效益中國郵差問題（Maximum Benefit Chinese Postman Problem, MBCPP）是傳統中國郵差問題（Chinese Postman Problem, CPP）的一般化問題，現實生活中有許多應用的實例。由於最大效益中國郵差問題比旅行推銷員問題（Traveling Salesman Problem, TSP）複雜度更高，因此要在可接受的時間內求出最佳解將是非常困難的。本篇論文中我們首先回顧Malandraki and Daskin [1] 提出的最佳解解法，接著我們提出最遠鄰居與最大效用插入兩個啟發式演算法求出起始解，我們也應用禁制搜尋法改善起始解，提出的演算法都經過測試例題測試和分析。

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.