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.     

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.     

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.     

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.     

Stowage planning in maritime container transportation

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.     

A simulation architecture to support intratheater sealift operations

A new architecture for simulating intratheater sealift operations is presented. Intratheater sealift operations refer to new strategies proposed for quickly deploying a military force to a theater of war when major seaports are not available. In this strategy, a self-deployable force is transported to a sea-based intermediate staging base (SISB) by conventional cargo transport ships. The SISB is a world-class seaport generally located within 800 miles of the theater of war. At the SISB, cargo is transferred to a new ship platform called the theater support vessel (TSV). TSVs are to be designed to access very small ports located at or near the theater of war. Simulation provides an efficient and cost-effective method for testing these strategies and for evaluating the required new logistics technologies. Should intratheater sealift operations prove viable, the simulation also provides a means to plan and rehearse an exercise. The new simulation architecture is described and example simulation case studies are conducted to demonstrate the capabilities and potential benefits of the approach.     

A combined ship scheduling and allocation problem

We present a bulk ship scheduling problem that is a combined multi-ship pickup and delivery problem with time windows (m-PDPTW) and multi-allocation problem. In contrast to other ship scheduling problems found in the literature, each ship in the fleet is equipped with a flexible cargo hold that can be partitioned into several smaller holds in a given number of ways. Therefore, multiple products can be carried simultaneously by the same ship. The scheduling of the ships constitutes the m-PDPTW, while the partition of the ships' flexible cargo holds and the allocation of cargoes to the smaller holds make the multi-allocation problem. A set partitioning approach consisting of two phases is proposed for the combined ship scheduling and allocation problem. In the first phase, a number of candidate schedules (including allocation of cargoes to the ships' cargo holds) is generated for each ship. In the second phase, we minimise transportation costs by solving a set partitioning problem where the columns are the candidate schedules generated in phase one. The computational results show that the proposed approach works, and optimal solutions are obtained on several cases of a real ship planning problem.     

基于低碳环保因素的“前港后厂”钢铁产成品运输网络优化

中国大部分钢铁企业深居内陆,出口钢材需远距离运输到港口,再通过海运发往世界各地,故建立港口与钢铁企业的合作关系将尤为重要。与铁路、水路运输相比,公路运输单位换算周转量的碳排放量更高。但中国内陆运输多采用公路运输,这将加剧大气污染。本文提出基于“前港后厂”联运的钢铁产成品运输问题,以加强港口与钢铁企业的合作。为降低运营成本和碳排放量,建立以碳排放成本、运输成本、仓储成本及时间窗惩罚成本最小为目标的钢铁产成品运输网络优化模型;并设计融合和声搜索的环形拓扑结构PSO算法进行求解;最后对仓储成本进行灵敏度分析,以探究其对“前港后厂”模式的影响。结果表明,“前港后厂”模式不仅能有效降低运输网络的总成本和碳排放量,且合理的仓储成本更能加强港口和钢铁企业间的紧密性。     

Column generation approaches to ship scheduling with flexible cargo sizes

We present a Dantzig–Wolfe procedure for the ship scheduling problem with flexible cargo sizes. This problem is similar to the well-known pickup and delivery problem with time windows, but the cargo sizes are defined by intervals instead of by fixed values. The flexible cargo sizes have consequences for the times used in the ports because both the loading and unloading times depend on the cargo sizes. We found it computationally hard to find exact solutions to the subproblems, so our method does not guarantee to find the optimum over all solutions. To be able to say something about how good our solution is, we generate a bound on the difference between the true optimal objective and the objective in our solution. We have compared our method with an a priori column generation approach, and our computational experiments on real world cases show that our Dantzig–Wolfe approach is faster than the a priori generation of columns, and we are able to deal with larger or more loosely constrained instances. By using the techniques introduced in this paper, a more extensive set of real world cases can be solved either to optimality or within a small deviation from optimality.     

主导权异质性视角下的过坝方式货运量分担率研究

