点击次数：

论文类型：期刊论文

发表时间：2011-05-01

发表刊物：Journal of Information and Computational Science

收录刊物：EI、Scopus

卷号：8

期号：5

页面范围：833-841

ISSN号：15487741

摘要：This paper studies an extended version of the Chinese Postman Problem involving the added complexity of time dependent travel times, which is motivated from hybrid system testing. In the literature, the conventional Chinese Postman Problems defined on the Euler graph are polynomially solvable. However, we prove that the Chinese Postman Problem defined on the time dependent network is NP-hard even if it verifies the Eulerian and First-In-First-Out properties. Furthermore, a dynamic programming algorithm is proposed for the problem with the First-In-First-Out property. Experimental results show that small to medium-sized instances can be solved to proven optimality. Copyright ? 2011 Binary Information Press.