Research on Public Ship Scheduling Strategy Based on Multi-objective Optimization
陈城钰 CHEN Cheng-yu
（西北工业大学，西安 710000）
（Northwestern Polytechnical University，Xi'an 710000，China）
摘要：在公共交通系统中，如何合理调度以实现运营收入与乘客满意度的双重效益一直是重点研究方向。本文以某轮船公司开设的轮船摆渡服务为研究对象，设定公司运营收入最大化与利润最大化为最优目标，考虑一天内游轮数量、等待损失机制等不同情况，通过非线性动态组合优化算法分析并求解轮船航程安排与实际载客量等实际调度规划。
Abstract: In the public transportation system, how to rationally dispatch to achieve the dual benefits of operating income and passenger satisfaction has always been the focus of research. This paper takes the ship ferry service opened by a certain shipping company as the research object, sets the company's operating income maximization and profit maximization as the optimal goal, considers the number of cruise ships in one day, the waiting loss mechanism and other different situations, through the nonlinear dynamic combination optimization algorithm to analyze and solve the actual scheduling plan such as the ship's voyage schedule and actual passenger capacity.
关键词：多目标优化；运营成本；组合优化；调度
Key words: multi-objective optimization；operating cost；portfolio optimization；scheduling
中图分类号：F252 文献标识码：A 文章编号：1006-4311（2019）27-0027-02
1 问题背景
随着公共交通的发展与人口的急剧增长，对于以营利与社会效益为目的交通公司来说，实施合理的调度算法显得尤为重要。本文通过市场调研，以西安当地一家商用公共轮船公司的经营情况为例，通过合理的模型建立，使之实现利益最大化，并为游客提供最为优质的服务。
从游轮公司的角度出发，为了实现利益最大化，首先，是实现每天运营收入的最大化；其次，考虑运营时油费、设备折旧等成本，实现利润最大化；最后，为提高服务质量和游客满意度在总运载人数不变情况下，使游轮每次运载的人数尽可能均衡。
为使得模型具有说服力与可靠性，对使用数据与实际约束条件进行如下设定。游轮满载是150人，起航时的载客量至少达到满载的60%。游轮载客游览时间（即启航至返航的时间）为1.5小时。每人次的游览票价为25元。游客主要参观游览时间为上午8点到下午6点，在该时间段内，游客将以平均每分钟3人的速度到达码头。
2 模型假设
①到达码头的游客，在符合登船规则的情况下，都会登船游览。②游轮在运行过程中不会发生故障，影响后续航程安排。③前两问不接待8：00前和18：00点后到达码头的游客，第三问中，考虑7:50~18:00到达码头的游客。④忽略游客上下船的时间。
3 模型的建立
为获得单艘游船的航程安排并计算总载客量，首先根据游船的运营成本并结合相关经济学原理建立出航利润模型；再以收入最大化、利润最大化为目标进行多目标优化，最终筛选所得数据，选出每次运载游客最为均衡的航程规划方案，确定总载客量。[1]
①收入的量化：已知收入特指票价收入，满足关系式：收入=票价×乘客人数，设Ti为游轮运行总时间，其中包括接客时间ti和航程时间90分钟，总人数为N且N=Σ■■3ti，则收入F为：
F=25N（1）
②成本的量化：本小组计算总成本包括游船运营成本和游客出行成本，其中游船运营成本受维护费、折损额和油耗等因素影响，综合考虑游客满意度等因素可知，游客出行成本受到游客等待时间和游船满载率影响。[2]
游船运营成本：G=A+B+C（2）
其中每日维护费用为A元，每日折旧额为B，每日油耗费用为C元。
为了简化问题，每日轮船的维护保养费A定为常数。据《企业所得税法实施条例》规定，可得折旧额B计算公式为：
■（3）
■（4）
油耗分为等待油耗和运行油耗且油耗与载重有关，油耗为每日C元，包括等待油耗b元/分钟和运行油耗c元/分钟，出行次数为x，每个游客及行李的质量和为m，已知载重每增加1000kg油耗增加d%，满足关系：
■（5）
乘客出行成本：
假设单位运营时间为T，且600?燮T?燮690，游船接客时间为ti，且30?燮ti?燮49。
1）等待时间成本：
假设m为与平均等待时间有关的出行成本经验折算系数，qi表示平均每时段在码头等待轮船的人数即上船人数，则在轮船停靠等待时间为ti分钟时，游客实际最长接客时间为ti分钟，最短接客时间为0分钟，则游客平均等待时间Δt=■。[3]等待时间成本满足：
■（6）
其中N为总乘客人数。
2）游客满意度成本：
假设n表示与车辆平均满载率有关的出行成本经验折算系数，pi表示每时段内单向断面平均通过乘客人数，K0为额定搭载乘客人数，则在单位运营时间内学生乘车的平均满意程度为w：
■（7）
游客满意度成本满足关系：
■ （8）
由式（6）（8）可得游客出行成本满足关系：
■（9）
根据游轮运营成本和乘客出行成本对总成本的影响设置权重α和β，得到游轮载客总成本函数为：
■（10）
③利润计算：每日出行的总利润f满足关系式：
■（11）
由式（1）（10）即可得总利润。
根据题目要求，需实现收入最大化、利润最大化且保证运营时间尽可能均衡，因此本小组通过设置约束调节和目标函数实现多目标优化，并通过设置权重衡量收入最大化和利润最大化对最终目标的影响，最终确定最佳接客时间ti并安排游船的航程。[4]
可得约束条件的表达式为：
■（12）
■（13）
■（14）
根据收入最大化和利润最大目标可知目标函数为：
■（15）
■（16）
这两个目标是相互关联的，由于游船公司对这两个目标的重视程度不同，因此要对这两个目标在最终目标中分别对赋予权重α和β得出终的目标函数：
■（17）
4 模型的求解
根据相关资料，设置相关变量如下：
每日维护费用A为200元；轮船折旧的最低年限为10年，一般情况下，预计净残值为5%；假设游轮的固定资产原价为a=100万元，由公式（2）（3）则可得每日折旧额为：
■（18）
等待油耗b为7元/分钟，运行油耗c为8.385元/分钟，每增加1000kg油耗增加0.2%；由于30?燮tij<50，tij∈Z由前面分析可得运载次数x=5，每个游客及行李的质量和为M=70kg，可得消耗油费为：
■（19）
由式（1）（4）（5）得游轮运营成本为：
■（20）
平均等待时间有关的出行成本经验折算系数m为0.1，与车辆平均满载率有关的出行成本经验折算系数n为0.1，由式（）（）（）得游客出行成本为：
■（21）
则可得游客利润为：
■（22）
对于这五次运载的接客时间可组合出C■■种情况，计算出每组的fi和Ni，带入目标公式并赋予权重α=0.6，β=0.4，计算随着等待时间的增加，收入、成本和利润的变化率。
最终可得，收入整体呈递增趋势，由于成本收到顾客等待时间的影响，0-45分钟利润不断增加，在等待时间过长（大于45分钟），利润有所下降。因此在等待时间为45分钟时利润最大为9191.63元，在等待时间为49分钟时收入最大为17850元，最终设置等待时间为47分钟，五趟后总搭载量为705人。
轮船航程安排和搭载量如表1。
■
5 模型的评价与推广
本模型的主要优点在于，将游客的满意度这一抽象标准转换成可以衡量的金钱成本与收入，利润等量的单位进行统一，方便进行多目标优化。然而，在运营成本的制定过程中，随机因素较多，导致模型无法准确地反映出来。我们采用抓住最主要的影响因素的办法进行处理。
本文提出的模型具有较好的应用前景。其中，成本计算模型将抽象的顾客满意度的概念进行量化处理，可以应用于衡量其他服务业务的客户满意度。以收入和利润最大化为目标的多目标组合优化模型，可以通过设定不同的权重，以达到不同决策者对不同目标的重视程度不同。可以应于其他组合优化问题，比如规划校车发车时间。
参考文献：
[1]任建洵，王浩华.基于组合优化算法下的校车发车时间问题研究[J].井冈山大学学报，2018（7）：11-16.
[2]刘文.校车优化调度算法及模型研究[J].清华大学学报：自然科学版，2013（2）：247-251.
[3]刘伟，陈科全，谢忠金.大型公交站的动态排队论分析与优化[J].重庆交通大学学报，2018（8）：7.
[4]越民义.组合优化介绍[J].运筹学杂志，1988（01）. |
