Liner ship route capacity utilization estimation with a bounded polyhedral container shipment demand pattern

This paper aims to estimate capacity utilization of a liner ship route with a bounded polyhedral container shipment demand pattern, arising in the liner container shipping industry. The proposed maximum and minimum liner ship route capacity utilization problems are formulated as a linear programming model and a min–max model, respectively. We examine two fundamental properties of the min–max model. These two nice properties enable us to develop two ε-optimal global optimization algorithms for solving the min–max model, which find a globally ε-optimal solution by iteratively cutting off the bounded polyhedral container shipment demand set with a cut. The latter algorithm overcomes non-convexity of the remaining feasible demand set generated by the former algorithm via a novel hyperplane cut. Each hyperplane cut can assure that the current vertex of the polyhedral demand set is cut off, whereas solutions that may improve the current one by more than a factor of ε are retained. Extensive numerical experiments for problems larger than those encountered in real applications demonstrate the computational efficacy of the latter algorithm.     

Liner container seasonal shipping revenue management

This paper proposes a liner container seasonal shipping revenue management problem for a container shipping company. For a given weekly multi-type shipment demand pattern in a particular season, the proposed problem aims to maximize the total seasonal shipping profit by determining the number of multi-type containers to be transported and assigned on each container route, the number of containerships deployed on each ship route, and the sailing speed of containerships on each shipping leg subject to both the volume and capacity constraints of each containership. By adopting the realistic bunker consumption rate of a containership as a function of its sailing speed and payload (displacement), we develop a mixed-integer nonlinear programing with a nonconvex objective function for the proposed liner container seasonal shipping revenue management problem. A tailored branch and bound (B&B) method is designed to obtain the global ε-optimal solution of the model. Numerical experiments are finally conducted to assess the efficiency of the solution algorithm and to show the applicability of the developed model.     

Liner container assignment model with transit-time-sensitive container shipment demand and its applications

This paper proposes a practical tactical-level liner container assignment model for liner shipping companies, in which the container shipment demand is a non-increasing function of the transit time. Given the transit-time-sensitive demand, the model aims to determine which proportion of the demand to fulfill and how to transport these containers in a liner shipping network to maximize the total profit. Although the proposed model is similar to multi-commodity network-flow (MCNF) with side constraints, unlike the MCNF with time delay constraints or reliability constraints that is NP-hard, we show that the liner container assignment model is polynomially solvable due to its weekly schedule characteristics by developing two link-based linear programing formulations. A number of practical extensions and applications are analyzed and managerial insights are discussed. The polynomially solvable liner container assignment model is then applied to address several important decision problems proposed by a global liner shipping company.     

Liner ship route schedule design with port time windows

This paper examines a practical tactical liner ship route schedule design problem, which is the determination of the arrival and departure time at each port of call on the ship route. When designing the schedule, the availability of each port in a week, i.e., port time window, is incorporated. As a result, the designed schedule can be applied in practice without or with only minimum revisions. This problem is formulated as a mixed-integer nonlinear nonconvex optimization model. In view of the problem structure, an efficient holistic solution approach is proposed to obtain global optimal solution. The proposed solution method is applied to a trans-Atlantic ship route. The results demonstrate that the port time windows, port handling efficiency, bunker price and unit inventory cost all affect the total cost of a ship route, the optimal number of ships to deploy, and the optimal schedule.     

The nonlinear equation system approach to solving dynamic user optimal simultaneous route and departure time choice problems

