时间依赖网络中国邮路问题  

The Time-Dependent Chinese Postman Problem

作　　者：孙景昊[1] 孟亚坤[1] 谭国真[1] 

机构地区：[1]大连理工大学计算机科学与技术学院,辽宁大连116023

出　　处：《计算机工程与科学》2010年第10期122-125,共4页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(60873256);国家973计划资助项目(2005CB321904)

摘　　要：中国邮路问题是图论中的经典问题,得到了深入的研究和广泛应用。近年来,由于计算机网络与通信、智能交通系统等复杂应用领域的需求,时间依赖网络问题的研究具有更为重要的现实应用意义。本文首次提出了时间依赖网络中的中国邮路问题,建立了该问题的整数线性规划模型,并对该模型的上界进行了分析,最后给出了网络应用实例。The Chinese Postman Problem is one of the classic problems in graph theory and has been deeply studied. It is applicable in a wide range of fields. With the rapid development of computer networks and communications, and Intelligent Transportation Systems （ITS）, the problems in timedependent networks become more realistic than the classic problems. In this paper, we introduce the TimeDependent Chinese Postman Problem （TDCPP） for the first time,and the problem is formulated as an Integer Linear Program. The upper bound of the formulation is proved and the correctness of the formulation is verified by a small example.

关 键 词：中国邮路问题 时间依赖网络 整数线性规划模型 上界分析 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]