A study of container berth allocation

This study is based on a major container terminal operator in Hong Kong. Container terminals form a link in the transport chain for transhipment and temporary storage of containers. The service time for vessels including waiting time for berthing must be minimal in order to reduce costs for shipping lines. The use of heuristics and computer simulation to measure different allocation strategies is demonstrated. The existing performance measures of allocation are evaluated and prioritized. Three sets of allocation policies are developed to tackle the day-to-day allocation problems with a view to increasing operational efficiency and enhancing customer service levels. Results show that all three proposed allocation policies have substantial improvements over the existing policy.     

Bi-objective optimization for the container terminal integrated planning

In this paper, we study the joint optimization of the tactical berth allocation and the tactical yard allocation in container terminals, which typically consist of berth side and yard side operations. The studied two objectives are: (i) the minimization of the violation of the vessels’ expected turnaround time windows with the purpose of meeting the timetables published by shipping liners, and (ii) the minimization of the total yard transportation distance with the aim to lower terminal operational cost. We propose a bi-objective integer program which can comprehensively address the import, export and transshipment tasks in port daily practice. Traditionally, a container transshipment task is performed as a couple of import and export tasks, called indirect-transshipment mode, in which the transit container are needed to be temporally stored in the yard. As the way of transferring containers directly from the incoming vessel to the outgoing vessel, called direct-transshipment mode, has potential to save yard storage resources, the proposed model also incorporates both indirect- and direct-transshipment modes. To produce Pareto solutions efficiently, we devise heuristic approaches. Numerical experiments have been conducted to demonstrate the efficiency of the approaches.     

Storage space allocation in container terminals

Container terminals are essential intermodal interfaces in the global transportation network. Efficient container handling at terminals is important in reducing transportation costs and keeping shipping schedules. In this paper, we study the storage space allocation problem in the storage yards of terminals. This problem is related to all the resources in terminal operations, including quay cranes, yard cranes, storage space, and internal trucks. We solve the problem using a rolling-horizon approach. For each planning horizon, the problem is decomposed into two levels and each level is formulated as a mathematical programming model. At the first level, the total number of containers to be placed in each storage block in each time period of the planning horizon is set to balance two types of workloads among blocks. The second level determines the number of containers associated with each vessel that constitutes the total number of containers in each block in each period, in order to minimize the total distance to transport the containers between their storage blocks and the vessel berthing locations. Numerical runs show that with short computation time the method significantly reduces the workload imbalance in the yard, avoiding possible bottlenecks in terminal operations.     

The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery

Once limited to the military domain, unmanned aerial vehicles are now poised to gain widespread adoption in the commercial sector. One such application is to deploy these aircraft, also known as drones, for last-mile delivery in logistics operations. While significant research efforts are underway to improve the technology required to enable delivery by drone, less attention has been focused on the operational challenges associated with leveraging this technology. This paper provides two mathematical programming models aimed at optimal routing and scheduling of unmanned aircraft, and delivery trucks, in this new paradigm of parcel delivery. In particular, a unique variant of the classical vehicle routing problem is introduced, motivated by a scenario in which an unmanned aerial vehicle works in collaboration with a traditional delivery truck to distribute parcels. We present mixed integer linear programming formulations for two delivery-by-drone problems, along with two simple, yet effective, heuristic solution approaches to solve problems of practical size. Solutions to these problems will facilitate the adoption of unmanned aircraft for last-mile delivery. Such a delivery system is expected to provide faster receipt of customer orders at less cost to the distributor and with reduced environmental impacts. A numerical analysis demonstrates the effectiveness of the heuristics and investigates the tradeoffs between using drones with faster flight speeds versus longer endurance.     

Container liner fleet deployment: A systematic overview

Container liner fleet deployment (CLFD) is the assignment of containerships to port rotations (ship routes) for efficient transport of containers. As liner shipping services have fixed schedules, the ship-related operating cost is determined at the CLFD stage. This paper provides a critical review of existing mathematical models developed for the CLFD problems. It first gives a systematic overview of the fundamental assumptions used by the existing CLFD models. The operating characteristics dealt with in existing studies are then examined, including container transshipment and routing, uncertain demand, empty container repositioning, ship sailing speed optimization and ship repositioning. Finally, this paper points out four important future research opportunities: fleet deployment considering ship surveys and inspections, service dependent demand, pollutant emissions, and CLFD for shipping alliances.     

Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state–space–time network representations