Dynamic user optimal simultaneous route and departure time choice (DUO-SRDTC) problems are usually formulated as variational inequality (VI) problems whose solution algorithms generally require continuous and monotone route travel cost functions to guarantee convergence. However, the monotonicity of the route travel cost functions cannot be ensured even if the route travel time functions are monotone. In contrast to traditional formulations, this paper formulates a DUO-SRDTC problem (that can have fixed or elastic demand) as a system of nonlinear equations. The system of nonlinear equations is a function of generalized origin-destination (OD) travel costs rather than route flows and includes a dynamic user optimal (DUO) route choice subproblem with perfectly elastic demand and a quadratic programming (QP) subproblem under certain assumptions. This study also proposes a solution method based on the backtracking inexact Broyden–Fletcher–Goldfarb–Shanno (BFGS) method, the extragradient algorithm, and the Frank-Wolfe algorithm. The BFGS method, the extragradient algorithm, and the Frank-Wolfe algorithm are used to solve the system of nonlinear equations, the DUO route choice subproblem, and the QP subproblem, respectively. The proposed formulation and solution method can avoid the requirement of monotonicity of the route travel cost functions to obtain a convergent solution and provide a new approach with which to solve DUO-SRDTC problems. Finally, numeric examples are used to demonstrate the performance of the proposed solution method.     

A multi‐class mean‐excess traffic equilibrium model with elastic demand

Recent empirical studies have revealed that travel time variability plays an important role in travelers' route choice decisions. To simultaneously account for both reliability and unreliability aspects of travel time variability, the concept of mean‐excess travel time (METT) was recently proposed as a new risk‐averse route choice criterion. In this paper, we extend the mean‐excess traffic equilibrium model to include heterogeneous risk‐aversion attitudes and elastic demand. Specifically, this model explicitly considers (1) multiple user classes with different risk‐aversions toward travel time variability when making route choice decisions under uncertainty and (2) the elasticity of travel demand as a function of METT when making travel choice decisions under uncertainty. This model is thus capable of modeling travelers' heterogeneous risk‐averse behaviors with both travel choice and route choice considerations. The proposed model is formulated as a variational inequality problem and solved via a route‐based algorithm using the modified alternating direction method. Numerical analyses are also provided to illustrate the features of the proposed model and the applicability of the solution algorithm. Copyright © 2012 John Wiley & Sons, Ltd.     

A tailored branch-and-price approach for a joint tramp ship routing and bunkering problem

This paper deals with a practical tramp ship routing problem while taking into account different bunker prices at different ports, which is called the joint tramp ship routing and bunkering (JSRB) problem. Given a set of cargoes to be transported and a set of ports with different bunker prices, the proposed problem determines how to route ships to carry the cargoes and the amount of bunker to purchase at each port, in order to maximize the total profit. After building an integer linear programming model for the JSRB problem, we propose a tailored branch-and-price (B&P) solution approach. The B&P approach incorporates an efficient method for obtaining the optimal bunkering policy and a novel dominance rule for detecting inefficient routing options. The B&P approach is tested with randomly generated large-scale instances derived from real-world planning problems. All of the instances can be solved efficiently. Moreover, the proposed approach for the JSRB problem outperforms the conventional sequential planning approach and can incorporate the prediction of future cargo demand to avoid making myopic decisions.     

Modeling stochastic perception error in the mean-excess traffic equilibrium model

In this paper, we extend the α-reliable mean-excess traffic equilibrium (METE) model of Chen and Zhou (Transportation Research Part B 44(4), 2010, 493-513) by explicitly modeling the stochastic perception errors within the travelers’ route choice decision processes. In the METE model, each traveler not only considers a travel time budget for ensuring on-time arrival at a confidence level α, but also accounts for the impact of encountering worse travel times in the (1 − α) quantile of the distribution tail. Furthermore, due to the imperfect knowledge of the travel time variability particularly in congested networks without advanced traveler information systems, the travelers’ route choice decisions are based on the perceived travel time distribution rather than the actual travel time distribution. In order to compute the perceived mean-excess travel time, an approximation method based on moment analysis is developed. It involves using the conditional moment generation function to derive the perceived link travel time, the Cornish-Fisher Asymptotic Expansion to estimate the perceived travel time budget, and the Acerbi and Tasche Approximation to estimate the perceived mean-excess travel time. The proposed stochastic mean-excess traffic equilibrium (SMETE) model is formulated as a variational inequality (VI) problem, and solved by a route-based solution algorithm with the use of the modified alternating direction method. Numerical examples are also provided to illustrate the application of the proposed SMETE model and solution method.     

