混合網路上的多郵差問題

Abstract

典型的中國郵差問題(CPP)，是在一個無向的街道圖中找到一個郵差的最 短工作路徑，該路徑必須包含所有的街道。混合網路的多郵差問題(k- MCPP)是衍生自中國郵差問題，在一個混合網路中找到k個郵差最短的總工 作路徑。在混合網路中，有些街道可以雙向行走，而有些是單行道。在一 般日常的許多問題如 : 送報生、郵差、停車計時器的收費、垃圾車、掃 街車、掃雪車、校車、讀電表和電線及油管的檢查都是混合網路上多郵差 問題的應用。混d p鼽籅熄l差問題已經被證實是複雜度相當高(NP- complete)的問題，混合網路上的多郵差問題亦然。在本論文中，我們將 介紹混合網路上多郵差問題的幾種近似解的演算法。 Given an undirected street network, the celebrated Chinese postman problem (CPP) is that of finding a shortest postman tour covering all the edges (streets) in the network. The k-person Chinese postman problem on mixed networks (k-MCPP), is an extension of the CPP, in which there are multiple postmen involved in the routing on mixed networks. On mixed networks, some streets are allowed to be traversed in both directions, and others may be traversed in one specified direction only. Applications of the k-MCPP include: routing of newspaper or mail delivery, parking meter coin collection or household refuse collection vehicle, street sweepers, snow plows, and school buses; spraying roads with salt, inspection of electric power lines, or oil or gas pipelines, and reading electric meters. The Chinese postman problem on mixed networks (MCPP) has been shown to be NP-complete. Therefore, the k-MCPP must be also NP- complete. In this thesis, we introduce some heuristic solution procedures to solve the problem approximately.