A reactive tabu search algorithm for the multi-depot container truck transportation problem

A container truck transportation problem that involves multiple depots with time windows at both origins and destinations, including the reposition of empty containers, is formulated as a multi-traveling salesman problem with time windows (m-TSPTW) with multiple depots. Since the problem is NP-hard, a cluster method and a reactive tabu search (RTS) algorithm are developed to solve the problem. The two methods are compared with the mixed integer program which can be used to find optimum solutions for small size problems. The computational results show that the developed methods, particularly the RTS algorithm, can be efficiently used to solve the problem.     

A GRASP algorithm for the container stowage slot planning problem

This work presents a generalization of the Slot Planning Problem which raises when the liner shipping industry needs to plan the placement of containers within a vessel (stowage planning). State-of-the-art stowage planning relies on a heuristic decomposition where containers are first distributed in clusters along the vessel. For each of those clusters a specific position for each container must be found. Compared to previous studies, we have introduced two new features: the explicit handling of rolled out containers and the inclusion of separations rules for dangerous cargo. We present a novel integer programming formulation and a Greedy Randomized Adaptive Search Procedure (GRASP) to solve the problem. The approach is able to find high-quality solution within 1 s. We also provide comparison with the state-of-the-art on an existing and a new set of benchmark instances.     

Tactical berth and yard template design at container transshipment terminals: A column generation based approach

Quay-side berthing congestion is an emerging challenging issue that arises in busy container transshipment terminals and calls for effective management of terminal operations. This paper tackles the berthing congestion problem by introducing a proactive management strategy from the terminal’s perspective that adjusts the calling schedule of feeder vessels in such a way that the quay-side workload distribution in the temporal dimension can be balanced. Such a schedule template design problem is considered simultaneously with another two tactical level decision problems, berth template design (i.e., determining preferred berthing positions for vessels) and yard template design (i.e., allocating storage yard space to transshipment flows). This highly integrated problem is formulated as a set covering model. Heuristic methods based on column generation are developed to obtain near-optimal solutions in an efficient way. Computational experiments on real-world sized test instances demonstrate the efficiency and effectiveness of the proposed approach.     

Terminal and yard allocation problem for a container transshipment hub with multiple terminals

This paper presents an integer programming model for the terminal and yard allocation problem in a large container transshipment hub with multiple terminals. The model integrates two decisions: terminal allocation for vessels and yard allocation for transshipment container movements within a terminal as well as between terminals. The objective function aims to minimize the total inter-terminal and intra-terminal handling costs generated by transshipment flows. To solve the problem, we develop a 2-level heuristic algorithm to obtain high quality solutions in an efficient way. Computational experiments show the effectiveness of the proposed approach.     

Space allocating strategies for improving import yard performance at marine terminals

This paper focuses on the organization of the import storage yard at container port terminals. Three new stacking strategies are introduced which take into account the containers’ arrival and departure rates and the storage yard characteristics. A mathematical model based on probabilistic distribution functions is developed to estimate the number of rehandles required to manage an import container yard. The model is applied to the three proposed stacking strategies. Results show that the optimal strategy depends on stacking height and the relationship between vessel headway and container dwell time.     

Reducing truck emissions at container terminals in a low carbon economy: Proposal of a queueing-based bi-objective model for optimizing truck arrival pattern

This study proposes a methodology to optimize truck arrival patterns to reduce emissions from idling truck engines at marine container terminals. A bi-objective model is developed minimizing both truck waiting times and truck arrival pattern change. The truck waiting time is estimated via a queueing network. Based on the waiting time, truck idling emissions are estimated. The proposed methodology is evaluated with a case study, where truck arrival rates vary over time. We propose a Genetic Algorithm based heuristic to solve the resulting problem. Result shows that, a small shift of truck arrivals can significantly reduce truck emissions, especially at the gate.     

A model for a multi-size inland container transportation problem

In the multi-size Inland Container Transportation Problem (mICT) trucks are able to transport up to two 20-foot or one 40-foot container at a time along routes with various pickup and delivery locations. A mixed-integer linear program for the mICT is presented using two alternative objective functions: minimization of the total travel distance and minimization of the total operation time of the trucks. The presented model is tested on instances which vary in size. Computational experiments show that by means of the presented model small problem instances can be solved optimally.     

Modeling the mixed storage strategy for quay crane double cycling in container terminals

