共查询到20条相似文献,搜索用时 31 毫秒
1.
在集装箱出口箱区堆场的实际作业中,常将待提箱提前翻倒至一空闲箱区,使其装船前以船舶配载图的倒序堆垛,以提高装船效率。为提高初始出口箱区的预翻作业效率,针对该箱区的多场桥调度优化问题进行研究。以实施预翻作业的某一出口箱区为研究对象,在船舶配载图已知的前提下,考虑作业场桥间保持安全距离且不可跨越的条件,兼顾满足经验翻箱规则等现实约束,侧重作业过程中实时翻箱,构建了以场桥作业总行走时间最小为优化目标的线性规划模型,并设计了分支定价算法。在算例实验中,通过与非实时预翻箱方案、FCFS方案以及下界进行对比,验证了模型及算法的有效性,可为集装箱码头出口箱堆场的场桥调度提供参考。 相似文献
2.
This paper addresses the joint quay crane and truck scheduling problem at a container terminal, considering the coordination of the two types of equipment to reduce their idle time between performing two successive tasks. For the unidirectional flow problem with only inbound containers, in which trucks go back to quayside without carrying outbound containers, a mixed-integer linear programming model is formulated to minimize the makespan. Several valid inequalities and a property of the optimal solutions for the problem are derived, and two lower bounds are obtained. An improved Particle Swarm Optimization (PSO) algorithm is then developed to solve this problem, in which a new velocity updating strategy is incorporated to improve the solution quality. For small sized problems, we have compared the solutions of the proposed PSO with the optimal solutions obtained by solving the model using the CPLEX software. The solutions of the proposed PSO for large sized problems are compared to the two lower bounds because CPLEX could not solve the problem optimally in reasonable time. For the more general situation considering both inbound and outbound containers, trucks may go back to quayside with outbound containers. The model is extended to handle this problem with bidirectional flow. Experiment shows that the improved PSO proposed in this paper is efficient to solve the joint quay crane and truck scheduling problem. 相似文献
3.
The container was introduced as a universal carrier for various goods in the 1960s and soon became a standard worldwide transportation.
The competitiveness of a container seaport is marked by different success factors, particularly the time in port for ships.
Operational problems of container terminals is divided into several problems, such as assignment of vessels, loading/unloading
and storage of the containers, quay cranes scheduling cite, planning yard cranes cite and assignment of storage containers
cite. In this work, the study will focus on piloting yard trucks. Two different types of vehicles can be used, namely automated
guided vehicles (AGVs) and lifting vehicles (LVs). An AGV receives a container from a quay crane and transports containers
over fixed path. LVs are capable of lifting a container from the ground by itself. The model that we consider is formulated
as a mixed integer programming problem, and the difficulty arises when the number of binary variables increases. There are
a lot of algorithms designed for mixed integer programming problem such as Branch and Bound method, cutting plane algorithm,
. . . By using an exact penalty technique we treat this problem as a DC program in the context of continuous optimization.
Further, we combine the DCA with the classical Branch and Bound method for finding global solutions. 相似文献
4.
Amir Hossein Gharehgozli Yugang Yu René de Koster Jan Tijmen Udding 《European Journal of Operational Research》2014
This paper studies an operational problem arising at a container terminal, consisting of scheduling a yard crane to carry out a set of container storage and retrieval requests in a single container block. The objective is to minimize the total travel time of the crane to carry out all requests. The block has multiple input and output (I/O) points located at both the seaside and the landside. The crane must move retrieval containers from the block to the I/O points, and must move storage containers from the I/O points to the block. The problem is modeled as a continuous time integer programming model and the complexity is proven. We use intrinsic properties of the problem to propose a two-phase solution method to optimally solve the problem. In the first phase, we develop a merging algorithm which tries to patch subtours of an optimal solution of an assignment problem relaxation of the problem and obtain a complete crane tour without adding extra travel time to the optimal objective value of the relaxed problem. The algorithm requires common I/O points to patch subtours. This is efficient and often results in obtaining an optimal solution of the problem. If an optimal solution has not been obtained, the solution of the first phase is embedded in the second phase where a branch-and-bound algorithm is used to find an optimal solution. The numerical results show that the proposed method can quickly obtain an optimal solution of the problem. Compared to the random and Nearest Neighbor heuristics, the total travel time is on average reduced by more than 30% and 14%, respectively. We also validate the solution method at a terminal. 相似文献
5.
为降低送箱集卡到场的不确定性对出口箱堆存和装船效率的影响,以最小化堆场进出场作业系统总作业时间为上层模型的目标,以最小化同一批入场出口箱的堆存时间下层模型的目标,构建了双层混合整数规划模型为进出场的出口箱分配箱位并优化场桥调度。设计改进的遗传模拟退火算法求解上层模型可得出口箱箱位分配方案,求解下层模型可得预翻箱和场桥调度方案,通过不断平衡上下层最优解使堆场堆存和装船作业效率最优。通过数值实验验证了算法和调度策略有效性,研究结果可丰富集装箱码头运营系统优化理论,为提高出口箱堆场作业效率提供决策参考。 相似文献
6.
7.
《European Journal of Operational Research》2005,164(1):64-78
This paper examines the problem of scheduling multiple yard cranes to perform a given set of jobs with different ready times in a yard zone with only one bi-directional travelling lane. Due to sharing of the travelling lane among two or more yard cranes, inter-crane interference, a planned move of a yard crane blocked by the other yard cranes, may happen. The scheduling problem is formulated as an integer program. It is noted that the scheduling problem is NP-complete. This research develops a dynamic programming-based heuristic to solve the scheduling problem and an algorithm to find lower bounds for benchmarking the schedules found by the heuristic. Computational experiments are carried out to evaluate the performance of the heuristic and the results show that the heuristic can indeed find effective solutions for the scheduling problem, with the heuristic solutions on average 7.3% above their lower bounds. 相似文献
8.
基于垂岸式自动化集装箱码头不同装船周期出口集装箱堆场多贝位混合堆存、场桥大车在贝位间频繁移动取箱装船特点,考虑装船发箱时场桥移动等操作时间及翻箱取箱次数对出口箱装船效率和连续性影响,建立多贝位出口箱装船堆场翻箱模型,提出两阶段贪婪禁忌搜索算法,将翻箱规则嵌入算法中,有效限制算法时间和解空间增长速度。通过算例,将提出的翻箱规则与现有常见翻箱规则进行对比,验证模型及算法的有效性与实用性。结果表明,提出的模型和算法可以在合理的求解时间内输出较优的翻箱方案,减少装船时场桥发箱作业时间,提高装船作业效率。 相似文献
9.
10.
B. Cao 《Mathematical Methods of Operations Research》1992,36(2):185-197
In a container terminal management, we are often confronted with the following problem: how to assign a reasonable depositing position for an arriving container, so that the efficiency of searching for and loading of a container later can be increased. In this paper, the problem is modeled as a transportation problem with nonlinear side constraints (TPNSC). The reason of nonlinear side constraints arising is that some kinds of containers cannot be stacked in the same row (the space of storage yard is properly divided into several rows). A branch and bound algorithm is designed to solve this problem. The algorithm is based on the idea of using disjunctive arcs (branches) for resolving conflicts that are created whenever some conflicting kinds of containers are deposited in the same row. During the branch and bound, the candidate problems are transformed into classical transportation problems, so that the efficient transportation algorithm can be applied, at the same time the reoptimization technique is employed during the branch and bound. Further, we design a heuristic to obtain a feasible initial solution for TPNSC in order to prune some candidates as early and/or as much as possible. We report computational results on randomly generated problems. 相似文献
11.
The quay crane scheduling problem (QCSP) is at the basis of a major logistic process in maritime container terminals: the process of discharging/loading containers from/on berthed vessels. Several groups of containers, laying in one or more stowage portions of a containership, have to be assigned to multiple cranes and discharge/loading operations have to be optimally sequenced, under some complicating constraints imposed by the practical working rules of quay cranes. The QCSP has been the object of a great deal of research work since the last decade and it is focused in this paper, with the aim of consolidating a promising solution approach based upon the combination of specialized branch & bound (B&B) and heuristic algorithms. A cost-effective solution technique that incorporates the local branching method within a refined B&B algorithm is proposed and its effectiveness is assessed by numerical comparisons against the latest algorithm available in literature. 相似文献
12.
13.
Xinjia Jiang Loo Hay Lee Ek Peng Chew Yongbin Han Kok Choon Tan 《European Journal of Operational Research》2012
This paper studies the storage yard management problem in a busy transshipment hub, where intense loading and unloading activities have to be considered at the same time. The need to handle huge volumes of container traffic and the scarcity of land in the container port area pose serious challenges for the port operator to provide efficient services. A consignment strategy with a static yard template has been used to reduce the level of reshuffles in the yard, but it sacrifices on land utilization because of exclusive storage space reservation. Two space-sharing approaches are proposed to improve on the land utilization through dynamic reservation of storage space for different vessels during different shifts. Meanwhile, workload assignment among reserved spaces will also satisfy the high-low workload balancing protocol to reduce traffic congestion in the yard. A framework which integrates space reservation and workload assignment is proposed. Experimental results show that the framework is able to provide solutions for containers handling within much less storage space, while guarantee the least yard crane deployment. 相似文献
14.
关注单船桥机调度问题,指出了单船桥机的闲置会影响码头整体的运作效率。以单个集装箱为任务单位,考虑桥机移动时间、安全距离等约束,建立了最小化桥机完工时间和闲置时间的多目标规划模型。基于完工时间下界的两种不同情况:以重点贝位工作量确定和以平均工作量确定,分别设计了基于邻域搜索的启发式算法和基于贪心策略的“分割贝位”算法,并且证明了在以平均工作量确定下界的情况中该算法不会导致桥机闲置。不同规模、不同下界类型的算例表明:提出的模型与算法得到的桥机调度计划更适合实际生产作业,能够有效地逼近完工时间下界,算法运行速度较现有的研究有显著的提高。 相似文献
15.
针对集装箱码头提箱作业过程中,由于外集卡的提箱顺序与目标箱在堆场的堆存位置不匹配导致大量翻箱这一难题,以码头的作业成本和外集卡的延误成本之和最小为目标,建立堆场翻箱与外集卡提箱顺序同步优化模型,优化外集卡的提箱顺序、龙门吊的任务分配以及翻箱方案。设计基于动态规划的启发式算法求解模型,并利用算例对模型与算法的有效性进行了验证。结果表明:与目前码头普遍采用的提箱方式相比,通过调整外集卡提箱顺序并同时优化翻箱方案以及龙门吊的任务分配可以降低堆场翻箱率,减少龙门吊的移动成本,从而节省提箱作业的总成本。 相似文献
16.
We consider a stowage-planning problem of arranging containers on a container ship in the maritime transportation system. Since containers are accessible only from the top of the stack, temporary unloading and reloading of containers, called shifting, is unavoidable if a container required to be unloaded at the current port is stacked under containers to be unloaded at later ports on the route of the ship. The objective of the stowage planning problem is to minimize the time required for shifting and crane movements on a tour of a container ship while maintaining the stability of the ship. For the problem, we develop a heuristic solution method in which the problem is divided into two subproblems, one for assigning container groups into the holds and one for determining a loading pattern of containers assigned to each hold. The former subproblem is solved by a greedy heuristic based on the transportation simplex method, while the latter is solved by a tree search method. These two subproblems are solved iteratively using information obtained from solutions of each other. To see the performance of the suggested algorithm, computational tests are performed on problem instances generated based on information obtained from an ocean container liner. Results show that the suggested algorithm works better than existing algorithms. 相似文献
17.
《European Journal of Operational Research》2001,132(3):643-665
We consider two problems of m-machine flow shop scheduling in this paper: one, with the objective of minimizing the variance of completion times of jobs, and the other with the objective of minimizing the sum of squares of deviations of job completion times from a common due date. Lower bounds on the sum of squares of deviations of job completion times from the mean completion time of jobs for a given partial sequence are first presented. Using these lower bounds, a branch and bound algorithm based on breadth-first search procedure for scheduling n jobs on m-machines with the objective of minimizing completion time variance (CTV) is developed to obtain the best permutation sequence. We also present two lower bounds and thereafter, a branch and bound algorithm with the objective of minimizing the sum of squares of deviations of job completion times from a given common due date (called the MSD problem). The computational experience with the working of the two proposed branch and bound algorithms is also reported. Two heuristics, one for each of the two problems, are developed. The computational experience on the evaluation of the heuristics is discussed. 相似文献
18.
Angelo Alessandri Simona Sacone Silvia Siri 《Journal of Mathematical Modelling and Algorithms》2007,6(1):109-133
The main objective of this paper consists in modelling, optimizing, and controlling container transfer operations inside intermodal
terminals. More specifically, maritime container terminals are here considered, involving three kinds of transportation modes,
i.e., maritime, rail, and road transport. Generally speaking, an intermodal port terminal can be seen as a system of container
flows with two interfaces, towards the hinterland and towards the sea, respectively. Moreover, inside a terminal, unloading
operations of inbound containers, container storage, and loading operations of outbound containers are carried out. A simple
model for maritime container terminals is proposed in this paper. In the model, a system of queues represents the standing
of containers and their movements inside the terminal. The dynamic evolutions of these queues are described by discrete-time
equations, where the state variables represent the queue lengths and the control variables take into account the utilization
of terminal resources such as load/unload handling rates. On the basis of the proposed model, an optimization problem is defined
that consists in minimizing the transfer delays of containers in the terminal. The problem is stated as an optimal control
problem whose solution is sought by adopting a receding-horizon strategy.
相似文献
19.
This paper considers a scheduling problem with two identical parallel machines. One has unlimited capacity; the other can only run for a fixed time. A given set of jobs must be scheduled on the two machines with the goal of minimizing the sum of their completion times. The paper proposes an optimal branch and bound algorithm which employs three powerful elements, including an algorithm for computing the upper bound, a lower bound algorithm, and a fathoming condition. The branch and bound algorithm was tested on problems of various sizes and parameters. The results show that the algorithm is quite efficient to solve all the test problems. In particular, the total computation time for the hardest problem is less than 0.1 second for a set of 100 problem instances. An important finding of the tests is that the upper bound algorithm can actually find optimal solutions to a quite large number of problems. 相似文献
20.
This paper studies the problem of improving the operations efficiency for retrieving inbound containers in a modern automatic container terminal. In the terminal, when an external truck arrives to collect a container stored in a specific container block, it waits at one end of the block where an automatic stack crane will retrieve the container and deliver it to the truck. With the aim of reducing the expected external truck waiting time which is determined by how the containers are stored in a block, we propose two correlated approaches for the operations efficiency improvement, (1) by designing an optimized block space allocation to store the inbound containers after they are discharged from vessels, and (2) by conducting overnight re-marshaling processes to re-organize the block space allocation after some containers are retrieved. For the block space allocation problem, we consider three optimization models under different strategies of storing containers, namely, a non-segregation model, a single-period segregation model, and a multiple-period segregation model. Optimal solution methods are proposed for all three models. For the re-marshaling problem with a given time limit, we find that the problem is NP-hard and develop a heuristic algorithm to solve the problem. We then use simulation to validate our models and solution approaches. Simulation results reveal important managerial insights such as the advantage of the multiple-period segregation over the myopic single-period segregation, the possibility of overflow of the segregation model, and the benefit of re-marshaling. 相似文献