Berth allocation planning in Seville inland port by simulation and optimisation

We study the problems associated with allocating berths for containerships in the port of Seville. It is the only inland port in Spain and it is located on the Guadalquivir River. This paper addresses the berth allocation planning problems using simulation and optimisation with Arena software. We propose a mathematical model and develop a heuristic procedure based on genetic algorithm to solve non-linear problems. Allocation planning aims to minimise the total service time for each ship and considers a first-come-first-served allocation strategy. We conduct a large amount of computational experiments which show that the proposed model improves the current berth management strategy.     

基于计算物流与计算智能的多码头泊位堆场联合调度

针对同一地区邻近集装箱码头往往物流功能相似、货源腹地重叠、无序竞争突出和资源利用率较低等特点, 本文重点探讨了隶属于同一组织内且位置相邻多集装箱码头的泊位-堆场一体化计划调度(multiple container terminal tactical berth and yard incorporate integrative scheduling, MCT-TBY-IIS)问题. 基于计算物流, 利用多重多背包问题将MCT-TBY-IIS抽象和分解为考虑泊位水深约束和出口集装箱可转港作业的多码头动态连续泊位分配和多码头周期滚动堆场分配两个中度耦合子问题, 进而在计算物流面向问题探索的思想下, 提出了面向层次嵌套结构的二阶段改进帝国竞争算法(hierarchical nesting oriented two-stage improved imperialist competitive algorithm, HNO-TSI-ICA)对MCT-TBY-IIS进行求解优化. 最后, 面向我国东南沿海的典型多码头联合作业实例, 遴选出面向帝国兴替的双同化帝国竞争改进算法和面向0-1背包问题的二进制帝国竞争算法组合应用于HNO-TSI-ICA, 其在求解MCT-TBY-IIS时效果较好, 且堆场作业子系统目标成本的结构较稳定, 其不受计划期内港口负荷和计划周期长度的影响, 其中, 出口箱区集装箱水平运输成本的贡献度在堆场作业子目标成本的比重最大, 稳定在83%左右. 通过对MCT-TBY-IIS的建模与优化, 可以发现多码头联合作业模式有较好的潜力帮助同一组织内邻近的多码头降本增效和提高核心资源的利用率.     

A bi-objective model for robust berth allocation scheduling

Berth allocation is an important port operation problem for container terminals. This paper studies how to develop a robust schedule for berth allocation that incorporates a degree of anticipation of uncertainty (e.g., vessels’ arrival time and operation time) during the schedule’s execution. This study proposes a bi-objective optimization model for minimizing cost and maximizing robustness of schedules. A heuristic is also developed for solving the bi-objective model in large-scale problem cases. Numerical experiments are conducted to validate the effectiveness and efficiency of the proposed model and method. Managerial implications are also discussed.     

A network flow model for the dynamic and flexible berth allocation problem

This paper presents a new model for the dynamic berth allocation problem (BAP). The model is developed using a berth-flow network modeling approach and is formulated as an integer multi-commodity network flow problem. In addition, an innovative flexible berth-space utilization scheme, based on blocking plans, is incorporated into the proposed model. This is referred to as the dynamic (vessel arrivals) and flexible (berth space) BAP model (or DFBAP), and is designed to better utilize wharf space in a container port. Computational experiments conducted on an instance generated using actual data show that the DFBAP model is more effective and efficient than the method currently used by port authorities. A set of scenario analyses is also performed to obtain insights into important model parameters.     

Collaborative mechanisms for berth allocation

