An efficient approach for solving yard crane scheduling in a container terminal

An efcient approach for yard crane（YC）scheduling is proposed in this paper.The definition of task group for YC scheduling is proposed.A mixed integer programming（MIP）model is developed.In the model,objective functions are subject to the minimization of the total delay of complete time for all task groups and the minimization of block-to-block movements of YCs.Due to the computational scale of the non-deterministic polynomial（NP）complete problem regarding YC scheduling,a rolling-horizon decision-making strategy is employed to solve this problem,by converting the MIP model into another MIP model in the scheduling of each rolling period.Afterwards,a heuristic algorithm based on modified A＊search is developed to solve the converted model and obtain near optimal solution.Finally,the computational experiments are used to examine the performance of the proposed approach for YC scheduling.     

考虑能耗的铁水联运集装箱装卸设备协同调度

随着集装箱港站铁水联运作业量增大,以及节能减排压力与日俱增,实现港站作业设备的高效调度和低能源消耗间的协同优化将是亟待解决的问题.本文研究了集装箱铁水联运港站中多设备间的高能效协同调度问题,基于混合流水车间调度(HFSS)思想,构建了综合考虑岸桥、集卡、正面吊三阶段装卸过程的协同调度模型,以总完成时间最短和能耗最低为目标,设计了基于遗传算法和模拟退火的混合优化算法.通过实验验证了模型和算法的可行性,证明可以实现高能效利用下的港站设备协同调度优化.     

面向班型动态生成的地服人员排班算法

面向班型动态生成的地服人员排班旨在动态生成班型,并将员工分配到班型中,以班型为航班地面保障单元.现有面向班型的人员排班算法是建立在固定班型数和班型内的员工资质数,未考虑班型数未知的重要前提.为此,提出面向班型动态生成的地服人员排班算法,其核心思想是通过block Gibbs抽样迭代优化班型内人员构成、班型内航班集和班型生成.在某机场值机人员的数据集中验证此算法,实验结果表明,在满足员工层次资质、员工白夜班和班型动态生成的约束下,算法能够生成合理的班型.     

基于地铁乘务资源共享的排班计划优化方法

针对不同线路间列车不跨线情况下的乘务基地和乘务员共享问题开展研究,分析乘务资源共享，在传统排班模型基础上考虑乘务员跨线值乘，班次出退勤地点比例及其鲁棒性优化，建立乘务排班计划集合覆盖模型。针对乘务资源共享后多线协同优化引起的问题规模显著增大，以连续值乘区段为最小值乘任务单元构建网络图，引入分层结构，多级的汇点和源点，以及跨线就餐和间休弧等以满足班次的可行性约束。构建对应不同出退勤地点属性的网络图集合，将定价子问题转化为网络图集合的最短路问题以进行列生成法求解。案例结果表明：相比于分线单独优化，乘务资源共享可为乘务员提供更多的出退勤地点选择，显著降低其通勤时间；此外乘务资源共享可少量节省乘务班次数，提高排班计划效率。     

基于拉格朗日的高速铁路车站作业优化

本文从Job-Shop 调度角度出发,以列车为待加工的“工件”,将车站接车进路、 到发线和发车进路看作“加工机器”,列车在车站的走行与停站看做不同的“作业工序”, 把高速铁路车站作业问题抽象成Job-Shop 车间调度优化,以设备能力、冲突进路、停站时 间为空间和时间约束,以最小化到发线的占用时间为优化目标,建立高速铁路车站作业 优化模型.采用拉格朗日方法松弛原模型的约束条件,建立车站技术作业问题的拉格朗日 对偶松弛问题,设计了高速铁路车站作业优化模型算法.并以高速铁路的某一车站为实例 进行验证,实例表明,该算法可以有效地化解车站作业进路冲突和实现到发线运用时间 的最小化.     

公共自行车多层次分区调度方法研究

公共自行车发展的制约性问题在于调度滞后,服务水平无法满足用户需求.从时间分布和空间分布两方面分析了公共自行车高峰期潮汐需求规律及其与用地类型的关系.创新地提出以上层调度区域、调度小区和站点为主的多层次分区调度方法.在详细分析了各层次分区流程及相关参数的基础上,提出结合虚拟小区与有时间窗的多目标优化调度模型解决区间调度问题,并且建立了小区内调度的最优路径模型.形成区间灵活调度,区内路径固定的半确定调度体系.案例证明该方法具有较强的可操作性.该方法在保证高峰期及时调度,减少不必要的绕行和拥堵时间,提高调度效率,减少盲目性等方面具有重要意义.     

基于动态学习的泊位调度方案优化

泊位调度方案的制定要依据在泊船舶的占用泊位情况及预计在泊时间,确定其他待泊船舶的靠泊位置与靠泊时间.然而,预计在泊时间受水文气象等多种复杂因素的影响,且影响程度是随时间动态变化的,给泊位调度方案的制定增加了难度.对此,本文采用动态学习方法对在泊时间计算函数进行更新,再基于所得函数对泊位调度方案进行优化.并设计了包含船舶在泊时间动态学习及泊位调度方案优化的并行算法,前者为后者提供更新的在泊时间计算函数,后者的实际执行结果为前者提供学习样本.通过算例对模型有效性进行了验证,结果表明：加入动态学习过程,船舶在泊时间的计算偏差得以降低;优化方案的平均在泊时间缩短2.4 h,总成本降低11.1%.     

