城市交通优化中基于对偶算法的元胞自动机  

Dual algorithm based-cellular automata model in city traffic optimization

作　　者：周康[1] 殷燕芳[2] 解智[1] 魏传佳[1] 

机构地区：[1]武汉工业学院数理科学系,湖北武汉430023 [2]武汉工业学院机械工程学院,湖北武汉430023

出　　处：《华中科技大学学报（自然科学版）》2010年第1期50-54,共5页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(60574041);湖北省自然科学基金资助项目(2007ABA407);湖北省教育厅科学技术研究资助项目(D20091805)

摘　　要：对基于换乘时间的城市交通优化问题进行了数学模型分析,根据模型的对偶原理得到了问题的对偶算法,设计了元胞自动机.在元胞自动机中,以每一个站点作为一个元胞,根据是否获得最佳乘车线路将元胞分为2种状态,将中心元胞的下一个站点作为其邻居,演化规则只作用于未获得最佳乘车线路的元胞,并只需通过对演化时间与元胞的相应权值的比较来确定状态的改变.基于对偶算法元胞自动机具有元胞状态少、邻居关系简单、演化规则简便和计算量少的特点.仿真实验说明了基于对偶算法元胞自动机的有效性和可行性.From transferring time, a mathematical model for city traffic optimization was put forward. Dual algorithm of this optimization was founded according to dual principle of the mathematical model. On the basis of the dual algorithm, cellular automata was designed to optimize the city traffic. In the cellular automata, every single bus station was regarded as a cellular. According to obtaining the optimal bus line or not, cellular was divided into two states. The next bus station of central cellular was regarded as a neighbor of the central cellular. Evolution rule only acts on the cellular which did not obtain the optimal bus line. It only needed to compare evolution time with the relative weight of cellular to determine state change of the cellular. Therefore, cellular automata based on dual algorithm has advantages in less cellular state, simpler relationship of neighbor, convenient rule, computational complexity, etc. Finally, the validity and feasibility of cellular automata based on dual algorithm were explained by a simulate experiment.

关 键 词：城市交通优化 对偶算法 元胞自动机 换乘时间 最佳乘车线路 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]