Dynamic optimization of ship energy efficiency considering time-varying environmental factors

Nowadays, optimization of ship energy efficiency attracts increasing attention in order to meet the requirement for energy conservation and emission reduction. Ship operation energy efficiency is significantly influenced by environmental factors such as wind speed and direction, water speed and depth. Owing to inherent time-variety and uncertainty associated with these various factors, it is very difficult to determine optimal sailing speeds accurately for different legs of the whole route using traditional static optimization methods, especially when the weather conditions change frequently over the length of a ship route. Therefore, in this paper, a novel dynamic optimization method adopting the model predictive control (MPC) strategy is proposed to optimize ship energy efficiency accounting for these time-varying environmental factors. Firstly, the dynamic optimization model of ship energy efficiency considering time-varying environmental factors and the nonlinear system model of ship energy efficiency are established. On this basis, the control algorithm and controller for the dynamic optimization of ship energy efficiency (DOSEE) are designed. Finally, a case study is carried out to demonstrate the validity of this optimization method. The results indicate that the optimal sailing speeds at different time steps could be determined through the dynamic optimization method. This method can improve ship energy efficiency and reduce CO₂ emissions effectively.     

Short/medium-term prediction for the aviation emissions in the en route airspace considering the fluctuation in air traffic demand

This paper proposes a novel short/medium-term prediction method for aviation emissions distribution in en route airspace. An en route traffic demand model characterizing both the dynamics and the fluctuation of the actual traffic demand is developed, based on which the variation and the uncertainty of the short/medium-term traffic growth are predicted. Building on the demand forecast the Boeing Fuel Flow Method 2 is applied to estimate the fuel consumption and the resulting aviation emissions in the en route airspace. Based on the traffic demand prediction and the en route emissions estimation, an aviation emissions prediction model is built, which can be used to forecast the generation of en route emissions with uncertainty limits. The developed method is applied to a real data set from Hefei Area Control Center for the en route emission prediction in the next 5 years, with time granularities of both months and years. To validate the uncertainty limits associated with the emission prediction, this paper also presents the prediction results based on future traffic demand derived from the regression model widely adopted by FAA and Eurocontrol. The analysis of the case study shows that the proposed method can characterize well the dynamics and the fluctuation of the en route emissions, thereby providing satisfactory prediction results with appropriate uncertainty limits. The prediction results show a gradual growth at an average annual rate of 7.74%, and the monthly prediction results reveal distinct fluctuation patterns in the growth.     

Segment-based alteration for container liner shipping network design

Container liner shipping companies only partially alter their shipping networks to cope with the changing demand, rather than entirely redesign and change the network. In view of the practice, this paper proposes an optimal container liner shipping network alteration problem based on an interesting idea of segment, which is a sequence of legs from a head port to a tail port that are visited by the same type of ship more than once in the existing shipping network. In segment-based network alteration, the segments are intact and each port is visited by the same type of ship and from the same previous ports. As a result, the designed network needs minimum modification before implementation. A mixed-integer linear programming model with a polynomial number of variables is developed for the proposed segmented-based liner shipping network alternation problem. The developed model is applied to an Asia–Europe–Oceania liner shipping network with a total of 46 ports and 11 ship routes. Results demonstrate that the problem could be solved efficiently and the optimized network reduces the total cost of the initial network considerably.     

Game-theoretical models for competition analysis in a new emerging liner container shipping market

