“兩江游”輪船調度問題

孟慶展

摘要：關于輪船往返的時間調度問題，為減少輪船出行次數，增大每天總乘載人數，均衡每次出行人數，本文充分考慮時間的限制條件和游客可能的等待狀況，建立了線性規劃模型和0-1線性規劃模型。對于不同情況，不同要求分別得出了合理的輪船航程安排。

關鍵詞：輪船;線性規劃;0-1線性規劃;lingo;航程安

一、問題分析

輪船的調度問題就是確定各艘輪船的發行時間，使輪船出行總次數盡可能小，運載人數盡可能多以及每次運輸人數盡量均衡來實現輪船公司利益最大化。游客等待的等待情況關系航程時間安排對一天內坐船人數的影響，可用輪船數量多少決定岸邊等待人數能否被全部運走。

1.1游客無限等待

在此情境下，游客會無限等待，因此一天內將要上船的人數一定，與每艘輪船發行時間無關。因而主要考慮輪船每次運載人數最大化來實現出行次數最少和每次運輸人數的均衡。經簡單計算可得，在90分鐘航程內到達岸邊人數大于輪船最大乘載數，所以每次輪船回港時最少有270人。一艘輪船無法運完一天規定時間內到達岸邊的所有人數并且每次回港都無法運完岸上人數。因此著重考慮合理安排發船時間使一天運載人數達到最大。在輪船每次返航后即發船的情況下，通過定義初次發船時間距起始時間的時間間隔和一天該船總發行次數這兩個量，找出時間的不等式約束關系。找出運載人數與初次發船時間間隔的關系，將其作為目標函數，建立線性規劃模型，運用lingo編程法求得目標函數最大值的模型的解。從而找出最優航程安排。

1.2碼頭無船則游客立即離開

此時由于碼頭無船則游客不等待，所以在輪船外出航行的90分鐘內，碼頭不積累人數，每次上船人數與輪船每次等待時間有關。按照2.1.1中的時間約束條件，可以確定輪船出行次數為定值。為使一天內輪船乘載人數最多。在總出行次數一定的情況下，定義輪船每次出行前的等待時間同時引入該方差，利用2.1.1中的模型，運用lingo編程法，得到最優解。

二、模型的建立與求解

2.1模型建立

設經第一艘船出發時間與8：00相距t分鐘，該船總共出行n次。

由每次出發人數不得少于輪船最大乘載量的60%且不得超過最大乘載量可得

由于游客在8：00到18：00這600分鐘之間到來參觀，且根據假設，最后一艘船可在18時整及以前出發，在18時之后正常歸來。并且由于在輪船的每次航行時間內，到達岸邊人數為人3×90=270，大于150，每次輪船出行都滿載且都有120人無法上船。最后一艘船出行時間距8時的時間間隔為t+90（n-1）。且為保證最后輪船出行后再無輪船出行，得：

2.2模型的算法實現

算法流程圖如圖2.1所示

2.3模型求解

編寫Lingo程序，求得最終結果為

船的具體出發時間如下表：