Model and algorithms for multi-period sea cargo mix problem

In this paper, we consider the sea cargo mix problem in international ocean container shipping industry. We describe the characteristics of the cargo mix problem for the carrier in a multi-period planning horizon, and formulate it as a multi-dimensional multiple knapsack problem (MDMKP). In particular, the MDMKP is an optimization model that maximizes the total profit generated by all freight bookings accepted in a multi-period planning horizon subject to the limited shipping capacities. We propose two heuristic algorithms that can solve large scale problems with tens of thousands of decision variables in a short time. Finally, numerical experiments on a wide range of randomly generated problem instances are conducted to demonstrate the efficiency of the algorithms.     

时间敏感型货物两阶段集装箱舱位分配问题研究

本文旨在探索如何对时间敏感型货物的集装箱舱位分配和动态定价问题进行研究。考虑到时间敏感型货物对配送时间的要求,本文提出一种新的定价机制,即在该类货物的运费制定时,考虑时间敏感型货物的配送时效及港口拥挤对其存在的影响,建立运价和配送时间之间的关系。另外,以船舶公司总运费收益最大化为目标,构建两阶段随机整数规划模型,运用机会约束规划方法对模型进行求解。最后,通过算例研究,验证了模型及算法的有效性。结果表明,本文针对时间敏感型货物所提出的定价机制能够显著提高船公司收益。     

Modelling of containerized air cargo forwarding problems under uncertainty

This paper examines air container renting and cargo loading problems experienced by freight forwarding companies. Containers have to be booked in advance, in order to obtain discounted rental rates from airlines; renting or returning containers on the day of shipping will incur a heavy penalty. We first propose a mixed-integer model for the certain problem, in which shipment information is known with certainty, when booking. We then present a two-stage recourse model to handle the uncertainty problem, in which accurate shipment information cannot be obtained when booking, and all cargoes have to be shipped without delay. The first-stage decision is made at the booking stage, to book specific numbers of different types of containers. The second-stage decision is made on the day of shipping, depending on the extent to which the uncertainty has been realized. The decisions include number of additional containers of different types that are required to be rented, or the number of containers to be returned, under the scenario that might occur on the day of shipping. We then extend the recourse model into a robust model for dealing with the situation in which cargoes are allowed to be shipped later. The robust model provides a quantitative method to measure the trade-off between risk and cost. A series of experiments demonstrate the effectiveness of the robust model in dealing with risk and uncertainty.     

Multilevel,threshold-based policies for cargo container security screening systems

To mitigate the threat of nuclear terrorism within the US using nuclear material that has been smuggled into the country, the US Bureau of Customs and Border Protection has expanded its cargo container detection capabilities at ports of entry into the US This paper formulates a risk-based screening framework for determining how to define a primary screening alarm for screening cargo containers given a set of dependent primary screening devices. To do so, this paper proposes two linear programming models for screening cargo containers for nuclear material at port security stations using knapsack problem models. All cargo containers undergo primary screening, where they are screened by a given number of security devices. The objective is to identifying the primary security outcomes that warrant a system alarm for each container risk group such that the system detection probability is maximized, subject to a screening budget. The base model is compared to a second model that explicitly requires a threshold-based policy. The structural properties of the two models are compared, which indicates that all risk groups except at most one have deterministic screening policies. A computational example suggests that the detection probability is not significantly altered by enforcing a threshold policy.     

A tabu search heuristic for ship routing and scheduling with flexible cargo quantities

This paper presents a planning problem faced by many shipping companies dealing with the transport of bulk products. These shipping companies typically have a certain amount of contract cargoes that they are committed to carry, while trying to maximize their profit from optional spot cargoes. The cargo quantities are often flexible within an interval. Therefore, interwoven with the routing and scheduling decisions, the planner also has to decide the optimal cargo quantities. A tabu search algorithm embedding a specialized heuristic for deciding the optimal cargo quantities in each route is proposed to solve the problem. Computational results show that the heuristic gives optimal or near-optimal solutions to real-life cases of the problem within reasonable time. It is also shown that utilizing the flexibility in cargo quantities gives significantly improved solutions.     

