Designing optimal routes in a liner shipping problem

A real liner shipping problem of deciding optimal weekly routes for a given fleet of ships is considered and a solution method for solving the problem is proposed. First, all feasible routes for each ship are generated together with the cost and the duration for each route. The routes are given as input to an integer programming (IP) problem. By solving the IP problem, routes for each ship are selected such that total transportation costs are minimized and the demand at each port is satisfied. The total duration for the routes that are selected for a given ship must not exceed one week.

The real liner shipping problem is solved together with four randomly generated test problems. The computational results show that proposed solution method is suitable for designing optimal routes in several liner shipping problems.     

Multi-period liner ship fleet planning with dependent uncertain container shipment demand

This paper deals with a realistic multi-period liner ship fleet planning problem by incorporating stochastic dependency of the random and period-dependent container shipment demand. This problem is formulated as a multi-period stochastic programming model with a sequence of interrelated two-stage stochastic programming (2SSP) problems characterized ship fleet planning in each single period. A solution method integrating dual decomposition and Lagrangian relaxation method is designed for solving the developed model. Numerical experiments are carried out to assess applicability and performance of the proposed model and solution algorithm. The results further demonstrate importance of stochastic dependence of the uncertain container shipment demand.     

Fleet deployment optimization for liner shipping: an integer programming model

Extending and improving an earlier work of the second author, an Integer Programming (IP) model is developed to minimize the operating and lay-up costs for a fleet of liner ships operating on various routes. The IP model determines the optimal deployment of an existing fleet, given route, service, charter, and compatibility constraints. Two examples are worked with extensive actual data provided by Flota Mercante Grancolombiana (FMG). The optimal deployment is solved for their existing ship and service requirements and results and conclusions are given.     

A reactive container rerouting model for container flow recovery in a hub-and-spoke liner shipping network

This paper focuses on the container rerouting due to a disruption, aims at making the optimal container flow recovery plan for the affected liner shipping company. First, we make the initial effort to bring up with a basic framework of disruption management for liner shipping. Second, we present a compact integer linear programming model for addressing the container rerouting problem under the proposed framework in a hub-and-spoke liner shipping network, based on a given recovery vessel schedule that determines to omit a port of call. Other shipping companies’ services and other modes (roadway, railway, and airline) as candidate alternative means to transport the miss-connected containers are also incorporated in the proposed model. The container flow recovery plan would select the optimal alternative paths for the miss-connected containers balancing the trade-off between container transport costs and delivery delay penalty costs. Finally, a case study from a global liner shipping company is investigated and the computational results indicate the model can be solved effectively and efficiently for the real-scale problem. Thus, the proposed approach in this paper can supply real-time decision support tool for the liner shipping operators on handling the process of container flow recovery.     

Fleet deployment optimization for liner shipping Part 2. Implementation and results

We use linear programming (LP) for solving the problem of the optimal deployment of an existing fleet of multipurpose or fully containerized ships, among a given set of routes, including information for lay-up time, if any, and type and number of extra ships to charter, based on a detailed and realistic model for the calculation of the operating costs of all the ship types in every route and on a suitable LP formulation developed in earlier work of the authors. The optimization model is also applicable to the problem of finding the best fleet compostion and deployment, in a given set of trade routes, which may be the case when a shipping company is considering new or modified services, or a renewal of the existing fleet. In addition, two promising mixed linear-integer programming formulations are suggested.     

Ship scheduling and container shipment planning for liners in short-term operations

Good short-term ship scheduling and container shipment planning are very important for liner operations; however, in Taiwan, most such carriers currently utilize a trial-and-error process. In this study, we employ network flow techniques to construct a model for such activities. A solution algorithm, based on Lagrangian relaxation, a subgradient method, and a heuristic for the upper-bound solution, is developed to solve the model. To demonstrate and to test how well the model and the solution algorithm apply in the real world, we performed a case study using operating data from a major Taiwanese marine shipping company. The test results show that the model and the solution algorithm could be useful references for ship scheduling and container shipment planning.     

Tactical planning models for managing container flow and ship deployment

This paper addresses two practical problems from a liner shipping company, i.e. the container flow management problem and the ship deployment problem, at the tactical planning level. A sequential model and a joint optimisation model are formulated to solve the problems. Our results show that the company should implement the joint optimisation model at the tactical planning level to improve the shipping capacity utilisation rather than the sequential model used in the current practice. Repositioning empty containers also need to be considered jointly with the nonempty container flow at the tactical planning level. Some important managerial insights into the operational and business processes are gained.     

Connectivity analysis of the global shipping network by eigenvalue decomposition

ABSTRACT

