“两江游”轮船调度问题

孟庆展

摘要：关于轮船往返的时间调度问题，为减少轮船出行次数，增大每天总乘载人数，均衡每次出行人数，本文充分考虑时间的限制条件和游客可能的等待状况，建立了线性规划模型和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程序，求得最终结果为

船的具体出发时间如下表：