Optimization of on-demand transportation systems and ride-sharing services involves solving a class of complex vehicle routing problems with pickup and delivery with time windows (VRPPDTW). This paper first proposes a new time-discretized multi-commodity network flow model for the VRPPDTW based on the integration of vehicles’ carrying states within space–time transportation networks, so as to allow a joint optimization of passenger-to-vehicle assignment and turn-by-turn routing in congested transportation networks. Our three-dimensional state–space–time network construct is able to comprehensively enumerate possible transportation states at any given time along vehicle space–time paths, and further allows a forward dynamic programming solution algorithm to solve the single vehicle VRPPDTW problem. By utilizing a Lagrangian relaxation approach, the primal multi-vehicle routing problem is decomposed to a sequence of single vehicle routing sub-problems, with Lagrangian multipliers for individual passengers’ requests being updated by sub-gradient-based algorithms. We further discuss a number of search space reduction strategies and test our algorithms, implemented through a specialized program in C++, on medium-scale and large-scale transportation networks, namely the Chicago sketch and Phoenix regional networks.     

A prototype case-based reasoning system for real-time freeway traffic routing

With the recent advances in communications and information technology, real-time traffic routing has emerged as a promising approach to alleviating congestion. Existing approaches to developing real-time routing strategies, however, have limitations. This study examines the potential for using case-based reasoning (CBR), an emerging artificial intelligence paradigm, to overcome such limitations. CBR solves new problems by reusing solutions of similar past problems. To illustrate the feasibility of the approach, the study develops and evaluates a prototype CBR routing system for the interstate network in Hampton Roads, Virginia. Cases for building the system’s case-base are generated using a heuristic dynamic traffic assignment (DTA) model designed for the region. Using a second set of cases, the study evaluates the performance of the prototype system by comparing its solutions to those of the DTA model. The evaluation results demonstrate that the prototype system is capable of running in real-time, and of producing high quality solutions using case-bases of reasonable size.     

Dynamic yield management when aircraft assignments are subject to swap

As a practical form of demand driven dispatch at some major airlines in North America, cockpit compatible aircraft of different capacities are paired in the fleet assignment for a possible future swap on the two involved flights. They are paired in such a way that the swap does not affect their aircraft routings on other legs. The swap decision depends on demand realization on the two flights and is made at a predetermined time prior to departure. Yield management on the two flights is studied in this paper. We begin by studying a base problem in which at a certain time before departure, the assignment on a flight is subject to change with a fixed probability. The base problem extends the threshold policy into the case where future capacity is uncertain. Secondly, we propose a heuristic for yield management over two flights with swappable aircraft by repeatedly updating the swap probability as demand unfolds. Our numerical result shows that this policy significantly enhances the airline’s capability to increase revenue under demand driven dispatch. In addition, the base problem may shed lights on derivation of optimal yield management policy in irregular operational settings where final capacity assignment is independent of yield management policy.     

Scheduling heterogeneous train traffic on double tracks with efficient dispatching rules

To further improve the utilization rate of railway tracks and reduce train delays, this paper focuses on developing a high-efficiency train routing and timetabling approach for double-track railway corridors in condition that trains are allowable to travel on reverse direction tracks. We first design an improved switchable policy which is rooted in the approaches by Mu and Dessouky (2013), with the analysis of possible delays caused by different path choices. Then, three novel integrated train routing and timetabling approaches are proposed on the basis of a discrete event model and different dispatching rules, including no switchable policy (No-SP), Mu and Dessouky (2013)’s switchable policy (Original-SP) and improved switchable policy (Improved-SP). To demonstrate the performance of the proposed approaches, the heterogeneous trains on Beijing–Shanghai high speed railway are scheduled by aforementioned approaches. The case studies indicate that in comparison to No-SP and Original-SP approaches, respectively, the Improved-SP approach can reduce the total delay of trains up to 44.44% and 73.53% within a short computational time. Moreover, all of the performance criteria of the Improved-SP approach are usually better than those of other two approaches.     

