越野尋蹤問題之演算法應用於最大效益中國郵差問題

Abstract

最大效益中國郵差問題(Maximum Benefit Chinese Postman Problem, MBCPP)是傳統中國郵差問題（Chinese Postman Problem, CPP）的一般化問題，現實生活世界中有許多相關應用實例。由於最大效益中國郵差問題比旅行員推銷問題（Traveling Salesman Problem, TSP）複雜度更高，因此要在可接受的時間內求出最佳解將是非常困難的。在本篇論文中我們將無方向性的最大效益中國郵差網路以一簡單的轉換法則，轉換成為越野尋蹤問題（Orienteering Tour Problem, OTP）。由於越野尋蹤問題受到許多學者的研究，相關的演算法也發展得相當成熟並獲致良好成效，所以，越野尋蹤演算法將可應用在最大效益中國郵差問題。首先我們先將最大效益中國郵差問題藉由一轉換法則成為越野尋蹤問題後，利用修改後的Tsiligirides演算法求解最大效益中國郵差問題，修改後的Tsiligirides演算法都經過測試例題測試和分析並有顯著的成效。

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 to be more complex than the Traveling Salesman Problem (TSP), and therefore it is difficult to solve the problem exactly. In this paper, we consider the MBCPP on totally undirected networks. We first present a simple network transformation to convert the MBCPP into the Orienteering Tour Problem (OTP), a well-known network routing problem that has been investigated extensively. Consequently, the MBCPP may be solved using the existing OTP solution procedures. We then present a modification of the Tsiligirides’ algorithm to solve the MBCPP approximately. The proposed modified Tsiligiride’s algorithm showed significantly effectiveness after tests by using the cost and benefit structure considered in Malandraki and Daskin (1993). Extensive computational results are provided and analyzed.