Maritime shipping necessitates flexible and cost-effective port access worldwide through the global shipping network. This paper presents an efficient method to identify major port communities, and analyses the network connectivity of the global shipping network based on community structure. The global shipping network is represented by a signless Laplacian matrix which can be decomposed to generate its eigenvectors and corresponding eigenvalues. The largest gaps between the eigenvalues were then used to determine the optimal number of communities within the network. The eigenvalue decomposition method offers the advantage of detecting port communities without relying on a priori assumption about the number of communities and the size of each community. By applying this method to a dataset collected from seven world leading liner shipping companies, we found that the ports are clustered into three communities in the global container shipping network, which is consistent with the major container trade routes. The sparse linkages between port communities indicate where access is relatively poor.     

Evaluating the trade-off between the level of customer service and transportation costs in a ship scheduling problem

In many ship scheduling problems, time windows are imposed at the loading and/ or discharging of the cargoes to be lifted. Up until now, all proposed solution methods to ship scheduling problems have treated the time window constraints as hard constraints. By transforming the time window constraints into soft constraints, some of the loading/discharging operations may be performed outside the time windows, penalized by an inconvenience cost for not meeting the time window. The motivation behind introducing soft time windows is that, by allowing controlled time window violations for some customers, it may be possible to obtain better routes and significant reductions in the transportation costs. The purpose of this paper is to evaluate the trade-off between transportation costs and the time window violations. Computational results based on data from a real ship scheduling problem are presented and used as a basis for the evaluation.     

The design of liner shipping serives: the problem of feeder services versus multi-port-calls

In this paper, the authors outline the structure of liner shipping systems with special emphasis on the question of whether feeder services are superior in economic terms to the more traditional and commonly-used multi-port-calling system. They describe the theoretical advantages of the former over the latter, and develop a model by which the optimal conditions both operate in may be determined. This model is then applied to a real situation to ascertain whether the theory works in practice. They conclude that the shuuttle/feeder system is worthwhile only in exceptional circumstances when specific route characteristics—low trade density; hinterland generated cargo; inland position of port; and heavy congestion—coexist. Despite the expense of multi-port-calling, it remains the most practical solution to the thin trade problem.     

A combined tramp ship routing,fleet deployment,and network design problem

In this paper, a tramp ship routing model of fleet deployment in a hub-and-spoke network is presented. This model simultaneously determines the selection of hubs, the assignment of spokes to hubs, the deployment of feeder-containerships as well as containership routing between spokes and spokes, hubs and spokes, and hubs and hubs. Even though some parts have been studied, this complex combination of shipping problems has never been addressed. Because the problem is NP-hard, a genetic algorithm (GA) with local search is proposed. In the algorithm, a cut-off procedure is applied to fleet deployment in a sub-route strategy. A number of randomly generated problem instances are solved by both a mathematical program and the GA with local search. A simple but realistic heuristic algorithm is also developed. Both the GA with local search and the heuristic algorithm are used to solve a number of real case instances. A comparison of the results shows the efficiency of the GA with local search. The developed model can be used as a route-decision support tool for shipping companies that provide long-haul shipping services in a hub-and-spoke network.     

Evaluating the trade-off between the level of customer service and transportation costs in a ship scheduling problem

In many ship scheduling problems, time windows are imposed at the loading and/ or discharging of the cargoes to be lifted. Up until now, all proposed solution methods to ship scheduling problems have treated the time window constraints as hard constraints. By transforming the time window constraints into soft constraints, some of the loading/discharging operations may be performed outside the time windows, penalized by an inconvenience cost for not meeting the time window. The motivation behind introducing soft time windows is that, by allowing controlled time window violations for some customers, it may be possible to obtain better routes and significant reductions in the transportation costs. The purpose of this paper is to evaluate the trade-off between transportation costs and the time window violations. Computational results based on data from a real ship scheduling problem are presented and used as a basis for the evaluation.     

沿海内贸集装箱班轮航线优化研究

随着沿海内贸集装箱运输市场的快速发展,各大班轮公司如何把船舶安排到最佳航线上,使有限的船舶资源创造最大的经济利益,成为各大公司研究的课题。根据沿海几大干线港口之间的运量需求,建立非线性规划与整数规划相结合的混合模型,选择典型航线建立运输网络,并对其进行优化。该数学模型可应用于解决我国沿海内贸集装箱船舶运输航线配置问题,进而实现利润最大。     

Fleet deployment in liner shipping: a case study