A mixed storage strategy was proposed to improve the efficiency of yard operations and horizontal transportation to corporate with quay crane double cycling. The effects of the mixed storage strategy on terminal operations, including truck travel distance, yard crane operations and the number of required trucks, were analyzed. An approach based on cycle-time models, the queuing theory was proposed to evaluate the performances from long-term run. Results show using the mixed storage strategy, the truck travel distance can be decreased and the number of required trucks and yard crane’s operation time can be reduced by 16% and 26% respectively.     

A heuristic algorithm for yard truck scheduling and storage allocation problems

The yard truck scheduling and the storage allocation are two important decision problems affecting the efficiency of container terminal operations. This paper proposes a novel approach that integrates these two problems into a whole. The objective is to minimize the weighted sum of total delay of requests and the total travel time of yard trucks. Due to the intractability of the proposed problem, a hybrid insertion algorithm is designed for effective problem solutions. Computational experiments are conducted to examine the key factors of the problem and the performance of the proposed heuristic algorithm.     

A tabu search heuristic for the local container drayage problem under a new operation mode

This paper examines the Local Container Drayage Problem (LCDP) under an operation mode in which a tractor can be detached from its companion trailer and assigned to a new task. We have incorporated a set of temporal constraints into the classical VRP to realize this operation by utilizing the idle time available to tractors and coordinating the empty containers moving between customers. A tabu search algorithm is proposed. Some numerical experiments are conducted to assess the performance of the proposed algorithm, quantify the benefit of the new operation mode, and identify the conditions under which the mode is effective.     

A polynomial-time heuristic for the quay crane double-cycling problem with internal-reshuffling operations

One of great challenges in seaport management is how to handle containers under reshuffling, called reshuffles. Repositioning reshuffles in a bay (internal reshuffling) can improve the efficiency of quay cranes and help ports to reduce ship turn-around time. This paper studies the quay crane double-cycling problem with internal-reshuffling operations, and presents a fast solution algorithm. To reduce the number of operations necessary to turn around a bay of a vessel, the problem is first formulated as a new integer program. A polynomial-time heuristic is then developed. The analysis is made on the worst-case error bound of the proposed algorithm. Results are presented for a suite of combinations of problem instances with different bay sizes and workload scenarios. Comparisons are made between our algorithm and the start-of-the-art heuristic. The computational results demonstrate that our model can be solved more efficiently with CPLEX than the model proposed by Meisel and Wichmann (2010), and the proposed algorithm can well solve real-world problem instances within several seconds.     

Implications of the ageing society and internationalisation for airport services: A perspective on passenger demand for personal space at airport terminals

“Per-passenger-space” has been used as one of the fundamental units of Level of Service (LOS) measurement to evaluate the capacity of airport terminals for passenger comfort and service satisfaction. This study addresses the questions of how air passengers perceive personal space as an airport service attribute, and how the territoriality of passengers is moderated by their age and cultural background. Participants were grouped depending on their age and nationality for a comparative study. The results from the Repertory Grid Technique (RGT) and open-ended questions supported the conclusion that passengers of different age and cultural backgrounds perceive personal space differently, and their service satisfaction would be partially affected by the availability of personal space within the airport terminal. These findings suggest a necessity for alternative LOS standards that are cost-effective and able to reflect changing age structure and cultural composition of air passengers.     

Branch-and-price algorithm for the location-routing problem with time windows

This study proposes a branch-and-price algorithm to solve the Location-Routing Problem with Time Windows (LRPTW) which has never been attempted with the exact solutions before. The problem is solved by the simplex algorithm in the master problem and elementary shortest path problems with resource constraint corresponding to column generation in the subproblem until only the non-negative reduced cost columns remain. The proposed algorithm can solve many testing instances effectively. The computational results and the effect of time windows are also compared and discussed.     

A robust optimization approach for the road network daily maintenance routing problem with uncertain service time

This paper studies the robust optimization approach for the routing problem encountered in daily maintenance operations of a road network. The uncertainty of service time is considered. The robust optimization approach yields routes that minimize total cost while being less sensitive to substantial deviations of service times. A robust optimization model is developed and solved by the branch-and-cut method. In computational experiments, the behavior of the robust solutions and their performance are analyzed using Monte Carlo simulation. The robust optimization model is also compared with a classic chance-constrained programming model. The experimental analysis provides managerial insights for decision makers to determine an appropriate routing strategy.