Introducing change to transportation and energy systems: the case of alcohol fuels

This paper describes the application of optimization techniques to the problems of garage location and bus routing. The technique employed involves the decomposition of a garage location and bus routing model into two submodels. Solutions for the garage location and bus routing submodels are combined iteratively to find an optimal solution for the overall optimization model. Significant cost savings realizable for the Transit Authority of River City (Louisville, Kentucky) were calculated by implementing the results.     

Rail freight transportation: A review of recent optimization models for train routing and empty car distribution

This paper describes two types of rail transportation problems in detail. These are train routing and makeup, and empty car distribution problems. Some of the recent optimization models which address these problems are reviewed and the areas for potential improvements in rail transportation literature are identified. The type of interactions which exist between routing, makeup, and empty car distribution decisions are highlighted and potential areas for future research are identified.     

Performance analysis of the phase swap sorting strategy for an isolated intersection

A separate left-turn phase wastes the capacity of intersection, because all the lanes on the approach are not fully utilized during either the left-turn or through green phase. Under the phase swap sorting strategy (Xuan, 2011), different types of movements can be reorganized by a pre-signal so that all the lanes in the sorting area can be used to discharge vehicles during their green phases. Thus the capacity is improved significantly. In fact, when a pre-signal is installed upstream of the intersection signal (also named main signal), the two signals will have a great impact on not only the capacity, but other traffic performances, such as delays, queue formations, maximum queue length, residual queue, and spillback, etc., which are very important performance factors for the design and application of the phase swap sorting strategy. In order to more fully quantify and characterize the performance of the phase swap sorting strategy, a three-dimensional Markov queueing model is presented. Two levels of performance evaluation indices are formulated using the matrix analytic techniques. All these indices can be used to establish a more comprehensive analytical framework to evaluate the use of the phase swap sorting strategy. Model validation shows that the proposed model can provide a reliable performance analysis for the phase swap sorting strategy under various different conditions. In addition, in order to intuitively illustrate the effects of various factors on the performance of the phase swap sorting strategy, a series of numerical experiments is conducted.     

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.     

Cranes scheduling in frame bridges based automated container terminals

This paper investigates crane scheduling problems for a new type of automated container terminal system, which is based on multi-storey frame bridges. For the new design concept, this paper studies how to schedule two types of cranes, i.e., quay cranes and bridge cranes that transfer containers between different storeys. The schedules of these two types of cranes impact the operation efficiency of the terminal system. Mathematical models are proposed for the two scheduling problems. Meta-heuristics are developed to solve them. Numerical experiments are conducted to validate the effectiveness of the proposed models and the efficiency of the proposed solution method.     

Weather impact on containership routing in closed seas: A chance-constraint optimization approach

Weather conditions have a strong effect on the operation of vessels and unavoidably influence total time at sea and associated transportation costs. The velocity and direction of the wind in particular may considerably affect travel speed of vessels and therefore the reliability of scheduled maritime services. This paper considers weather effects in containership routing; a stochastic model is developed for determining optimal routes for a homogeneous fleet performing pick-ups and deliveries of containers between a hub and several spoke ports, while incorporating travel time uncertainties attributed to the weather. The problem is originally formulated as a chance-constrained variant of the vehicle routing problem with simultaneous pick-ups and deliveries and time constraints and solved using a genetic algorithm. The model is implemented to a network of island ports of the Aegean Sea. Results on the application of algorithm reveal that a small fleet is sufficient enough to serve network’s islands, under the influence of minor delays. A sensitivity analysis based on alternative scenarios in the problem’s parameters, leads to encouraging conclusions with respect to the efficiency and robustness of the algorithm.     

A set-covering model for a bidirectional multi-shift full truckload vehicle routing problem

This paper introduces a bidirectional multi-shift full truckload transportation problem with operation dependent service times. The problem is different from the previous container transport problems and the existing approaches for container transport problems and vehicle routing pickup and delivery are either not suitable or inefficient. In this paper, a set covering model is developed for the problem based on a novel route representation and a container-flow mapping. It was demonstrated that the model can be applied to solve real-life, medium sized instances of the container transport problem at a large international port. A lower bound of the problem is also obtained by relaxing the time window constraints to the nearest shifts and transforming the problem into a service network design problem. Implications and managerial insights of the results by the lower bound results are also provided.     

