摘要
中国邮路问题是图论中的经典问题,得到了深入的研究和广泛应用。近年来,由于计算机网络与通信、智能交通系统等复杂应用领域的需求,时间依赖网络问题的研究具有更为重要的现实应用意义。本文首次提出了时间依赖网络中的中国邮路问题,建立了该问题的整数线性规划模型,并对该模型的上界进行了分析,最后给出了网络应用实例。
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 timedependent networks become more realistic than the classic problems. In this paper, we introduce the TimeDependent 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.
出处
《计算机工程与科学》
CSCD
北大核心
2010年第10期122-125,共4页
Computer Engineering & Science
基金
国家自然科学基金资助项目(60873256)
国家973计划资助项目(2005CB321904)
关键词
中国邮路问题
时间依赖网络
整数线性规划模型
上界分析
Chinese Postman Problem
timedependent network
integer linear programming
unpper bound analysis