This paper develops three game-theoretical models to analyze shipping competition between two carriers in a new emerging liner container shipping market. The behavior of each carrier is characterized by an optimization model with the objective to maximize his payoff by setting optimal freight rate and shipping deployment (a combination of service frequency and ship capacity setting). The market share for each carrier is determined by the Logit-based discrete choice model. Three competitive game strategic interactions are further investigated, namely, Nash game, Stackelberg game and deterrence by taking account of the economies of scale of the ship capacity settings. Three corresponding competition models with discrete pure strategy are formulated as the variables in shipment deployment are indivisible and the pricing adjustment is step-wise in practice. A ɛ -approximate equilibrium and related numerical solution algorithm are proposed to analyze the effect of Nash equilibrium. Finally, the developed models are numerically evaluated by a case study. The case study shows that, with increasing container demand in the market, expanding ship capacity setting is preferable due to its low marginal cost. Furthermore, Stackelberg equilibrium is a prevailing strategy in most market situations since it makes players attain more benefits from the accommodating market. Moreover, the deterrence effects largely depend on the deterrence objective. An aggressive deterrence strategy may make potential monopolist suffer large benefit loss and an easing strategy has little deterrence effect.     

Estimating road network accessibility during a hurricane evacuation: A case study of hurricane Irma in Florida

Understanding the spatio-temporal road network accessibility during a hurricane evacuation—the level of ease of residents in an area in reaching evacuation destination sites through the road network—is a critical component of emergency management. While many studies have attempted to measure road accessibility (either in the scope of evacuation or beyond), few have considered both dynamic evacuation demand and characteristics of a hurricane. This study proposes a methodological framework to achieve this goal. In an interval of every six hours, the method first estimates the evacuation demand in terms of number of vehicles per household in each county subdivision (sub-county) by considering the hurricane’s wind radius and track. The closest facility analysis is then employed to model evacuees’ route choices towards the predefined evacuation destinations. The potential crowdedness index (PCI), a metric capturing the level of crowdedness of each road segment, is then computed by coupling the estimated evacuation demand and route choices. Finally, the road accessibility of each sub-county is measured by calculating the reciprocal of the sum of PCI values of corresponding roads connecting evacuees from the sub-county to the designated destinations. The method is applied to the entire state of Florida during Hurricane Irma in September 2017. Results show that I-75 and I-95 northbound have a high level of congestion, and sub-counties along the northbound I-95 suffer from the worst road accessibility. In addition, this research performs a sensitivity analysis for examining the impacts of different choices of behavioral response curves on accessibility results.     

A joint optimization model for liner container cargo assignment problem using state-augmented shipping network framework

This paper proposes a state-augmented shipping (SAS) network framework to integrate various activities in liner container shipping chain, including container loading/unloading, transshipment, dwelling at visited ports, in-transit waiting and in-sea transport process. Based on the SAS network framework, we develop a chance-constrained optimization model for a joint cargo assignment problem. The model attempts to maximize the carrier’s profit by simultaneously determining optimal ship fleet capacity setting, ship route schedules and cargo allocation scheme. With a few disparities from previous studies, we take into account two differentiated container demands: deterministic contracted basis demand received from large manufacturers and uncertain spot demand collected from the spot market. The economies of scale of ship size are incorporated to examine the scaling effect of ship capacity setting in the cargo assignment problem. Meanwhile, the schedule coordination strategy is introduced to measure the in-transit waiting time and resultant storage cost. Through two numerical studies, it is demonstrated that the proposed chance-constrained joint optimization model can characterize the impact of carrier’s risk preference on decisions of the container cargo assignment. Moreover, considering the scaling effect of large ships can alleviate the concern of cargo overload rejection and consequently help carriers make more promising ship deployment schemes.     

Integrating multi-source maritime information to estimate ship exhaust emissions under wind,wave and current conditions

How to accurately calculate ship exhaust emissions has become urgent needs. In this paper, multi-source maritime information is integrated to estimate ship exhaust emissions under ocean environment. Influences of wind, wave and current on ship speed are firstly analyzed and mathematically modeled. Based on the influences, ocean environment information and ship trajectories are integrated to identify ship activities exactly. After that, ship activity based calculation method is present to obtain exhaust emissions from ship in various activities. Contribution ratios of different ship type and ship activities have been further discussed. In a case study of Ningbo-Zhoushan port in China, greenhouse gas (CO₂, CO, SO_x, NO_x and PM) emissions from ships in 2014 calculated by the proposed method are 8.72 × 10⁵ ton, 2.07 × 10³ ton, 1.47 × 10⁴ ton, 2.60 × 10⁴ ton and 1.40 × 10³ ton respectively. The maximum error is under 10%. Experimental results illustrate that the proposed method can produce more accurate ship exhaust emissions than traditional method under ocean environment conditions.     

