基于分支定价算法的泊位与岸桥联合调度问题研究

《基于分支定价算法的泊位与岸桥联合调度问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于分支定价算法的泊位与岸桥联合调度问题研究(申请清华大学工程硕士专业学位论文)培养单位：工业工程系工程领域：物流工程申请人：解凡芮指导教师：张灿荣副教授联合指导教师：周受钦教授级高工二○一七年五月BranchandPriceAlgorithmfortheIntegratedBerthAllocationandQuayCraneAssignmentThesisSubmittedtoTsinghuaUniversityinpartialfulfillmentoftherequirementfortheprofession

2、aldegreeofMasterofEngineeringbyXieFanrui(LogisticsEngineering)ThesisSupervisor:AssociateProf.ZhangCanrongAssociateSupervisor:ProfessorofEngineerZhouShouqinMay,2017摘要摘要集装箱运输在国际贸易中扮演着重要角色。岸桥和泊位联合调度问题是集装箱港口运作中的重要问题，直接决定集装箱码头的运作效率，此外，由于岸桥和泊位在一定程度上具有互相绑定和制约关系，获取这两类稀缺

3、资源的最优分配计划变得非常困难。因此，研究港口泊位与岸桥联合调度问题具有重要的理论和现实意义。本文研究了集装箱港口泊位与岸桥联合调度问题，在给定的计划周期内为计划到达港口的船舶分配泊位以及靠泊时间，同时选择满足船舶作业条件的岸桥分配组合，在资源分配过程中需要考虑船舶和泊位的时间窗约束、港口岸桥的数量约束、船舶之间不可重叠等约束。本文的主要难点和特点有：1）考虑了两种资源的联合调度；2）引入了岸桥分配组合的概念，使得船舶作业时间并非为传统意义上的常数，而是取决于所选定的岸桥分配组合和船舶靠泊时间。在求解方法上，不同于以往

4、学者通常采用的启发式算法，本文采用了面向全局最优的分支定价算法。文章设计了基于船舶分解的DantzigWolfe分解算法，将原问题分解为以船舶为单位的可独立求解的子问题，和把所有子问题衔接起来协调控制资源分配的主问题。在算法设计中，引入了次梯度优化拉格朗日松弛算法解决列更新过程中可能产生的退化问题；采用了基于子问题而非主问题进行分支的策略，即将分支约束加入子问题中，避免产生新的对偶价格，降低了分支的复杂性；同时设计了广度优先和深度优先节点选择策略。此外，论文也设计了多种用于生成初始列的方法。在大量的数值实验的基础上，本

5、文比较研究了初始列生成阶段、迭代过程中列更新阶段、节点选择阶段的多种策略和方法，并与CPLEX的结果进行比较验证了算法的有效性。实验结果表明：在初始列生成阶段，时间优先启发式算法优于其它初始列生成方法，可以更快得到原问题最优解；在列更新阶段，之前学者提出的拉格朗日松弛嵌套列生成方法并没有表现出明显的优势；在节点选择阶段，深度优先策略对部分算例表现较优，但在求解时间上波动性较大，其稳定性次于广度优先策略。此外，数值结果也表明分支定价算法在求解时间和求解质量上均优于CPLEX。关键词：泊位分配；岸桥调度；分支定价；拉格朗日

6、松弛；次梯度优化IAbstractAbstractContainer-basedtransportiscrucialtointernationaltrade.Bothberthallocationandquaycraneassignmentdirectlyinfluencetheoperatingefficiencyofcontainerterminals,andthereforeareimportantissuesfacedbytheterminaloperators.Moreover,duetothefacttha

7、tquaycranesandberths,tosomeextent,areboundtoeachother,theirintegratedallocationbecomesmoredifficult.Therefore,studyinghowtogenerateaproperintegratedallocationofberthsandquaycranesisofsignificance.Thispaperstudiesanintegratedproblemfortheberthallocationandquaycra

8、neassignment,withtheaimtosettletheberthandquaycraneprofileforeachincomingvesselovertheplanninghorizon.Intheproblem,nooverlappingofresourcesamongvessels,timewindowsfor