翻坝公路与通航建筑物两类过坝方式的主导权,分别由货主和通航管理局所主导。针对货物过坝主导方的异质性,首先建立了各过坝方式的效用函数来分析主导权的转移机制。然后据此结合通航建筑物过坝原则,构建了货运量分担率多目标优化模型。最后以三峡工程为例,探讨了翻坝运输费率和船舶过坝顺序对分担率的影响,进而探讨了缓解大坝通航拥堵的决策机制。结果表明:提高翻坝公路的货运分担,可以有效改善船舶及货物的过坝运输状况;相比翻坝运输费率,降低装卸费率能更有效地提高翻坝公路货运分担水平;船舶过坝存在一个次序区间,使得水运货物经由通航建筑物过坝和经由翻坝公路过坝的效用相同。     

Port space allocation with a time dimension

In the Port of Singapore, as in many other ports, space has to be allocated in yards for inbound and transit cargo. Requests for container space occur at different times during the planning period, and are made for different quantities and sizes of containers. In this paper, we study space allocation under these conditions. We reduce the problem to a two-dimensional packing problem with a time dimension. Since the problem is NP-hard, we develop heuristic algorithms, using tabu search, simulated annealing, a genetic algorithm and ‘squeaky wheel’ optimization, as solution approaches. Extensive computational experiments compare the algorithms, which are shown to be effective for the problem.     

An approach for analysing transportation costs and a case study

One of the important parameters in the determination of optimal transportation system is economy. Therefore, a realistic method based on the technical, economical and operational parameters of various transportation modes, namely, road, railway, and sea routes is required in the analysis of costs. This method will take into consideration the probable price escalations during the lifetime of a certain transportation system. The cost of a unit of cargo or passenger per route length should be considered since it is an indicator of economics. In this paper, an approach for transportation cost analysis based on the economic analysis of the alternative modes of cargo or passenger transportation, is presented.     

基于遗传算法与贪婪策略的多港口集装箱配载研究

在物流运输行业中,集装箱运输已经成为我国长江沿岸各大港口的主要运输业务。集装箱的处理流程,尤其是集装箱的配载过程直接影响着班轮的运输效率,配载方案的制定对班轮运输起着至关重要的作用。本文针对多港口集装箱船的配载情况,利用CPLEX对该线性规划问题进行求解,并设计遗传算法和贪婪算法对长江沿岸多港口集装箱船配载情形进行对比。通过仿真实验,在小规模时遗传算法与CPLEX求解的精确解相同,验证了遗传算法的有效性。并且在大规模运输情形下,遗传算法得出的结果明显优于贪婪策略,进一步说明了遗传算法是行之有效的。得出的解决方案降低了班轮公司的运输成本,提高了港口的工作效率,对我国长江沿岸港口集装箱配载计划的制定具有一定的指导作用。     

Maritime inventory routing with multiple products: A case study from the cement industry

This paper considers a maritime inventory routing problem faced by a major cement producer. A heterogeneous fleet of bulk ships transport multiple non-mixable cement products from producing factories to regional silo stations along the coast of Norway. Inventory constraints are present both at the factories and the silos, and there are upper and lower limits for all inventories. The ship fleet capacity is limited, and in peak periods the demand for cement products at the silos exceeds the fleet capacity. In addition, constraints regarding the capacity of the ships’ cargo holds, the depth of the ports and the fact that different cement products cannot be mixed must be taken into consideration. A construction heuristic embedded in a genetic algorithmic framework is developed. The approach adopted is used to solve real instances of the problem within reasonable solution time and with good quality solutions.     

Characterization of facility assignment costs for a location-inventory model under truckload distribution

We consider a two-stage distribution system, where the first stage consists of potential distribution centres (DCs) and the second stage consists of geographically dispersed existing retailers. Our goal is to determine the set of open DCs and assignment of open DCs to retailers simultaneously with inventory decisions of retailers. In addition to the DC-specific fixed facility location costs, we explicitly model the inventory replenishment and holding costs at the retailers and truckload transportation costs between the DCs and the retailers. The transportation costs are subject to truck/cargo capacity, leading to an integrated location-inventory problem with explicit cargo costs. We develop a mixed-integer nonlinear model and analyse its structural properties leading to exact expressions for the so-called implied facility assignment costs and imputed per-unit per-mile transportation costs. These expressions analytically demonstrate the interplay between strategic location and tactical inventory/transportation decisions in terms of resulting operational costs. Although both the theory and practice of integrated logistics have recognized the fact that strategic and tactical decisions are interrelated, to the best of our knowledge, our paper is the first to offer closed-form results demonstrating the relationship explicitly. We propose an efficient solution approach utilizing the implied facility assignment costs and we demonstrate that significant savings are realizable when the inventory decisions and cargo costs are modelled explicitly for facility location purposes.     