集装箱码头铁水联运装卸设备协同调度

集装箱码头铁路作业区是开展集装箱铁水联运的主要场所,其效率将影响集装箱铁水联运的整体效率,因而,建立了以装卸过程总完成时间最短为目标的龙门吊、集卡和场桥的协同调度问题的混合整数规划模型,既考虑了装卸同步,又考虑了龙门吊间的干扰和安全距离、龙门吊和场桥走行时间及缓冲区等现实约束,并考虑了集卡堵塞问题.为了求解模型,设计了改进的多层遗传算法.最后通过实验验证了模型和算法的有效性和可行性,证明了考虑集卡堵塞问题是有必要的,并给出了50个和100个集装箱的设备最佳配比.     

基于时间和能耗权重的密集停车场调度策略

平面密集停车是一项全新的停车方案,利用四向移载设备配合停车托盘来实现密集停车功能. 为研究其调度问题,利用改进最短路径算法求解平面密集停车场内任一车位上车辆出库调度的综合最短路径. 不同客户对时间和费用的偏好不同,电机空载和满载时能耗不同导致调度成本不同,故引入时间权重和能耗权重两项指标建立数学模型. 通过仿真模拟,实验结果验证了模型的可行性. 研究结果表明,建立的车辆调度模型可用于密集停车场的出库调度,在保证车辆调度出库时间合理的基础上节约能源消耗、降低成本,实现了经济环保的目标.本研究对智能平面密集停车场的推广应用做出了一定的贡献.     

基于时间和能耗权重的密集停车场调度策略

平面密集停车是一项全新的停车方案,利用四向移载设备配合停车托盘来实现密集停车功能. 为研究其调度问题,利用改进最短路径算法求解平面密集停车场内任一车位上车辆出库调度的综合最短路径. 不同客户对时间和费用的偏好不同,电机空载和满载时能耗不同导致调度成本不同,故引入时间权重和能耗权重两项指标建立数学模型. 通过仿真模拟,实验结果验证了模型的可行性. 研究结果表明,建立的车辆调度模型可用于密集停车场的出库调度,在保证车辆调度出库时间合理的基础上节约能源消耗、降低成本,实现了经济环保的目标.本研究对智能平面密集停车场的推广应用做出了一定的贡献.     

非标准HFS-B问题的设备协同调度研究

在同贝位边装边卸工艺的集装箱作业环境中,提出了一类非标准的HFS-B问题,即同时存在2种方向互逆的工件流、与紧前紧后机器相关的准备和处理时间.这类来自港口背景的非标准HFS-B问题,主要涉及空间位置决策、任务分配和设备调度等子问题的决策,目标是makespan最小.鉴于HFS-B的NP-hard特性,在分析设备顺序约束和协同关系基础上,基于Fill ratio启发式、表调度理论和设备的状态空间变换,设计了3阶段决策的启发式算法.基于阶段的下界理论和makespan的下界理论,对多个实际的大规模案例进行仿真分析,结果表明:算法的makespan与理论下界的最大偏差不大于7%,具有良好的实用性.     

具有反向学习能力的串车调度算法研究

为了避免串车问题,研究了多条线路不同站点间隔的车辆实时串车调度算法.基于车辆自动定位(AVL)数据的分析预测,给出了具备反向学习能力的克隆选择优化算法 (Opposition-learning Clonal Selection Algorithm, OCSA )求解避免串车的调度序列,指导车辆调度.算法中设计了反向抗体库,反向抗体库存储了种群迭代过程中多个较差抗体的信息,利用较差基因位置信息,指导部分基因链以较快速度进行反向学习,将其迅速牵引出局部最优区域.反向学习过程可迅速改善抗体的多样性,使得算法在短时间内具有较强的全局寻优能力;且局部学习的缩放因子可随迭代过程动态调整,提高了算法的求解精度.实验结果表明,基于 OCSA算法获取的调度序列与经典的调度算法相比有较好的适应性,求得的调度序列能够实时有效地降低站点串车问题.     

基于泊位计划的集装箱码头岸桥动态调度优化

所谓基于泊位计划的集装箱码头岸桥动态调度问题,是指在计划周期内,在每艘船舶均已安排了靠泊时间和靠泊位置的前提下,将有限的岸桥资源在船舶上的装卸任务间进行动态分配与排序,以最大限度地减少计划期内所有船舶的滞港时间. 在充分考虑岸桥不能交叉作业、装卸任务有作业顺序要求等现实约束下,对此问题构建了非线性数学规划模型,基于问题自身的特点设计了基于任务排序的染色体结构,用遗传算法进行求解. 通过与文献中单船的调度结果的对比、单船岸桥调度与多船动态岸桥调度结果的对比,以及多船动态岸桥调度的仿真实验,证明了模型及算法的有效性.     

集装箱码头集成调度研究综述

