Scheduling of inbound and outbound trucks in cross docking systems with temporary storage

Cross docking is a warehouse management concept in which items delivered to a warehouse by inbound trucks are immediately sorted out, reorganized based on customer demands, routed and loaded into outbound trucks for delivery to customers without the items being actually held in inventory at the warehouse. If any item is held in storage, it is usually for a brief period of time that is generally less than 24 hours. This way, the turnaround times for customer orders, inventory management cost, and warehouse space requirements are reduced. One of the objectives for cross docking systems is how well the trucks can be scheduled at the dock and how the items in inbound trucks can be allocated to the outbound trucks to optimize on some measure of system performance. The objective of this research is to find the best truck docking or scheduling sequence for both inbound and outbound trucks to minimize total operation time when a temporary storage buffer to hold items temporarily is located at the shipping dock. The product assignment to trucks and the docking sequences of the inbound and outbound trucks are all determined simultaneously.     

Yard crane scheduling in port container terminals

Yard cranes are the most popular container handling equipment for loading containers onto or unloading containers from trucks in container yards of land scarce port container terminals. However, such equipment is bulky, and very often generates bottlenecks in the container flow in a terminal because of their slow operations. Hence, it is essential to develop good yard crane work schedules to ensure a high terminal throughput. This paper studies the problem of scheduling a yard crane to perform a given set of loading/unloading jobs with different ready times. The objective is to minimize the sum of job waiting times. A branch and bound algorithm is proposed to solve the scheduling problem optimally. Efficient and effective algorithms are proposed to find lower bounds and upper bounds. The performance of the proposed branch and bound algorithm is evaluated by a set of test problems generated based on real life data. The results show that the algorithm can find the optimal sequence for most problems of realistic sizes.     

Complexity of flow time minimization in a crossdock truck scheduling problem with asymmetric handover relations

We address a novel truck scheduling problem arising in crossdocking logistics, in which inbound trucks carry items (pallets) which must be sorted and loaded onto outbound trucks. We minimize the utilisation of the warehouse by focusing on the synchronisation between the different related trucks. The problem is to assign the trucks to the doors of the warehouse and sequence them, in order to minimize the total time spent in the system by the pallets. We discuss the complexity of the problem, showing that even with a single door the problem is NP-hard in general, and discuss some special cases.     

Storage space allocation models for inbound containers in an automatic container terminal

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.     

考虑泊位疏浚的连续型泊位和动态岸桥联合调度

针对集装箱码头泊位需要定期维护的实际特征,研究了泊位疏浚情况下连续型泊位和动态岸桥联合调度问题。首先,建立了一个以船舶周转时间最小为目标的整数线性规划模型;其次,针对问题特性设计了三种启发式算法。为了分析泊位疏浚对码头工作的影响并验证模型正确性和算法有效性,分别对未考虑泊位疏浚和考虑泊位疏浚两种调度情形,进行了小规模与大规模问题输入的多组测试。三种算法在小规模输入上均取得了相同于CPLEX的精确解,从而验证了算法的有效性;进一步通过对比分析这些算法在大规模输入中的运行结果,验证其有效性能。     

兼顾成本与时间保证率的泊位及岸桥协同调度优化

针对集装箱班轮根据船期表按计划到离港的运行规律以及港口企业追求低运营成本的需求,本文以集装箱班轮按计划离港保证率最大和码头作业成本最低为目标,构建了泊位及岸桥协同调度多目标优化模型;设计了叠加式局部搜索算法,将其嵌入到带精英策略的非支配排序遗传算法中,经过相互交叉反馈运算,得到Pareto非劣解;采用“性价比”的概念和量化方法,选择出对港口和船公司的利益偏向最小的实施方案,解决了在Pareto解集中寻优的问题。最后,以大连港集装箱码头的生产实际为例,验证了上述优化模型及算法的合理性和有效性。     

An effective mathematical formulation for the unidirectional cluster-based quay crane scheduling problem

The quay crane scheduling problem plays an important role in the paradigm of port container terminal management, due to the fact that it closely relates to vessel berthing time. In this paper, we focus on the study of a special strategy for the cluster-based quay crane scheduling problem that forces quay cranes to move unidirectionally during the scheduling. The scheduling problem arising when this strategy is applied is called the unidirectional quay crane scheduling problem in the literature. Different from other researches attempting to construct more sophisticated searching algorithms, in this paper, we seek for a more compact mathematical formulation of the unidirectional cluster-based quay crane scheduling problem that can be easily solved by a standard optimization solver. To assess the performance of the proposed model, commonly accepted benchmark suites are used and the results indicate that the proposed model outperforms the state-of-the-art algorithms designed for the unidirectional cluster-based quay crane scheduling problem.     

DCA for solving the scheduling of lifting vehicle in an automated port container terminal

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.     

MIP approaches for the integrated berth allocation and quay crane assignment and scheduling problem

In this paper we consider an integrated berth allocation and quay crane assignment and scheduling problem motivated by a real case where a heterogeneous set of cranes is considered. A first mathematical model based on the relative position formulation (RPF) for the berth allocation aspects is presented. Then, a new model is introduced to avoid the big-M constraints included in the RPF. This model results from a discretization of the time and space variables. For the new discretized model several enhancements, such as valid inequalities, are introduced. In order to derive good feasible solutions, a rolling horizon heuristic (RHH) is presented. A branch and cut approach that uses the enhanced discretized model and incorporates the upper bounds provided by the RHH solution is proposed. Computational tests are reported to show (i) the quality of the linear relaxation of the enhanced models; (ii) the effectiveness of the exact approach to solve to optimality a set of real instances; and (iii) the scalability of the RHH based on the enhanced mathematical model which is able to provide good feasible solutions for large size instances.     

A truck scheduling problem arising in intermodal container transportation

We address a truck scheduling problem that arises in intermodal container transportation, where containers need to be transported between customers (shippers or receivers) and container terminals (rail or maritime) and vice versa. The transportation requests are handled by a trucking company which operates several depots and a fleet of homogeneous trucks that must be routed and scheduled to minimize the total truck operating time under hard time window constraints imposed by the customers and terminals. Empty containers are considered as transportation resources and are provided by the trucking company for freight transportation. The truck scheduling problem at hand is formulated as Full-Truckload Pickup and Delivery Problem with Time Windows (FTPDPTW) and is solved by a 2-stage heuristic solution approach. This solution method was specially designed for the truck scheduling problem but can be applied to other problems as well. We assess the quality of our solution approach on several computational experiments.