“兩江游”輪船調(diào)度問題

孟慶展

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

關(guān)鍵詞：輪船;線性規(guī)劃;0-1線性規(guī)劃;lingo;航程安

一、問題分析

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

1.1游客無限等待

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

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

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

二、模型的建立與求解

2.1模型建立

設(shè)經(jīng)第一艘船出發(fā)時(shí)間與8：00相距t分鐘，該船總共出行n次。

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

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

2.2模型的算法實(shí)現(xiàn)

算法流程圖如圖2.1所示

2.3模型求解

編寫Lingo程序，求得最終結(jié)果為

船的具體出發(fā)時(shí)間如下表：