This paper proposes two collaborative mechanisms between container shipping lines and port operators to facilitate port operators to make proper berth allocation decisions. In the first mechanism, assuming no transshipment, a shipping line needs to provide the port operator with the utilities associated with the start operation days of each liner route. The total utilities for all start operation days must be 0. A higher bunker and inventory cost for the shipping line means a lower utility. The port operator compensates the shipping line if its ship is scheduled on a day with negative utility and charges additional fees if the ship is scheduled on a day with positive utility. The second mechanism accounts for the utilities related to the inventory cost of transshipment containers. These two mechanisms ensure that shipping lines have no incentive to overstate or undervalue the utilities. The utilities estimated by shipping lines are much more accurate than those estimated by port operators. Hence, models for the tactical berth allocation problem incorporating the utilities provided by shipping lines lead to more efficient and equitable berth allocation plans. The utilities provided by shipping lines can also guide the decisions on operational berth allocation.     

桥吊可动态分配的连续泊位分配问题算法

研究在允许桥吊动态分配的情况下集装箱码头的连续泊位动态分配问题,并建立以船舶在港时间最小为目标的动态泊位分配模型;然后基于兄弟-儿子方法对船舶的位置进行调整以规划桥吊使桥吊不交叉。在相同算例下,比现有方法得到的船舶在港时间更少,从而验证了模型及算法的有效性。     

多场桥分区域平衡策划下的集装箱堆场箱位分配问题

集装箱码头堆场出口箱箱位分配和场桥调度对码头运营效率有重要影响. 为了合理分配箱位和调度场桥, 采用分区域平衡策划方法, 在给定批量任务下, 考虑场桥实际作业中的安全距离, 以均衡各场桥作业任务量和减少场 桥的非装卸时间为目标, 建立混合整数规划模型, 并设计遗传算法求解, 通过不同批量任务的实验分析验证所提出方法的有效性. 研究表明, 分区域平衡策划方法可以更好地解决箱位分配和箱区多场桥联合作业的优化问题.

     

MapReduce下连续泊位分配系统

针对传统串行环境下码头连续泊位分配算法在船数大于七条时,算法的执行效率明显降低、资源占用量显著增加.首次设计了基于分布式环境下连续泊位分配系统总体架构和软件架构;提出了基于Hadoop平台下连续泊位分配系统开发环境的搭建,分布式环境下码头泊位分配系统组件设计与部署以及分布式环境下基于MapReduce改进连续泊位分配算法的关键技术;最后实现了分布式环境下连续泊位分配系统.实验结果表明,该系统可以有效的提高连续泊位分配问题的执行效率.     

Quay crane and yard truck dual-cycle scheduling with mixed storage strategy

In order to enhance the efficiency of port operations, the scheduling problem of the quay cranes and yard trucks is crucial. Conventional port operation mode lacks optimization research on efficiency of port handling operation, yard truck scheduling, and container storage location. To make quay crane operations and horizontal transportation more efficient, this study uses a dual-cycle strategy to focus on a quay crane and yard truck scheduling problem in conjunction with a mixed storage strategy. A dispatching plan for yard trucks is considered, as well as the storage location of inbound containers. Based on the above factors, a mixed-integer programming model is formulated to minimize vessels’ berth time for completing all tasks. The proposed model is solved using a particle swarm optimization-based algorithm. Validation of the proposed model and algorithm is conducted through numerical experiments. Additionally, some managerial implications which may be potentially useful for port operators are obtained.     

基于动态平衡策划下的集装箱堆场箱位分配方案研究

针对集装箱在码头堆存时存在的箱位分配问题,在研究原有多场桥同时作业方案的基础上,提出了多场桥分区域动态平衡策划方案,弥补了原方案中因保证场桥间的安全距离而带来的缺陷。以合理利用堆存空间,提高场桥作业效率为目标,建立数学模型,结合遗传算法对所提方案进行验证。结果表明,分区域动态平衡策划方案能有效减少场桥的无效作业时间,提高场桥的工作效率,并能充分地利用堆场贝位,更好地利用堆场空间。     

Design of digital twin applications in automated storage yard scheduling