Ship routing and scheduling with flexible cargo sizes

Here, we describe a real planning problem in the tramp shipping industry. A tramp shipping company may have a certain amount of contract cargoes that it is committed to carry, and tries to maximize the profit from optional cargoes. For real long-term contracts, the sizes of the cargoes are flexible. However, in previous research within tramp ship routing, the cargo quantities are regarded as fixed. We present an MP-model of the problem and a set partitioning approach to solve the multi-ship pickup and delivery problem with time windows and flexible cargo sizes. The columns are generated a priori and the most profitable ship schedule for each cargo set–ship combination is included in the set partitioning problem. We have tested the method on several real-life cases, and the results show the potential economical effects for the tramp shipping companies by utilizing flexible cargo sizes when generating the schedules.     

Routing,ship size,and sailing frequency decision-making for a maritime hub-and-spoke container network

This study formulates a two-objective model to determine the optimal liner routing, ship size, and sailing frequency for container carriers by minimizing shipping costs and inventory costs. First, shipping and inventory cost functions are formulated using an analytical method. Then, based on a trade-off between shipping costs and inventory costs, Pareto optimal solutions of the two-objective model are determined. Not only can the optimal ship size and sailing frequency be determined for any route, but also the routing decision on whether to route containers through a hub or directly to their destination can be made in objective value space. Finally, the theoretical findings are applied to a case study, with highly reasonable results. The results show that the optimal routing, ship size, and sailing frequency with respect to each level of inventory costs and shipping costs can be determined using the proposed model. The optimal routing decision tends to be shipping the cargo through a hub as the hub charge is decreased or its efficiency improved. In addition, the proposed model not only provides a tool to analyze the trade-off between shipping costs and inventory costs, but it also provides flexibility on the decision-making for container carriers.     

An integrated model for screening cargo containers

This paper focuses on detecting nuclear weapons on cargo containers using port security screening methods, where the nuclear weapons would presumably be used to attack a target within the United States. This paper provides a linear programming model that simultaneously identifies optimal primary and secondary screening policies in a prescreening-based paradigm, where incoming cargo containers are classified according to their perceived risk. The proposed linear programming model determines how to utilize primary and secondary screening resources in a cargo container screening system given a screening budget, prescreening classifications, and different device costs. Structural properties of the model are examined to shed light on the optimal screening policies. The model is illustrated with a computational example. Sensitivity analysis is performed on the ability of the prescreening in correctly identifying prescreening classifications and secondary screening costs. Results reveal that there are fewer practical differences between the screening policies of the prescreening groups when prescreening is inaccurate. Moreover, devices that can better detect shielded nuclear material have the potential to substantially improve the system’s detection capabilities.     

Optimising cargo loading and ship scheduling in tidal areas

This paper describes a framework that combines decision theory and stochastic optimisation techniques to address tide routing (i.e. optimisation of cargo loading and ship scheduling decisions in tidal ports and shallow seas). Unlike weather routing, tidal routing has been little investigated so far, especially from the perspective of risk analysis. Considering the journey of a bulk carrier between N ports, a shipping decision model is designed to compute cargo loading and scheduling decisions, given the time series of the sea level point forecasts in these ports. Two procedures based on particle swarm optimisation and Monte Carlo simulations are used to solve the shipping net benefit constrained optimisation problem. The outputs of probabilistic risk minimisation are compared with those of net benefit maximisation, the latter including the possibility of a ‘rule-of-the-thumb’ safety margin. Distributional robustness is discussed as well, with respect to the modelling of sea level residuals. Our technique is assessed on two realistic case studies in British ports. Results show that the decision taking into account the stochastic dimension of sea levels is not only robust in real port and weather conditions, but also closer to optimality than standard practices using a fixed safety margin. Furthermore, it is shown that the proposed technique remains more interesting when sea level variations are artificially increased beyond the extremes of the current residual models.     

不确定箱量下内河集装箱班轮航线动态配载决策

