基于探针机的列车调度研究

Train scheduling is a typical combinatorial optimization problem, in many cases, this problem has been proved to be NP-complete. In scheduling theory, models and algorithms are the core problems; thence the research on scheduling problem has been carried out around these two points. Probe machine is a fully-parallel computing model in the sense that it can simultaneously process multiple pairs of data, rather than sequentially process every pair of linearly-adjacent data. Both graph coloring and Hamilton cycle problems are NP-complete, the probe machine can enumerate all solutions to each of these problems by only one probe operation. During the process of solving a problem by the probe machine, the number of probe operations required is independent of the size of the problem. Therefore, the project intends to use the probe machine to solve the train scheduling problem. Specifically, this research will be carried out from the following three aspects: ⑴ establish the mathematical model of train scheduling problem; ⑵ explore the probe machine implementation research by advanced electronic technology; ⑶ design the probe machine algorithm model for solving train scheduling problem.

列车调度问题是一类典型的组合优化问题，很多情形下的该问题已被证明是NP-完全问题。模型和算法是调度问题的核心，故对调度问题的研究也一直围绕这两点展开。探针机是一种底层全并行的数学计算模型，对于NP-完全问题中的图着色问题和Hamilton圈问题，探针机只需一次探针运算即可求出问题的所有解，探针运算次数与问题的规模无关。因此，本项目拟采用探针机来求解列车调度问题，研究内容主要分为以下3个方面：⑴ 列车调度问题的数学模型建立；⑵ 利用成熟先进的电子技术探索探针机的实现研究；⑶ 设计用于求解列车调度问题的探针机算法模型。

列车调度问题是一类典型的组合优化问题，很多情形下的该问题已被证明是NP-完全问题。模型和算法是调度问题的核心，故对调度问题的研究也一直围绕这两点展开。探针机是一种底层全并行的数学计算模型，对于NP-完全问题中的图着色问题和Hamilton圈问题，探针机只需一次探针运算即可求出问题的所有解，探针运算次数与问题的规模无关。本项目研究了基于探针机新型计算模型的解列车调度问题求解，研究成果主要分为以下3个方面：⑴ 列车调度问题的数学模型的建立；⑵ 求解列车调度问题的探针机算法模型的设计；⑶基于电子技术实现了1000个数据规模的问题求解。