Positive impact of distribution centres on the environment

The transport sector in general, and trucks in particular, generates a significant amount of emissions in Australia. It appears the trend will escalate unless different measures are taken to reduce the reliance of freight transport on trucks. This paper discusses the benefits of distribution centres as a means to reduce road congestion, increase safety, protect the environment by reducing atmospheric pollution and improve freight distribution. It also provides the effective use of the existing rail network and its infrastructure and improves the lead-time as well as lowering the cost of transportation of cargo. It also investigates the positive impact of distribution centres located near to manufacturing and farming production units. A simulation model has been developed and used to help determine the amount of atmospheric pollution produced by two modes of land transport, rail and road, for the movement of containers between port and destination. Results derived from the model provide evidence about a preferred land-transport regime. The paper has two sections: (1) the role of distribution centres in the chain of transport and (2) the impact of distribution centres on the environment. The first section investigates the feasibility of the implementation of distribution centres in the State of Victoria with respect to rail line capacity and location allocation. The second section presents an additional simulation model that investigates the role of a distribution centre in relation to the amount of atmospheric pollution produced by rail and road, while containers are carried between port and destination.     

Floating car based travel times for city logistics

City logistics routing requires time-dependent travel times for each network link. We rely on the concept of Floating Car Data (FCD) to develop and provide such travel times. Different levels of aggregation in the determination of time-dependent travel times from a database of historical FCD are presented and evaluated with regard to routing quality. Furthermore, a Data Mining approach is introduced, allowing for a substantial reduction of the volume of input data required for city logistics routing. The different approaches are investigated and evaluated by a huge amount of FCD collected for the urban area of Stuttgart, Germany. The results show that the Data Mining approach enables efficient provision of time-dependent travel times without a significant loss of routing quality for city logistics applications.     

The container retrieval problem with respect to relocation

The demand for container terminal yards is growing significantly faster than the supply of available land; therefore, containers are typically stacked high to better utilize the land space in container yards. However, in the process of container retrieval, non-productive reshuffling may be required to relocate the containers that are stacked on top of the target container. Container retrieval is directly related to the operational efficiency of terminals. Because the industry has become increasingly competitive, it has become critical to introduce a systematic approach to retrieving containers. In this study, we develop a heuristic that can generate feasible working plans for rail-mounted gantry cranes (RMGC) in container yards to minimize the number of container movements while taking the RMGC working time into consideration. The methodology takes into consideration the case that containers are grouped in terms of their retrieval order. Multi-lift RMGC models also are studied. Comprehensive numerical experiments reveal that the method runs faster than other methods published in the literature by several orders of magnitude; additionally, our method is able to solve instances larger than practical use. The number of movements approaches a theoretical lower bound, and the numerical results clearly demonstrate the tradeoff between the number of movements and the working time, and provide useful insights for yard planning.     

A frequency-based maritime container assignment model

This paper transfers the classic frequency-based transit assignment method of Spiess and Florian to containers demonstrating its promise as the basis for a global maritime container assignment model. In this model, containers are carried by shipping lines operating strings (or port rotations) with given service frequencies. An origin–destination matrix of full containers is assigned to these strings to minimize sailing time plus container dwell time at the origin port and any intermediate transhipment ports. This necessitated two significant model extensions. The first involves the repositioning of empty containers so that a net outflow of full containers from any port is balanced by a net inflow of empty containers, and vice versa. As with full containers, empty containers are repositioned to minimize the sum of sailing and dwell time, with a facility to discount the dwell time of empty containers in recognition of the absence of inventory. The second involves the inclusion of an upper limit to the maximum number of container moves per unit time at any port. The dual variable for this constraint provides a shadow price, or surcharge, for loading or unloading a container at a congested port. Insight into the interpretation of the dual variables is given by proposition and proof. Model behaviour is illustrated by a simple numerical example. The paper concludes by considering the next steps toward realising a container assignment model that can, amongst other things, support the assessment of supply chain vulnerability to maritime disruptions.