内河集装箱班轮运输中海关抽检可导致外贸箱箱量不断发生变化,班轮航线配载需要动态决策。基于滚动调度策略,将当前港口的配载决策按随机事件划分为多个阶段,以最小化班轮堆栈占用数量和相邻阶段间配载计划偏差为目标,构建单港口单阶段的配载决策模型,进而滚动实现班轮航线动态配载决策。基于大邻域搜索思想设计一种包含整数规划、破坏器与修复器的精确启发式算法,实现港口多阶段滚动配载。基于真实场景的算例研究表明,在优化堆栈占用数量方面,模型与算法之间差异不大,但在考虑相邻阶段间配载计划偏差时,算法的求解结果要优于模型。因此,模型与算法可用来辅助实现不确定箱量下内河集装箱班轮航线动态配载决策,且算法表现更优,可实现配载计划对不确定箱量的鲁棒吸收。     

Liner ship fleet deployment with week-dependent container shipment demand

This paper addresses a practical liner ship fleet deployment problem with week-dependent container shipment demand and transit time constraint, namely, maximum allowable transit time in container routing between a pair of ports. It first uses the space–time network approach to generate practical container routes subject to the transit time constraints. This paper proceeds to formulate the fleet deployment problem based on the practical container routes generated. In view of the intractability of the formulation, two relaxation models providing lower bounds are built: one requires known container shipment demand at the fleet deployment stage, and the other assumes constant container shipment demand over the planning horizon. An efficient global optimization algorithm is subsequently proposed. Extensive numerical experiments on the shipping data of a global liner shipping company demonstrate the applicability of the proposed model and algorithm.     

Short-term liner ship fleet planning with container transshipment and uncertain container shipment demand

This paper proposes a short-term liner ship fleet planning problem by taking into account container transshipment and uncertain container shipment demand. Given a liner shipping service network comprising a number of ship routes, the problem is to determine the numbers and types of ships required in the fleet and assign each of these ships to a particular ship route to maximize the expected value of the total profit over a short-term planning horizon. These decisions have to be made prior to knowing the exact container shipment demand, which is affected by some unpredictable and uncontrollable factors. This paper thus formulates this realistic short-term planning problem as a two-stage stochastic integer programming model. A solution algorithm, integrating the sample average approximation with a dual decomposition and Lagrangian relaxation approach, is then proposed. Finally, a numerical example is used to evaluate the performance of the proposed model and solution algorithm.     

Automating the planning of container loading for Atlas Copco: Coping with real-life stacking and stability constraints

The Atlas Copco^☆ distribution center in Allen, TX, supplies spare parts and consumables to mining and construction companies across the world. For some customers, packages are shipped in sea containers. Planning how to load the containers is difficult due to several factors: heterogeneity of the packages with respect to size, weight, stackability, positioning and orientation; the set of packages differs vastly between shipments; it is crucial to avoid cargo damage. Load plan quality is ultimately judged by shipping operators.This container loading problem is thus rich with respect to practical considerations. These are posed by the operators and include cargo and container stability as well as stacking and positioning constraints. To avoid cargo damage, the stacking restrictions are modeled in detail. For solving the problem, we developed a two-level metaheuristic approach and implemented it in a decision support system. The upper level is a genetic algorithm which tunes the objective function for a lower level greedy-type constructive placement heuristic, to optimize the quality of the load plan obtained.The decision support system shows load plans on the forklift laptops and has been used for over two years. Management has recognized benefits including reduction of labour usage, lead time, and cargo damage risk.     

Methods for strategic liner shipping network design

In this paper the combined fleet-design, ship-scheduling and cargo-routing problem with limited availability of ships in liner shipping is considered. A composite solution approach is proposed in which the ports are first aggregated into port clusters to reduce the problem size. When the cargo flows are disaggregated, a feeder service network is introduced to ship the cargo within a port cluster. The solution method is tested on a problem instance containing 58 ports on the Asia–Europe trade lane of Maersk. The best obtained profit gives an improvement of more than 10% compared to the reference network based on the Maersk network.     

Weight distribution considerations in container loading

A major drawback of the current literature on container loading is the lack of consideration of many practical issues. The weight distribution of the cargo is one such aspect which has been largely ignored. The paper considers post-processing approaches to tackle this problem. A new container loading heuristic is put forward in this context and is evaluated against several existing approaches. It is demonstrated that the procedure proposed is capable of producing loading arrangements which combine high space utilisation with an even weight distribution of the cargo.     