A digital twin-enabled automated storage yard scheduling framework for uncertain port dispatching is proposed in this paper. Digital twin technology is employed to establish the virtual yet realistic storage yard and the connection between them. In the proposed framework, disturbed scenarios during practical operation are monitored, and real-time data is visualized in the virtual space to adapt to the time-varying environment. The proposed framework focuses on the optimization of three main resources, viz. storage area, automated stacking cranes (ASCs), and automated guided vehicles (AGVs). In addition, three key technologies, the Internet of Things (IoT), virtual reality, and digital thread, are adopted to develop the proposed scheduling system. A case study of ASC rescheduling due to dynamic arrival is used to demonstrate the effectiveness of the proposed framework and the significance of obtaining uncertainties in port optimization. Sensitivity analysis is conducted to define the appropriate configuration required to handle all tasks. The results show that digital twin applications in automated storage yard scheduling help operators make optimization decisions.     

Hybrid rolling-horizon optimization for berth allocation and quay crane assignment with unscheduled vessels

Port operations usually suffer from uncertainties, such as vessels’ arrival time and handling time and unscheduled vessels. To address this, this study presents a dynamic berth allocation and crane assignment specific problem (BACASP) when unscheduled vessels arrive at the port, which is branded the berth allocation and quay crane assignment specific problem with unscheduled vessels (UBACASP). A rolling-horizon based method is proposed to decompose the UBACASP into a multi-stage static decision BACASP, wherein a rescheduling margin-based hybrid rolling-horizon optimization method is developed by incorporating the event-driven and periodical rolling-horizon strategies as the urgency of dynamic events is evaluated. In each rolling horizon, a mixed integer linear programming model (MILP) is presented for the BACASP to minimize the total port stay time of vessels and the penalties of delays associated with the spatial and temporal constraints, such as the length of continuous berth, number of quay cranes (QCs) and non-crossing of QCs. A discretization strategy is designed to divide the continuous berth into discrete segments, and convert the BACASP to a discrete combinatorial optimization problem, which is efficiently solved by the proposed adaptive large neighborhood search algorithm (ALNS). Case studies with different problem characteristics are conducted to prove the effectiveness of the solution methods proposed in this study. Moreover, the performances of the ALNS and the existing methods for solving the BACASP are compared, and the advantages and disadvantages of different rolling strategies under different degrees of uncertainties are deeply analyzed.     

Simulation-based investment planning for Humen Port

This paper addresses an investment planning problem for a container terminal in Humen Port using simulation with Arena software. We propose a simulation model considering various types of container ships and cranes, flexible berth allocation and dynamic crane scheduling. We carry out simulation experiments in order to identify a parameter setting that can minimize the total investment cost while maintaining a required service level. The experiment results show that the proposed economic investment plan can reduce the cost compared with the current investment plan.     

基于知识的集装箱堆场箱位分配计划研究

针对集装箱堆场箱位分配问题中规则因素较强的特点,建立基于知识的箱位分配计划方法.首先描述了该问题中知识构成和表示方法;并提出了基于知识的箱位分配模型,包括分配区域划分、作业模式及规则匹配、最优箱位选择三个部分.实例分析表明本方法可取得良好的箱位分配效果.     

Multi-objective genetic algorithm for berth allocation problem considering daytime preference

Maximization of operational efficiency and minimization of cost are pursued by terminal operators, whereas daytime preference is increasingly emphasized by governments, terminal operators and workers. Daytime preference in berth allocation schedule refers to schedule the workloads in nights as fewer as possible, which improves working comfort, safety, and green and energy-savings degrees, but may decrease the throughput and total operational efficiency. By extending existing dynamic discrete berth allocation model, a bi-objective model considering daytime preference is established to minimize the delayed workloads and the workloads in nights. Based on the well known NSGA-II algorithm, a multi-objective genetic algorithm (moGA) is developed for solving the bi-objective model by using a two-part representation scheme. The sensitivities of the algorithmic parameters and tradeoffs between daytime preference and delayed workloads are analyzed by numerical experiments. The algorithmic aspects of the proposed approach and the effects of daytime preference on solutions are all examined. Finally, the managerial implications are discussed.     

