基于公平原则的泊位一岸桥联合调度研究-范丽先.pdf
《基于公平原则的泊位一岸桥联合调度研究-范丽先.pdf》由会员分享,可在线阅读,更多相关《基于公平原则的泊位一岸桥联合调度研究-范丽先.pdf(9页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第22卷第2期2017年4月工业工程与管理Industrial Engineering and ManagementV0122 No2ADr2017文章编号:1007-5429(2017)02006009 DOI:1019495jcnki10075429201702009基于公平原则的泊位一岸桥联合调度研究范丽先1,王行苑1,尹静波2(1上海大学管理学院,上海200444;2上海交通大学船舶海洋与建筑工程学院,上海200240)摘要:港口调度优化问题分为离散的泊位分配和时变的岸桥调度问题,并构建泊位一岸桥联合调度优化模型。对于到港船舶泊位分配问题,提出靠泊优先权概念,并以此作为基因编码基础。岸
2、桥分配中提出岸桥调度的公平分配原则,使得岸桥分配存在初始分配和最终分配。为解决非线性混合整数规划模型,改进了遗传算法,模型目标是使所有船舶在港总时间最小。实验算例验证了算法设计的优越性。关键词:泊位一岸桥调度;优先权;公平原则;非线性混合整数规划模型;遗传算法中图分类号:U691 文献标识码:AJoint Scheduling of BerthQuay Crane Based on Fair PrincipleFAN Lixianl,WANG Xing-yuanl,YIN Jing-b02(1School of Management,Shanghai University,Shanghai 2
3、00444,China;2School of NavalArchitecture,Ocean and Civil Engineering,Shanghai Jiao Tong University,Shanghai 200240,China)Abstract:The operation of container terminals iS divided into discrete berth allocation andtime-variant scheduling of quay cranesA joint scheduling model is then developed for the
4、container berth-quay crane optimizationFor berth allocation,the concept of berth priority wasproposed to allocate berths for arriving ships,which is the basic unit in the coding systemA fairallocation principle was also designed in the scheduling of quay cranes,which makes the allocationinto initial
5、 and final allocationsTo solve this nonlinear mixed-integer programming model,thegenetic algorithm was improved with the goal of minimizing the total time of all the ships in portComputational experiments show the performance improvement of the proposed algorithmKey words:berth and crane scheduling;
6、priority;fair principle;nonlinear mixed integerprogramming model:genetic algorithm1 引 言集装箱船舶的大型化以及港口吞吐量的不断增加,对港口现有的装卸能力和管理水平提出新的考验。在集装箱港口硬件设施既定的条件下,泊位分配、岸桥调度以及两者的联合调度优化对提高港口作业效率至关重要。在泊位分配问题上,目前码头大多采用先到先服务(FCFS)的人工分配方式,但在船舶大小、到港时间和装卸作业量有明显差别时,这种方式不利于整体装卸作业时间的节省和总成本的节约。在当前竞争激烈的码头实际运营中,为吸引航运公司船舶停靠,港口纷纷
7、提出优先权概念。Imai等1 3研究了动态泊位分配问题。为减少港口费用,提出减少租收稿日期:20160810;修回日期:20161124基金项目:国家自然科学基金资助项目(71302052,71673181);上海市浦江人才计划资助项目(14PJC070)作者简介:范丽先(1979一),女,河北任丘人,副教授,博士,主要研究方向为航运管理、港口调度,E-mail:lixianfanshueducn。万方数据工业工程与管理 第2期赁泊位,增加公共泊位的数量,但其运营更需要联合调度以提高效率。Imai等21首次定义了多用户集装箱码头,阐述了船舶服务优先权在多用户集装箱码头的重要性。杨春霞、王诺3
8、3建立了以船舶平均在港时间、码头生产成本和安全质量为目标的泊位调度多目标优化模型。秦天保,沙梅4研究了动态连续泊位分配问题,设计了以所谓的区问变量为中心的新规划模型。彭建良等5构建了群岛泊位分配问题模型,并提出了一种混合粒子群算法进行求解。上述学者都在单纯的泊位分配问题中考虑了更多的因素。现实中,迟到的船舶优先服务会降低客户的满意度。所以,在考虑船舶服务优先权时,船舶的到达时间也是不可或缺的影响因素。另外,岸桥配给数服务时间也对泊位分配问题产生重要影响。Imai等6提出了一种有效的泊位一岸桥联合调度计划。放宽了岸桥转移的限制,并要求船舶只有获得一定数量的岸桥才可以被操作服务。Liang等7考虑
9、了离散泊位情况下岸桥一泊位动态调度计划。在模型中添加了诸如时问、泊位分配和岸桥数量等因素。Han等8在船舶到达时间和集装箱操作时间随机的情况下,研究了一种摄动不敏感的鲁棒性调度方法。范志强等9建立了岸桥作业调度混合整数规划模型。秦天保、沙梅10建立了基于约束规划的支持岸桥双向调度的岸桥调度问题模型。孙彬等11提出了一种基于鲁棒反应式策略的泊位和岸桥联合调度方法。乐美龙、刘秀玲121针对泊位偏离和岸桥工作损失两方面,建立了泊位一岸桥的混合整数线性规划模型。Iris等131提出了一种基于岸桥时变的泊位岸桥分配模型。以上文献都是对泊位一岸桥的联合调度进行研究,优化的目标大多是使船舶在港总时间最少,岸
10、桥调度呈现多样性,但都对船舶的在港时间产生重要影响。泊位一岸桥联合调度模型大多属于混合整数非线性规划模型,遗传算法是解决这类问题的有效方法261 781“15。本文改进了遗传算法中的变异、交叉规则,加入了岸桥公平分配原则,使得算法选择过程动态化,此过程中得到的解能够更快接近最优解。2 问题描述泊位分配为离散泊位分配问题,码头根据船舶到港时间和其它相关信息安排泊位和岸桥。岸桥调度为时变的岸桥调度问题,即船舶停泊时岸桥数量可变。因此,泊位一岸桥联合调度问题包含两个子问题:离散泊位分配问题和时变的岸桥调度问题。目标函数是使所有船舶在港总时问最小,其中船舶在港时间包括:船舶等待泊位时间,船舶操作时间以
11、及岸桥调整时间。数学模型基于如下假设。港口泊位均满足到港船舶的吃水水深和长度的要求;每艘船舶都必须且只靠泊一次,不存在移泊现象;每个?白位在一个时间只服务一艘船;船舶在到达后开始服务;船舶作业开始后将不中断直到作业结束;岸桥不能跨越转移;为同一艘船舶服务的岸桥不一定同时开始工作,但应同时结束服务;每个泊位分配的岸桥数量有上限。3泊位一岸桥联合调度模型31靠泊优先权为去除船舶装卸量和到港时间由于单位不同造成的影响,首先对变量进行标准化,进而提出优先权公式:S0。一以X乞z+6T (1)其中Sk。哪表示船舶J的靠泊优先权;挺。r一表示标准化后的船舶J装卸量;码。代表标准化后的船舶J到港时间;口和b
12、分别为权重,其值由港口公司根据实际情况决定;歹V一1,),V为所有到港船舶集合。32公平的岸桥分配集装箱港口所拥有的岸桥量有限,如随机或按经验分配岸桥,则会出现不公平的分配情况。因此,本文提出公平的岸桥分配原则。假设两艘船舶ship A和ship B的装卸货物量分别为P。和P。,拥有岸桥数分别是n-和rz,则每个岸桥处理的货物装卸量分别为P-n-和P。竹z。显然仅当P。n。一pz”z时岸桥的分配才是公平的。当总岸桥数增加1台时,不难证明当(2)式成立时增加的1台岸桥应分给ship A,反之则分给ship B。妻i 垂i r 9、n2(咒2+1)、”l(”1+1)、“7或者,若记Q7一雳吩(吩+
13、1),J一1,2,则增加的1台岸桥应分给Q值较大的一方,这种岸桥分配方法为Q值法。33数学模型在联合调度模型中,公平的岸桥分配原则作为一61一万方数据第22卷 范丽先,等:基于公平原则的泊位一岸桥联合调度研究岸桥分配及调度的限制条件。331参数iEB一1,J)为泊位集合;歹V一1,J)为船舶集合;尼0一1,厂)为每个泊位上船舶停泊顺序集合;mN一1,M)为岸桥集合;A,为船舶J的到达时刻;y。为泊位i所能分配的最大岸桥数;dED一1,y。)为服务单个船舶的岸桥数集合;Ui为船舶J的作业量;P为一台岸桥单位时间处理量;e为船舶靠泊时岸桥调整所用时间;R为足够大的数。332变量(1)决策变量z拍E
14、B为船舶歹在泊位i被第走个服务,取值为1,否则为O;t濉吨车为船舶J在泊位i被第忌个服务的开始时刻;C。熙车为岸桥m为船舶J的服务时间;QC,嗯车为岸桥服务船舶J的最长时间;S。昶年为岸桥m为船舶J服务的开始时刻;QS,陬车为岸桥服务船舶J的最早开始时刻;Z后涩+为船舶J初始分配的岸桥数;Q删吨军+为船舶J在泊位i第忌个顺序被d台岸桥服务的Q值。(2)辅助变量a咖B如仅有第m咒台岸桥(m咒)为泊位i上的船舶服务,取值为1,否则为0;r赫B如岸桥m为泊位i上的船舶服务,取值为1,否则为0;鼬B如第m咒台岸桥(m,z)都处于服务状态,取值为1,否则为0;仃划B如船舶即将在泊位i被第是个服务且有d台
15、岸桥处于待分配状态,取值为1,否则为0;弛,B如泊位i需向泊位(i+1)上的船舶J转移岸桥,取值为1,否则为0;毫(H)iB如泊位i需向泊位(i一1)(i1)上的船舶歹转移岸桥,取值为1,否则为0。333模型建立Minimizez驰(洳+QcjAj)(3)z驰1 V iB,尼O (5)JV32驰32d(V志2,iB (6)jV JV啦Rz出V iB,JV,尼O (7)t融A,VJV (8)iEBOzd(协1)+QcJ,+P)t弛jEV JEVV i E B,忌O,JJ 7V (9)R(3c驰一1)z驰(Q巴一(),V mN,iB,JV,愚O (10)R(z啦一1)z舭(一QSj),V m E
16、N,iB,JV,走O (11)t甜一Qs,V歹V (12)iEBO(赫+一Sj,。)(G,。+S,m一)0,V mN,JJ E V (13)+勘一(,+勘,)一0,V mN,JJ 7 E V (14)z啦乙一yi0,V i E B,JV,愚E 0(15)U(ZJP)一Q巴0,V歹E V (16)一1)。口r(r1)(一1)一0,1),V m(1),z E N,i(1)B (17)段,1)。a。r(斗1)(,1)一O,V m(1),行E N,iB (18)风(井1)a一,(斗1)(升1)一O,1),Vm,竹N,iB(19)厩(升1)口锄r(r1)(计1)一0),V m,n E N,i(1)B (
17、20)仃划叩i(j+1)j(Q4,女(扣1)一Q(汁1)业o,)0,V iB,JV,尼O,dD(26)a渤0,1,V iB,m,n(m咒)N(27)r。0,1,V iB,m E N (28)鼬0,1),V m,n(mn)N (29)盯涮0,1),V i E B,尼O,d E D (30)万方数据工业工程与管理 第2期7i(-F1)j E0,1,V iB,J E V (31)毫(,1)f0,1),V i(1)E B,歹V(32)式(3)是目标函数,目的是使所有船舶在港总时间最小。式(4)式(6)规定任意一艘船舶必须要有泊位为其服务,所有船舶只能停靠一次泊位且每个泊位停泊的所有船舶要按顺序服务。式
18、(7)表明船舶开始服务时间有上界。式(8)也是时间约束条件,船舶开始服务时间必须大于船舶到港时间。式(9)表示任意两艘依次停靠同一个泊位船舶,后一艘船舶的开始时间必须大于前一艘船舶结束时间。式(10)表示多台岸桥服务同一艘船舶时,必有岸桥服务时间最长。式(11)表明多台岸桥服务同一艘船舶时,每台岸桥服务开始时刻可能有所不同,最早开始服务时刻必定小于或等于任意一台岸桥服务的开始时刻。式(12)表示岸桥服务船舶的最早开始时刻即为船舶的开始服务时刻。式(13)限制一台岸桥不能同时服务两艘船舶。式(14)表明服务同一艘船舶的所有岸桥的结束时间相同。式(15)表示船舶分配的岸桥数不能超过泊位限制的最大岸
19、桥数。式(16)表示对任一艘船舶,初始分配的岸桥数不一定是最终服务船舶的岸桥数,因为存在其它岸桥在船舶服务过程中调度过来的情况。式(17)式(20)限制岸桥不能跨越。式(21)式(22)表明岸桥的调度需遵循公平的岸桥分配原则。4基于优先权和Q值的求解过程上述模型属于非线性混合整数规划模型,求解过程较为复杂。在解决泊位一岸桥优化问题时,仅在泊位分配时采用改进的遗传算法。具体求解过程如下图1所示。图1 求解流程图41染色体编码采用自然数编码,每个染色体代表一个停泊方案,包括泊位,船舶服务顺序及每个?自位的船舶停泊次序。在染色体中,除0外每个基因表示船舶服务的顺序,用0把每个泊位隔开。42初始种群有
20、J艘到港船舶,对应不同的服务顺序。假设有工个泊位,在1,2,(,一1)之间随机选择(卜一1)个点,在选择的(卜一1)个点后插入“0”,这样就生成一个泊位分配计划的染色体编码,如此反复直到满足设定的初始种群数目。43变异在既定的船舶服务顺序下,变异的目的是拓展船舶停泊方案的多样性。从一个染色体编码中随机选择两个基因,然后交换两个基因的位置。44交叉交叉操作能够以较大幅度调整船舶停泊方案,具体操作如图2图5所示。图2表示8艘到港船舶对应靠泊优先权所确定的船舶服务顺序。图3表示在染色体1中随机选取、标记两个基因位置,并在染色体2中标记对应位置。图4表示首先将两条染色体中所选中基因片段进行交换。进而在
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 公平 原则 泊位 一岸桥 联合 调度 研究 范丽先
限制150内