A service flow model for the liner shipping network design problem

Global liner shipping is a competitive industry, requiring liner carriers to carefully deploy their vessels efficiently to construct a cost competitive network. This paper presents a novel compact formulation of the liner shipping network design problem (LSNDP) based on service flows. The formulation alleviates issues faced by arc flow formulations with regards to handling multiple calls to the same port. A problem which has not been fully dealt with earlier by LSNDP formulations. Multiple calls are handled by introducing service nodes, together with port nodes in a graph representation of the problem, and by introducing numbered arcs between a port and a novel service node. An arc from a port node to a service node indicate whether a service is calling the port or not. This representation allows recurrent calls of a service to a port, which previously could not be handled by LSNDP models. The model ensures strictly weekly frequencies of services, ensures that port-vessel draft capabilities are not violated, respects vessel capacities and the number of vessels available. The profit of the generated network is maximized, i.e. the revenue of flowed cargo subtracted operational costs of the network and a penalty for not flowed cargo. The model can be used to design liner shipping networks to utilize a container carrier’s assets efficiently and to investigate possible scenarios of changed market conditions. The model is solved as a Mixed Integer Program. Results are presented for the two smallest instances of the benchmark suite LINER-LIB-2012 presented in Brouer, Alvarez, Plum, Pisinger, and Sigurd (2013).     

Impact analysis of maritime cabotage legislations on liner hub-and-spoke shipping network design

Maritime cabotage is a legislation published by a particular coastal country, which is used to conduct the cargo transportation between its two domestic ports. This paper proposes a two-phase mathematical programming model to formulate the liner hub-and-spoke shipping network design problem subject to the maritime cabotage legislations, i.e., the hub location and feeder allocation problem for phase I and the ship route design with ship fleet deployment problem for phase II. The problem in phase I is formulated as a mixed-integer linear programming model. By developing a hub port expanding technique, the problem in phase II is formulated as a vehicle routing problem with pickup and delivery. A Lagrangian relaxation based solution method is proposed to solve it. Numerical implementations based on the Asia–Europe–Oceania shipping services are carried out to account for the impact analysis of the maritime cabotage legislations on liner hub-and-spoke shipping network design problem.     

MIP-based approaches for the container loading problem with multi-drop constraints

In this paper, we present approaches based on a mixed integer linear programming model (MIP) for the problem of packing rectangular boxes into a container or truck, considering multi-drop constraints. We assume that the delivery route of the container is already known in advance and that the volume of the cargo is less than or equal to the container volume. Considering the sequence that the boxes should be unloaded, the aim is to avoid additional handling when each drop-off point of the route is reached, as well as ensuring that the boxes do not overlap each other and the cargo loading is stable. Computational tests with the proposed model and the approaches were performed with randomly generated instances and instances from the literature using an optimization solver embedded into a modeling language. The results validate the model and the approaches, but indicate that they are able to handle only problems of a moderate size. However, the model and the approaches can be useful to motivate future research to solve larger problems, as well as to solve more general problems considering integrated vehicle routing and container loading problems.     

A global optimization approach for solving three-dimensional open dimension rectangular packing problems

The three-dimensional open dimension rectangular packing problem (3D-ODRPP) aims to pack a set of given rectangular boxes into a large rectangular container of minimal volume. This problem is an important issue in the shipping and moving industries. All the boxes can be any rectangular stackable objects with different sizes and may be freely rotated. The 3D-ODRPP is usually formulated as a mixed-integer non-linear programming problem. Most existing packing optimization methods cannot guarantee to find a globally optimal solution or are computationally inefficient. Therefore, this paper proposes an efficient global optimization method that transforms a 3D-ODRPP as a mixed-integer linear program using fewer extra 0–1 variables and constraints compared to existing deterministic approaches. The reformulated model can be solved to obtain a global optimum. Experimental results demonstrate the computational efficiency of the proposed approach in globally solving 3D-ODRPPs drawn from the literature and the practical applications.