分布式实时系统中的预测调度算法

对于分布式实时系统中的周期性任务,人们提出了一系列静态分配调度算法,有效地解决了各种特定条件下的任务分配和调度问题.这些算法的主要特点是,它们均要求被调度任务的特征参数为已知条件.然而在很多实时系统中,周期性任务的运行时间或任务数量常常是一些具有一定规律的随机过程,因而上述静态算法的效能将受到限制.在分析了特定应用背景中的处理流程之后,抽象得到两类随机任务模型,针对这两类模型介绍了在分布式实时系统中已经得到应用的静态分配调度算法SAA(static allocation algorithms),进而提出了多任务分配调度的预测算法PAA(predicting allocation algorithm).它根据周期性任务执行时间或子任务数量的统计特性,实现任务参量的合理预测和多任务的动态调度,以提高系统的实时性能.仿真结果表明,对于两类任务模型,PAA算法与SAA算法相比,在任务完成时间、负载均衡度、系统响应时间及任务夭折率等多方面均有显著改善.     

Resource Allocation in the Grid with Learning Agents

One of the main challenges in Grid computing is efficient allocation of resources (CPU – hours, network bandwidth, etc.) to the tasks submitted by users. Due to the lack of centralized control and the dynamic/stochastic nature of resource availability, any successful allocation mechanism should be highly distributed and robust to the changes in the Grid environment. Moreover, it is desirable to have an allocation mechanism that does not rely on the availability of coherent global information. In this paper we examine a simple algorithm for distributed resource allocation in a simplified Grid-like environment that meets the above requirements. Our system consists of a large number of heterogenous reinforcement learning agents that share common resources for their computational needs. There is no explicit communication or interaction between the agents: the only information that agents receive is the expected response time of a job it submitted to a particular resource, which serves as a reinforcement signal for the agent. The results of our experiments suggest that even simple reinforcement learning can indeed be used to achieve load balanced resource allocation in large scale heterogenous system.     

单向航道下连续泊位分配与船舶调度集成优化

为改善单向航道连续泊位港口的运营效率,研究泊位分配与船舶进出港调度集成优化.考虑潮汐、进出港时段交替与偏好泊位的影响,建立0-1整数线性规划模型,以船舶偏离偏好泊位成本和滞期成本为优化目标,确定各艘船舶的靠泊位置与进出港时刻.针对问题情境和其特有的约束条件,将原数学模型通过Dantzig-Wolfe分解方法分成主问题模...     

多目标约束处理方法求解泊位岸桥联合分配问题

为了制定合理高效的泊位岸桥联合分配方案,加快船舶周转,本文针对船舶动态到港的连续泊位建立了以船舶总在港时间最短为目标的泊位岸桥联合分配混合整数非线性模型.通过多目标约束处理策略将复杂约束的违反程度转化为另一个目标,从而将原单目标优化模型转化为双目标优化模型,并用基于快速非支配排序的多目标遗传算法(NSGA-II)对其进行求解.同时,针对问题特点,分别设计了基于调整、惩罚函数、可行解优先和综合约束处理策略的单目标遗传算法对原模型进行求解.通过多组不同规模的标准算例对本文的方法进行测试,验证了基于多目标约束处理策略的方法求解效果相较于单目标约束处理策略的方法更加高效和稳定.     

动态环境下集装箱码头堆场出口箱箱位分配建模与算法研究

箱位分配是集装箱码头运作优化管理的关键问题.针对出口箱交箱时间的动态不确定性,提出两级调度策略,将出口箱位分配问题分解为贝位分配和贝内具体箱位分配,分别建立规划模型优化龙门吊大车行使距离和翻箱量,并针对两级调度策略特点分别设计开发基于禁忌搜索的求解算法.模拟实验表明,所提出的方法能够适应动态条件变化,改善调度效果,并在合理时间内获得满意解.