A solution algorithm for a dynamic deterministic user equilibrium assignment model with departure time choice

Abstract

A route-based combined model of dynamic deterministic route and departure time choice and a solution method for many origin and destination pairs is proposed. The divided linear travel time model is used to calculate the link travel time and to describe the propagation of flow over time. For the calculation of route travel times, the predictive ideal route travel time concept is adopted. Solving the combined model of dynamic deterministic route and departure time choice is shown to be equivalent to solving simultaneously a system of non-linear equations. A Newton-type iterative scheme is proposed to solve this problem. The performance of the proposed solution method is demonstrated using a version of the Sioux Falls network. This shows that the proposed solution method produces good equilibrium solutions with reasonable computational cost.     

Optimal bus service patterns and frequencies considering transfer demand elasticity with genetic algorithm

This paper attempts to optimize bus service patterns (i.e., all-stop, short-turn, and express) and frequencies which minimize total cost, considering transfer demand elasticity. A mathematical model is developed based on the objective total cost for a generalized bus route, which is optimized subject to a set of constraints ensuring sufficient capacity, an operable bus fleet, and service frequency conservation. To optimize the integrated service of a bus route with many stops, which is a combinatorial optimization problem, a genetic algorithm is developed and applied to search for the solution. A case study, based on a real-world bus route in New Jersey, is conducted to demonstrate the applicability and effectiveness of the developed model and the solution algorithm. Results show that the proposed methodology is fairly efficient, and the optimized bus service significantly reduces total cost.     

An epsilon-optimal algorithm considering greenhouse gas emissions for the management of a ship’s bunker fuel

This paper provides an algorithm to minimize the fixed ordering, purchase, and inventory-carrying costs associated with bunker fuel together with ship time costs; and environmental costs associated with greenhouse gas emissions. It determines the optimum ship speed, bunkering ports, and amounts of bunker fuel for a given ship’s route. To solve the problem, we use an epsilon-optimal algorithm by deriving a property. The algorithm is illustrated by applying it to typical sample data obtained and the effects of bunker prices, carbon taxes, and ship time costs on the ship speed are analyzed. The results indicate that the ship speed and CO₂ emissions are highly sensitive to the factors considered.     

Robust intermodal hub location under polyhedral demand uncertainty

In this study, we consider the robust uncapacitated multiple allocation p-hub median problem under polyhedral demand uncertainty. We model the demand uncertainty in two different ways. The hose model assumes that the only available information is the upper limit on the total flow adjacent at each node, while the hybrid model additionally imposes lower and upper bounds on each pairwise demand. We propose linear mixed integer programming formulations using a minmax criteria and devise two Benders decomposition based exact solution algorithms in order to solve large-scale problems. We report the results of our computational experiments on the effect of incorporating uncertainty and on the performance of our exact approaches.     

Design of public transit network in urban area with elastic demand

This research focuses on an efficient design of transit network in urban areas. The system developed is used to create, analyze and optimize routes and frequencies of transit system in the network level. The analysis is based on elastic demand, so the shift of demand between modes in network due to different service level is of prime consideration. The developed system creates all feasible routes connecting all pairs of terminals in the network. Out of this vast pool of routes, a set of optimal routes is generated for a certain predetermined number that maintains connectivity of significant demand. Based on these generated routes, the system fulfils transportation demand by assigning demand that considers path and route choices for non-transit users and transit users. Together with the assignment of demand, transit frequencies are optimized and the related fleet-size is calculated. Having an optimal setting of solution, the system is continued by reconnecting the routes to find some other better solutions in the periphery of the optimal setting. A set of mathematical programming modules is developed. Real data from Sioux Falls city network is used to evaluate the performance of the model and compare with other heuristic methods.