定序单线列车运行图的原始－对偶算法

定序单线列车运行图问题是在给定列车在各站的到达、出发和不停车通过作业顺序的条件下，铺画旅行时间最少的单线列车运行图。本文为此问题设计了一种原始－对偶算法，其时间界为Ｏ（（ｍｌ＋ｎｌ）３），其中，ｍ、ｎ、ｌ和Ｏ（ｍｌ＋ｎｌ）分别为上、下行列车数、车站数和输入数据个数。该算法设计精巧、求解迅速，对单线列车运行图优化有着重要的理论和实际意义。