动态需求下跨码头集卡调度问题研究

18-1-动态需求下跨码头集卡调度问题研究1引言随着国际集装箱运输业的迅猛发展，现代港口集装箱码头向大型化、信息化、自动化和智能化方向发展。同时，港口所面临的经营与竞争压力越来越大，降低码头的装卸成本，提高集装箱的装卸效率，是各个港口码头关注的重要领域。特别是当装卸工艺基本确定后，装卸设备的配置不均衡性是港口集成化运营面临的主要难题。集装箱卡车(简称集卡)运输是集装箱码头作业系统中的重要环节，衔接前沿岸桥和后方龙门吊的工作。目前国内很多港务集团下港口都设有多个码头，各自采用内集卡作为水平运输资源。港口大部分集卡调度系统普遍采用某码头单管一定数量的集卡的传统调度规则。传统集卡分配模式是根据本码头的实际操作业务量，对每个码头配备50～60辆集卡,配备的集卡就始终为该码头服务直至泊位工作终止。而集装箱码头的装卸任务量在不同时段往往有较大的差别，集卡的空闲程度也不同，此种调度规则下集卡在作业量较少时会产生空置的情况。这种模式便于管理集卡但不利于进一步提高集装箱码头机械设备的利用率，难以适应多泊位现代化集装箱码头生产管理的发展需求。因此采用集约化方式对集卡进行统一的跨码头调度是目前研究的热点。2跨码头集卡调度问题描述跨码头集卡动态调度是根据某时刻码头申请的集卡需求动态地调度集卡。设立一个集卡总调度中心集约化管理港口所有的集卡,使各个码头共享所有的集卡。各码头可根据当日码头作业计划向总调度中心提前预定一定数量的集卡，当某码头集卡无法满足码头作业要求时可提出申请额外的集卡，而当码头有空闲集卡即可申请退订。总调度中心可根据申请合理地就近从其他码头调度空置的集卡，各码头其余空置集卡则调回总调度中心。灵活地满足各码头对集卡的不同需求，从而在保证码头作业效率的基础上大幅度减少集卡数量并提高资源的利用率。图1集约管理港口集卡图2业务概述跨码头集卡调度的主要决策内容是：对于任一正常作业状态的集卡，是否将其调运至其他码头或总调度中心，从而满足租用方（码头）的申请及退订要求。集卡资源的分配必须遵循一定的规则，主要有以下几点：（1）按需分配原则。需求量是各码头根据其实际作业情况向总调度中心申请的集卡数量。当码头业务较繁忙而集卡无法满足码头作业需求时，需要向总调度中心额外申请的需要集卡。总调度中心分配给该码头的集卡数量应不大于该码头的申请量，并尽量满足码头的申请需求。（2）调回原则。调回原则指的是对于某码头申请退订的集卡，必须调离该码头，即就近调度至需要的码头，或者调度回总调度中心。（3）就近调度原则。集卡跨码头调度需考虑码头与码头之间的调运成本，该成本和码头之间的距离有关。例如码头A申请退订集卡而码头C申请需求额外的集卡的情况。若将集卡从码头A直接调运至码头C的距离要大于集卡从码头A先调运至总调度中心再从总调度中心调运至码头C的距离，此时则选择后一种调运方案。图3就近调度原则（4）工时平均原则集卡的有效工时指的是集卡调入总调度中心的时间减去上一次调出总调度中心的时间的差。为尽量均衡个集卡之间的作业强度，优先调度有效工时少的集卡至其他码头作业。若将码头退订的空置集卡调回总调度中心，优先调度有效工时相对较多的集卡回调度中心。图4工时平均原则（5）等级需求。对于难度较高的装卸作业任务，某些码头可以对集卡司机的经验等级提出要求。例如在处理危险品货物的情况下，可申请经验较为丰富的司机操作作业。3集卡跨码头调度模型构建3.1符号定义（1）维度（实体）的表示符号t，表示第t辆待调度的集卡。i/j，表示第i/j个码头，模型中将总调度中心设置为一个虚拟码头。l，表示集卡对应的司机经验等级，从高到低依次可分为甲、乙、丙、丁四个等级。（2）已知参数的表示符号，binary，用于描述第t辆集卡是否处于第j个码头。1表示第t辆集卡当前时刻处于第j个码头，0则相反。，用于描述第j个码头的集卡需求量。由各码头根据当前作业情况提出申请。，用于描述码头j的特殊等级需求。表示码头j对司机等级为l的集卡的需求量。它与装卸货物的特征有关。，binary，表示码头j是否有特殊等级需求。1表示码头j有水平等级l的需求，0则相反。，用于描述码头i申请的司机水平等级为l的集卡退订数量。，用于描述集卡从第i个码头调度到第j个码头的调运成本。它和码头i的码头j之间的距离有关。，binary，表示第t辆集卡对应的司机经验等级。1表示集卡t对应的司机经验等级为等级l，0则相反。，用于描述集卡t的有效工时。，binary，1表示码头i是总调度中心，0则相反。，表示码头j分配集卡资源的优先系数。描述码头对于需要集卡调度的重要程度。（3）决策变量的表示符号，模型的决策变量，binary，用于计算是否将集卡t调运至码头j。3.2模型约束条件构建（1）按需分配限制根据各码头向总调度中心提出的申请，可获得当前时刻码头集卡的空闲状态。当码头业务较繁忙而集卡无法满足码头作业需求时，就反馈所另需的集卡数量至总调度中心，即可得实时集卡需求量。在尽量满足各码头需求的前提下，总调度中心安排实际调度出的集卡数量应不超过统计的需求量，以免造成资源浪费以及增加调度成本。图5按需分配原则模型中该约束方程表示如下：不等式的左边，为关于t，j的二维01矩阵，对t求和后得到调度至码头j的集卡数量。不等式的右边是实时统计的码头j的集卡需求量。为满足资源需求限制，使得左边小于等于右边。（2）调回约束当码头的作业任务所需的集卡数量小于原先预定的集卡数量时，就会造成部分集卡处于空置的状态，空置集卡的数量即可为该码头申请的集卡退订量。对于某码头申请退订的集卡，必须调离该码头。因此，实际调出的l等级集卡应等于申请的退订量。图6调回原则模型中该约束方程表示如下：等式的左边，二维01矩阵、和相乘可得关于t，j，i，l的四维01矩阵，其中1表示从码头i调出且对应司机等级为l的集卡被调度至了码头j，0则表示该集卡t未被调度至了码头j。对j，t求和，可得到从码头i调出且对应司机等级为l的集卡数量。等式的右边，变量表示码头i申请的司机等级为l的集卡退订数量。等式两边乘以，表示码头i为总调度中心时，该约束不起作用。令左边等于右边，对集卡调回量进行约束。（3）等级需求约束。在某些特殊情况下，各码头需要根据业务的情况申请一定数量的特定等级的集卡。例如在处理危险品货物的情况下，需要经验等级为甲级的司机操作作业。在集卡调度时应尽量满足码头对集卡司机经验等级的要求，同时实际调出的该等级的集卡应不超过需求量。图7等级需求原则模型中该约束方程表示如下：不等式的左边，二维01矩阵和二维01矩阵相乘可表示得关于t，j，l的三维01矩阵，其中1表示对应司机等级为l的集卡t被调度至了码头j，0则表示该集卡t未被调度至了码头j。对t求和，可得到调度至码头j且对应司机等级为l的集卡数量。不等式的右边，变量表示码头j对司机等级为l的集卡的需求数量。令左边右边，对调度至各码头且为各特定等级的集卡数进行约束。（4）唯一性约束该约束保证一辆空置集卡只能分配给一个码头。集卡t指派给码头i后，就不能再将其指派给码头j。图8唯一性约束模型中该约束方程表示如下：3.3模型的目标函数构建（1）目标1——最大化集卡调运数量最大化集卡调运数量指的是在不超过码头所申请的集卡需求量的前提下，尽量满足该码头的需求，即分配量最大。满足该限制原则的目标函数可表示如下：表示集卡调度至各码头应考虑优先系数。考虑到在实际调运中，集卡t应优先调度至其他码头j，不考虑分配给作为一虚拟码头的总调度中心。因此，为保证集卡可被调运至需要的码头，对于，总调度中心的优先系数应远小于其他码头。表示调度至码头j的集卡数量，使其最大化，即尽量满足码头的需求。（2）目标2——最小化调运成本集卡跨码头调度需考虑码头与码头之间的调运成本，即和码头之间的距离有关。若将集卡调运至码头i，应从与其距离最短的码头j调运。集卡调运的总成本可表示如下：表示集卡t从码头i调运至码头j的调运距离，对其求和可得所有被调度的集卡的总调运距离。使最小化，即可实现该子目标。（3）目标3——优先调回工时较长的集卡为满足工时平均化原则，将码头退订的空置集卡调回总调度中心时，应优先调度有效工时相对较多的集卡回调度中心。即对于调回总调度中心的所有集卡，其有效工时之和应最大化。该目标函数可表示如下：表示调回总调度中心的集卡t的有效工时，对其求和可得调回总调度中心的所有集卡的有效工时之和。使其最大化，可实现该子目标。（4）目标4——优先调派工时较短的集卡如从总调度中心调出集卡，则优先调度有效工时少的集卡至其他码头作业。即从总调度中心调出的所有集卡的有效工时最小。该目标函数可表示如下：表示从总调度中心调出的集卡t的有效工时，对其求和可得从总调度中心调出的所有集卡的有效工时之和。使最小化，可实现该子目标。（5）目标5——尽量满足对集卡等级的特殊需求码头在处理特殊货物时，对集卡对应司机的经验等级有特殊的需求。最大等级需求分配指的是对于某个特定的司机经验等级，在不超过码头申请的集卡需求量的前提下，尽量满足该码头的等级需求，即是该等级分配量最大。表示对应司机等级为l的集卡调度至了码头j，乘以二维01矩阵后，使得该目标只对有特殊等级需求的码头有效。则表示调度至码头j且对应司机等级为l的集卡数量，使其最大化，即尽量满足码头的等级需求。（6）总目标函数本模型是一个多目标规划问题，总的目标函数可表达如下：a、b、c、d为目标函数的优先因子。子目标5是子目标1的特例，因此两目标之间优先满足目标5，而子目标1的重要级又高于其余子目标，因此本目标函数的优先级取即可。4模型求解及算例分析4.1模型求解4.2算例分析某港口设有四个码头进行生产作业，分别为码头A、码头B、码头C及码头D。假设总调度中心配置有30辆集卡，分别为T01、T02、T03……T30，码头可根据需求提前预定。而集卡对应的司机经验等级，从高到低依次可分为甲、乙、丙、丁四个等级。4.2.1已知参数数据（1）集卡信息总调度中心配置有30辆集卡，其中12辆甲等级集卡，7辆乙等级集卡，5辆丙等级集卡及6辆丁等级集卡。具体集卡对应的司机经验等级的矩阵可表示为下表：表1由上矩阵可知，矩阵元素为1的则表示该集卡对应某特定司机等级，例如集卡T01对应的司机等级为甲等级，集卡T21对应的司机等级为丙等级。（2）集卡位置信息根据当天计划，码头A提前预定9辆集卡，其中5辆甲等级集卡和4辆乙等级集卡。码头B预定5辆集卡，其中3辆丙等级和2辆丁等级。码头C预定7辆集卡，其中4辆甲等级集卡、2辆乙等级集卡和1辆丙等级集卡。码头D预定4辆集卡，其中3辆丁等级集卡和1辆甲等级集卡。而总调度中心剩余5辆集卡，其中2辆甲等级集卡、1辆丁等级集卡、1辆丙等级集卡和1辆乙等级集卡。集卡具体情况可见下矩阵：表2由上矩阵可知，集卡T01、T02…T09分配给码头A，集卡T10、T11…T14分配给码头B，集卡T15、T16…T21分配给码头C，集卡T22、T23…T25分配给码头D，而剩余的集卡T26、T27…T30由总调度中心管理。（3）码头需求数据码头需求可分为对集卡数量的需求以及对特定等级的需求，码头集卡需求量包含特殊等级的集卡需求数。码头A需求3辆集卡，其中甲等级集卡3辆。码头B需求2辆集卡，其中乙等级集卡2辆。码头C不需要集卡。码头D需求3辆集卡，无经验等级的特殊需求。具体需求情况见下矩阵：表3申请需求甲乙丙丁总需求码头A33码头B22码头C码头D3（4）特殊等级退订数据根据当前的作业情况，码头A处理危险品货物的装卸，需要经验丰富的司机进行操作作业，因此将不满足条件的4辆乙等级集卡退订，并需求3辆甲等级的集卡。码头C退订1辆甲等级集卡，码头B、码头D则无特定等级退订量。其矩阵可如下所示：表4退订需求甲乙丙丁码头A4码头B码头C1码头D（5）调运成本集卡的调运成本与码头之间的距离有关。该港口四个码头的位置如图1所示，根据码头之间距离的相对比例，调运成本可用如下矩阵表示。表5调运成本总调度中心码头A码头B码头C码头D总调度中心15151723码头A15102245码头B15101236码头C17221220码头D23453620（6）有效工时集卡的有效工时指的是集卡调入总调度中心的时间减去上一次调出总调度中心的时间的差。该港口在调运集卡时考虑集卡的工作时间。集卡具体情况如下表所示。表6集卡有效工时集卡有效工时集卡有效工时T018T114T213T024T126T222T035T137T234T043T142T241T057T158T256T069T164T263T073T177T275T082T185T284T095T197T297T104T207T3054.2.2结果分析决策结果如下表所示。表7调运方案码头A码头B码头DT061T071T081T091T151T261T271T281图9决策结果最优调运方案为：将集卡T06、T08从码头A调运至码头B，集卡T07、T09从码头A调运至码头D，集卡T15从码头C调运至码头A，集卡T26、T27从总调度中心调运至码头A，集卡T28从总调度中心调运至码头D。（1）满足按需分配原则。根据申请需求，总调度中心分配给码头A的集卡数量应不超过3辆，分配给码头B的集卡数量应不超过2辆，分配给码头D的集卡数量应不超过3辆，并尽量满足码头的申请需求。总调度中心将为T15、T26、T27的3辆集卡分配给码头A，将为T06、T08的2辆集卡分配给码头B，将为T07、T08、T28的3辆集卡分配给码头D，均满足按需分配原则。（2）满足调回原则。码头A申请退订的4辆集卡，2辆被调运至码头B，2辆被调度至码头D。码头C申请退订的1辆集卡，被调度至码头A。满足某码头申请退订的集卡，必须调离该码头的原则。（3）满足最大等级需求分配。根据申请特殊等级需求，总调度中心分配给码头A的甲等级集卡数量应不超过3辆，分配给码头B的乙等级集卡数量应不超过2辆。总调度中心分配给码头A为T15、T26、T27的3辆集卡均为甲等级，分配给码头B为T06、T08的2辆集卡均为乙等级。在不超过码头申请的集卡需求量的前提下，尽量满足该码头的等级需求。（4）满足最小调运成本。码头A申请需求3辆甲等级集卡，码头B申请需求2辆乙等级集卡，码头C申请需求3辆集卡。考虑各码头之间的距离，将码头C退订的1辆甲等级集卡以及总调度中心的2辆甲等级车调运至码头A，将码头A退订的2辆乙等级集卡调运至码头B，将码头A退订的另2辆集卡以及总调度中心的1辆集卡调运至码头D。在满足特殊需求的情况下，此时的调运距离最短，调运成本最小为237。由于从码头A至码头D的距离比至其他码头距离长，两码头间的集卡调运数量增加，调运成本增加的幅度也会提高。若将码头A退订的1辆集卡调运至码头B，另3辆集卡调运至码头D，此时总调运成本增加至238。（5）满足工时平均原则。根据具体情况，需要从总调度中心调1辆集卡至码头D。总调度中心的集卡T26已分配给码头A，剩余的4辆集卡T27、T28、T29、T30的有效工时分别为5、4、7、5。选择调运有效工时最少的集卡T28，满足优先调度有效工时少的集卡至其他码头作业的原则。而退订的集卡无调回总调度中心的情况，因此优先调度有效工时相对较多的集卡回调度中心的原则不作考虑。（6）满足唯一性约束。进行调度的集卡T06、T07、T08、T09、T15、T26、T27、T28，都只分配给一个码头，满足唯一性约束。4.3求解效率分析通过进行大量的算例分析及系统测试，可证明此决策系统性能良好，在实际进行决策的过程中能保持高效率的运行计算。不同的算例所需计算时间及占用内存对比情况如下表所示。此决策系统在变量数较多的情况下仍能保证所需的计算时间较短，且占用内存较小，运行性能良好，求解效率较高，可运用于实际的问题求解。算例码头数集卡数变量数SolvingTimePeakMem算例1210200.02sec1.1Mb算例2220400.02sec1.2Mb算例3320600.03sec1.3Mb算例43401200.05sec1.8Mb算例54301200.04sec1.6Mb算例64401200.05sec1.8Mb算例75241200.04sec1.7Mb算例85402000.07sec2.1Mb算例96503000.09sec2.7Mb算例106603600.09sec2.8Mb下图表为各算例计算时间的对比情况，变量个数为20~120的算例，所需计算时间呈递增趋势且增势平缓；而变量个数为200~360的算例，所需计算时间呈递增趋势且增幅较之前略大。下图表为各算例占用内存的对比情况，变量个数为20~120的算例，占用内存的大小呈递增趋势且增势平缓；而变量个数为2