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

doi:10.3969/j.issn.1007130X.2010.

J4 ›› 2010, Vol. 32 ›› Issue (10): 122-125.doi: 10.3969/j.issn.1007130X.2010.

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

孙景昊，孟亚坤，谭国真

（大连理工大学计算机科学与技术学院，辽宁大连 116023）

收稿日期:2010-03-12 修回日期:2010-06-19 出版日期:2010-09-29 发布日期:2010-09-28
作者简介:孙景昊(1985),男，河北沧州人，博士,研究方向为时变网络优化和时间自动机理论；孟亚坤，硕士，研究方向为时变网络优化；谭国真,博士，教授,研究方向为时变网络优化、物联网、时间自动机理论、智能交通和城市交通信号控制。
基金资助:
国家自然科学基金资助项目(60873256)；国家973计划资助项目(2005CB321904)

The TimeDependent Chinese Postman Problem

SUN Jinghao，MENG Yakun，TAN Guozhen

（School of Cmputer Science and Technology,Dalian University of Technology,Dalian 116023,China）

Received:2010-03-12 Revised:2010-06-19 Online:2010-09-29 Published:2010-09-28

摘要/Abstract

摘要：

中国邮路问题是图论中的经典问题，得到了深入的研究和广泛应用。近年来，由于计算机网络与通信、智能交通系统等复杂应用领域的需求，时间依赖网络问题的研究具有更为重要的现实应用意义。本文首次提出了时间依赖网络中的中国邮路问题，建立了该问题的整数线性规划模型，并对该模型的上界进行了分析，最后给出了网络应用实例。

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

Abstract:

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.

Key words: Chinese Postman Problem;timedependent network;integer linear programming;unpper bound analysis

孙景昊，孟亚坤，谭国真. 时间依赖网络中国邮路问题[J]. J4, 2010, 32(10): 122-125.

SUN Jinghao，MENG Yakun，TAN Guozhen. The TimeDependent Chinese Postman Problem[J]. J4, 2010, 32(10): 122-125.

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

The TimeDependent Chinese Postman Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 0

编辑推荐

Metrics

本文评价