Abstract
在本論文□，我們探討一種具有特殊結構的對稱中國郵差問題。由於, 中國郵差問題可描述成一整數規劃之模式, 在過去的文獻中,有關中國郵差問題的求解研究一直持續著。一般說來, 這種整數規劃在放鬆整數限制後, 即為一線性規劃模式 (簡稱LPR), 此時必須滿足對稱和偶邊性質才能得到整數解。近年來, 經由尋找圖形上的奇切割的方式已經發展出切割平面法來解此 LPR 模式。這種切割平面法是建立在對稱郵差多面體的部份線性系統上, 這種系統提供新的切割平面, 因此產生較好的對稱郵差多面體之 LPR 模式,但由實證中發現,即使找出所有的奇切割, 也不能保證可以得到最佳整數解。因此, 在本論文中, 我們將探討這種特殊結構的對稱郵差問題,從實際的例子中, 經由找部份的奇切割, 亦即單切割, 我們可以在 LPR 模式中找到最佳的整數解, 進而發展出類似上述的切割平面法來解決我們的問題。而這種方法也可應用在某些有方向性或混合性的對稱郵差問題; 同時, 我們也放鬆網路上的對稱權重來對此問題做更進一步的研究探討。最後我們以一些例子來評估這種切割平面法的成效。In this paper, we investigate a special structure of SymmetricChinese Postman Problems (SCPPs). The Chinese Postman Problem(CPP) has been studied extensively in the literatures. When aCPP is formulated in a form of an Interger Programming (IP)model, it can be solved by a method of linear programming (LP)if and only if it satisfies the symmetric and even-degreeproperties. Recent years, the cutting-plane algorithm for aCPP is developed by way of finding out the odd cuts of a graph.But, in general, the complexity of finding out all odd cuts isbad, and even though all odd cuts in a graph are found out, itstill cannot guarantee to obtain the optimal integralsolutions. So, we investigate the Symmetric Postman Problemsof special CPPs, of which the symmetric weights and symmetricgraph are defined. Numerically, we can obtain the optimalintegral solutions of a SCPP by way of finding out somepartial odd cuts, namely, the single cuts. Therefore, a prop-osed cutting plane algorithm is developed for the SCPPs. Thisproposed algorithm can also be applied to some symmetricdirected and mixted postman problems. Meanwhile, we extend thealgorithm to the problems that relax the condition ofsymmetric weights. Finally, we evaluate the performance of theproposed algorithm with some illustrative examples.