Maritime crude oil transportation - A split pickup and split delivery problem

The maritime oil tanker routing and scheduling problem is known to the literature since before 1950. In the presented problem, oil tankers transport crude oil from supply points to demand locations around the globe. The objective is to find ship routes, load sizes, as well as port arrival and departure times, in a way that minimizes transportation costs. We introduce a path flow model where paths are ship routes. Continuous variables distribute the cargo between the different routes. Multiple products are transported by a heterogeneous fleet of tankers. Pickup and delivery requirements are not paired to cargos beforehand and arbitrary split of amounts is allowed. Small realistic test instances can be solved with route pre-generation for this model. The results indicate possible simplifications and stimulate further research.     

A mathematical model of inter-terminal transportation

We present a novel integer programming model for analyzing inter-terminal transportation (ITT) in new and expanding sea ports. ITT is the movement of containers between terminals (sea, rail or otherwise) within a port. ITT represents a significant source of delay for containers being transshipped, which costs ports money and affects a port’s reputation. Our model assists ports in analyzing the impact of new infrastructure, the placement of terminals, and ITT vehicle investments. We provide analysis of ITT at two ports, the port of Hamburg, Germany and the Maasvlakte 1 & 2 area of the port of Rotterdam, The Netherlands, in which we solve a vehicle flow combined with a multi-commodity container flow on a congestion based time–space graph to optimality. We introduce a two-step solution procedure that computes a relaxation of the overall ITT problem in order to find solutions faster. Our graph contains special structures to model the long term loading and unloading of vehicles, and our model is general enough to model a number of important real-world aspects of ITT, such as traffic congestion, penalized late container delivery, multiple ITT transportation modes, and port infrastructure modifications. We show that our model can scale to real-world sizes and provide ports with important information for their long term decision making.     

Location of depots in a sugar-beet distribution system

In the following case study the problem of the location of depots in a sugar-beet distribution system for a certain sugar enterprise in Poland is considered. The sugar-beet is delivered from farms to sugar-mills either directly or through some depots. Lower and upper limits on the depot throughputs are imposed. The depot investment and operating costs are estimated by a piecewiselinear function. Given a set of possible depot locations, costs associated with the depots and the unit transportation costs, we seek a minimum cost location-transportation plan determining the number, location and sizes of the depots to be opened and the amounts of the sugar-beet flows. Two solution procedures are developed: (1) The application of MPSX and MIP systems for the problem of the reduced size; (2) The heuristic method. Based upon the computational results both approaches can be treated as alternative solution techniques to the presented problem.     

Optimizing Ports through Computer Simulation Sensitivity Analysis of Pertinent Parameters

This study is concerned with the analysis of the importance of a number of parameters influencing the economic optimum size of a sea port. The combined influence of quay length-as distinct from number of berths-and the total capacity of the cargo handling equipment, expressed as the number of cranes, is studied. The reliability of optimization results is discussed based on their sensitivity to variations in the distributions of ship sizes and crane capacities.     

考虑运营稳定性的内支线班轮航线网络规划模型

货主选择承运航线的影响因素,既包括挂靠港口的计划到港时间与单箱运价,还包括反映班轮运营稳定性的甩箱率与准班率。对此,文章将挂靠港口的航行与在港时间不确定引入研究,并对挂靠港口间的不确定性建立联系,基于航次仿真来计算各挂靠港的到港时间分布、船舶的航次最大载箱量分布。以班轮航线的甩箱率与准班率限制、内支线最大船型与最长往返时间为约束,在优化内支线航线网络结构的同时,计算航线适配船型、班期密度及挂靠港计划到港时间。针对所构建的带不确定参数的NP难问题,文章设计了基于模拟仿真的智能优化算法,通过方案仿真技术来处理输入模型的众分布函数,借助智能优化原理从大范围解空间内寻找满意方案。文末对船舶航次仿真与网络规划模型的有效性进行了验证,算例分析表明:内支线班轮航线网络的货主选择比例达64%,且不论货主更偏好运输时间或价格,航线方案皆能贴近货主偏好。