Abstract: It plays an important role in regional public traffic scheduling that creating the timetable which can minimize the transfer time of the passengers in every connection stop; meanwhile, synchronization departure can deal with the problem effectively. In this paper, the regional public transportation timetabling is formulated as a peculiar kind of non-capacity Knapsack Problem (KP) with the synchronization coefficient that is defined by author. The mathematical model is built, and the Nesting Taboo Search Algorithm is developed to solve the problem. The computational results demonstrate that the high quality solutions to the KP can be obtained by using the modified taboo search algorithm，and that the algorithm is efficient and feasible.

Key words: Bus Timetable, Public Transportation, Synchronization, Knapsack Problem, Taboo Search

摘要： 编制出能够最大限度地减少乘客在不同线路交叉点处换乘等待时间的公交时刻表是实现公交调度区域化的关键任务之一，而协同发车是实现这一目标的有效手段。本文将以乘客换乘时间最少为目标的区域公交时刻表的编制问题归结为一类特殊的带有协同系数且无容量约束的0-1背包问题，并定义了协同系数，建立了相应的数学模型，给出了基于嵌套式的禁忌搜索算法的模型解法。实验计算结果表明，用本文设计的算法求解这类特殊的0-1背包问题可以取得良好的结算结果，该算法是可行的，也是有效的。

关键词: 时刻表, 公共交通, 协同, 0-1背包问题, 禁忌搜索