按照不同的研究区域, 总结了集成调度在码头前沿、码头堆场以及码头前沿和堆场间等方面的国内外文献, 并提出了未来的研究方向。研究结果表明: 多数文献研究的是传统集装箱码头的集成调度问题, 并取得了较多成果, 也有少数文献研究了自动化码头的集成调度问题, 随着科技的发展和自动化码头的增多, 在今后的研究中, 应结合自动化码头的特点, 研究自动化码头内的设备集成调度问题; 多数文献都是在静态或确定情况下研究集装箱码头的集成调度问题, 只有极少数文献考虑了码头生产调度过程的动态或不确定性, 因此, 随着研究的逐步深入, 动态或不确定因素下的集成调度问题将成为未来的研究重点; 多数文献均建立了以时间、成本最小或二者相结合的目标函数, 虽然也有助于提高码头的生产效率, 但是依旧存在一定的局限性, 随着能源问题的日益严重, 在未来的研究中, 应建立均衡能耗和其他优化目标的多目标模型; 多数文献中设计了启发式算法, 并获得了较好的优化解, 为了使求解方法更加多元化, 应将算法计算与仿真验算相结合; 随着多式联运的兴起, 应在考虑铁路作业区对整个集装箱码头影响的基础上研究铁路作业区与码头间的集成调度问题。      

A Class of Single Machine Scheduling Problems with Variable Processing Time

In this paper, single machine scheduling problems with variableprocessing time are raised. The criterions of the problem considered are minimizing scheduling length of all jobs, flow time and number of tardy jobs and so on. The complexity of the problem is determined.     

Development of a theory of constraints based scheduling system for ship piping production

Manufacturing of ship piping system is one of the major production activities in shipbuilding. The schedule of pipe production has an important impact on master schedule of shipbuilding. In this research, the theory of constraints (TOC) concept is introduced to solve the scheduling problems of piping factory, and an intelligent scheduling system is developed. The system integrates a product model, an operation model, a factory model and a knowledge database of piping production and can make the process planning and production scheduling automatically. In the paper, details of above points are discussed. Moreover, an application of the system in a piping factory, which achieves a higher level of performance as measured by tardiness, lead time and inventory, is demonstrated at the end of the paper.     

考虑行程时间波动的电动公交可变行车计划

为解决因运行时间不确定性导致的公交到发时间不准点问题,本文基于公交线路双方向发车趟次和运营时间的不对称特征,提出一种可变行车计划优化问题。以最小化车辆使用数和乘客等待时间为目标,考虑车次链的行程接续和电动公交车辆电量等约束,构建公交时刻表和车辆排班一体化优化模型。根据可变行车计划优化问题特性设计改进的粒子群算法(Modified Particle Swarm Optimization for Timetabling and Scheduling, MPSO-TS)进行求解,定制粒子编码和子代更新方式。采用“基于优势车次链”的子代更新机制,以“车次链”为纽带最大程度地保留父代被继承信息中时刻表与车辆调度方案之间的关联性。使用连云港市某公交线路验证模型和算法,案例结果表明：可变行车计划能够有效保证车辆到发准点性,通过更紧密的排班计划将使用车数由35辆减少至31辆,车辆使用效率提升了28.1%;所提出的MPSO-TS算法求解效率较高,具有较好的稳定性,可有效避免计算结果陷入“局部最优”。     

延误航班机场场面滑行优化调度策略研究

为减少大面积航班延误带来的机场拥堵和安全隐患,提出了将解决延误航班调度过程转化为求解流水车间调度问题（flow-shop scheduling problems,FSP）.以航空器总体调度滑行时间最小为目标,建立延误航班滑行调度模型,设计多粒子群算法求解模型.算例分析表明,该调度模型较之比FCFS方案在一个高峰时段内能减少14.2min调度时间,提高了机场运行效率.     

��ɫ����ʱ������򹫽���������ģ�ͺ��㷨

区域公交调度是未来城市公共交通的发展趋势,主要解决如何合理统一安排最初分布于不同车场的车辆完成所有线路固定时刻表对应班次任务,从而减少车队规模和降低营运成本.考虑现实中许多突发事件干扰车辆按时完成班次,本文研究一类灰色旅行时间的区域公交车辆调度问题.在满足多车型、车场容量限制、燃料限制等现实因素基础上,设计改进蚁群算法,编制一个最低营运费用的公交调度方案.该方案可适应不断变化的交通环境,更容易在公交运营中被应用.最后,通过算例验证了模型和算法的正确性.     

���������ij������������ģ�����㷨�о�

在对多配送中心车辆调度问题进行直观描述的基础上，建立了该问题的数学模型。提出了采用距离最近分配法将多配送中心车辆调度问题分解为多个单配送中心车辆调度问题进行求解的策略．基于求解单配送中心车辆调度问题的禁忌搜索算法，设计了求解多配送中心车辆调度问题的算法，并进行了实验计算．计算结果表明，用本文设计的算法求解多配送中心车辆调度问题，不仅可以取得很好的计算结果，而且算法的计算效率较高，收敛速度较快，计算结果也较稳定．