The fleet deployment problem is an important planning problem in liner shipping. It deals with optimally assigning voyages to available vessels in the fleet and determining vessel routes and schedules in a way that minimizes costs or maximizes profit. This paper presents a new model for a fleet deployment problem in liner shipping, and we also propose a multi-start local search heuristic to solve the problem. The heuristic has been embedded in a prototype decision support system (DSS) that has been implemented and tested at Höegh Autoliners, a major global provider of ro-ro (roll-on roll-off) vehicle transportation services. The heuristic was able to produce high-quality solutions within a few minutes to a real planning problem with more than 55 vessels and 150 voyages over a planning horizon of 4–6 months. Tests indicated that the solutions suggested by the DSS gave between 2 and 10% improvements compared with solutions from manual planning. What is almost equally important is that using the DSS can ease the planning process.     

基于改进粒子群算法的船舶排样问题研究

提出了一种改进的粒子群算法来解决船舶排样问题。该算法将混合蛙跳算法的分组思想引入简化粒子群算法中,粒子能够利用更丰富的信息进行更快地收敛。船舶排样零件形状虽多为不规则图形,但它可以转化为矩形件后再进行排样。剩余矩形排样法是解决矩形件排样问题的一种较好的启发式算法,它既满足BL条件又符合BLF算法的思想,这样就能够对排样过程中产生的空白间隙进行填充,保证了较高的板材利用率,有利于找到较优解。用此算法结合剩余矩形法对2组矩形件进行排样,达到了90%以上的利用率,均优于对比文献,表明了本文算法的有效性。     

港口锚地选址海域适用性评价及优化模型

合理的锚地选址可以保障船舶锚泊安全性,同时可以优化港口的平面布置,提高港口运营效率。总结解决锚地选址问题的现有方法,分析GIS技术在选址问题中的运用,明确锚地选址影响因素并建立综合评价指标体系,同时确定各指标权重值,通过海域适用性评价模型对所有栅格进行综合评价。基于海洋功能区划等约束条件,获得锚地选址的可行方案集,优化比选出最优方案。通过算例分析,验证本文提出的模型合理、可行,可作为锚地选址优化的一种方法。     

市场随机波动下干散货和原油船投资决策研究

运用实物期权博弈理论,建立了航运市场随机波动情况下干散货和原油船舶的投资决策模型,得出了承运人之间同质竞争和差异化竞争时船舶的最优投资准则.理论研究和实证分析均表明:承运人的收益和投资船舶的边际收益随航运市场规模和风险的增加而增加;最优的船舶投资量与航运市场的规模和风险正相关;随着航运市场竞争的加剧,承运人的收益和最优的船舶投资量呈下降趋势;随着承运人之间服务差异化程度的增加,承运人的收益和最优的船舶投资量呈上升趋势.     

环日本海地区的航线优化研究

随着环日本海地区贸易往来的频繁,优化该地区航运网络结构,提升海运通达性,成为推动该地区经济发展的重要手段.因此,提出一个以航运企业利润最大为目标的航线网络优化模型.该模型综合考虑航线、船型与需求间的关系,以船舶的载重量为约束,优化航运企业的资源配置,设计航线及选择适宜船型.利用实际数据对该模型进行检验,结果显示,优化的航线网络以及确定船型在不同经济条件下有所差别,可为环日本海航线的开辟与运营提供借鉴.     

Studying port selection on liner routes: An approach from logistics perspective

The research aims to study the port selection in liner shipping. The central work is to set up a model to deal with port choice decisions. The model solves three matters: ports on a ship’s route; the order of selected ports and loading/unloading ports for each shipment. Its objective is to minimize total cost including ship cost, port tariff, inland transport cost and inventory cost. The model has been applied in real data, with cargo flows between the USA and Northern Europe. Afterwards, two sensitive analyses are considered. The first assesses the impact of a number of port calls on the total cost which relates closely to the viability of two service patterns: multi ports and hub & spoke. The second analyzes the efficiency of large vessels in the scope of a logistics network. The overriding result of this research is to indicate the influence of logistics factors in the decision of port choice. The research emphasizes the necessity to combine different factors when dealing with this topic, or else a result can be one-sided.     

基于SEEMP的船舶营运能效评价指数的开发及应用:韩国某案例研究（英文）

The CO_2 emission reduction policy of the International Maritime Organization(IMO) recommends that the operation of ships,managed by maritime transport companies, should be energy-efficient. An evaluation method that can determine how successfully a ship implements the energy efficiency plan is proposed in this study. To develop this method, the measures required for energy-efficient ship operations according to the Ship Energy Efficiency Management Plan(SEEMP) operational guidelines were selected. The weights of the selected measures, which indicate how they contribute to the energy-efficient operation of a ship, were derived using a survey based on the analytic hierarchy process(AHP) method. Consequently, using these measures and their weights, a new evaluation method was proposed. This evaluation method was applied to shipping companies in South Korea, and their ship operation energy efficiency indices were derived and compared. This evaluation method will be useful to the government and shipping companies in assessing the energy efficiency of ship operations.