以整數規劃法作列車班次排點

Abstract

本論文中，我們提出一個以整數規劃法來作列車班次排點。列車排點最主要的問題是 如何解決衝突繁衍。由於解決一衝突後可能造成其它衝突，我們採用向前看策略來避 免引發其它潛伏但明顯可預見的衝突。經由仔細地分析，我們對每一種衝撞及最小時 隔的情形提出一組限制條件來避免衝撞並保證符合最小時隔的要求。利用這些限制條 件我們提出一套系統化的程序來解列車排點問題。首先，我們根據各輛列車本身的一 些限制條件，如發車時間，停站時間，運轉時間，將問題描述成一個線性規劃的模式 。然後，以LINDO 此套裝軟體來求解。當解出一個基本的排點後，我們以一個演算法 來檢查這個初步的排點是否合理。也就是說，看看此排點是否滿足列車之間的限制條 件，如避免衝撞，以及是否符合最小時隔的要求。如果滿足，則所求的解就是我們所 要的最佳解。如果不滿足，則系統會根據不滿足的情形自動產生相對的一些限制條件 ，並加入於原來的模式中重新求解。如果所求出的排點，經過檢查後仍然有不滿足的 情形時，則相對應那些新的且未被滿足的限制條件將自動被產生並加至原來的模式中 ( 是指包含最原始的各輛列車本身的限制條件以及截至目前為止已經加入的那些列車 之間的限制條件) 重新再求解。此一程序，將重覆至找到一個沒有不合理現象的排點 ，或者是發現根本不存在一個合理解。此程序最主要的優點是它提供了一個逐步調整 法來解大尺度的數學規劃問題。理論證明與實驗結果均證明了此方法的最佳性。