Shipping Logistics Research: Scheduling and Routing Management

Abstract

Shipping logistics research, particularly in the context of scheduling and routing management, is a critical area of study that addresses the optimization of maritime transportation systems. The thesis focuses on three important phases of shipping logistics management. For the loading phase, we focus on the stack loading problem, considering the load-bearing limit to minimize the number of used stacks and the number of unordered stackings. For the transporting phase, we study the crane scheduling problem on a line to minimize the energy-consuming cost. For the delivery phase, we consider pickup and delivery problems with time window and ride-time constraints to minimize the total distance cost. We aim to provide insights and recommendations in the maritime logistics sector. The findings show the significance of adopting advanced scheduling and routing management solutions to enhance the efficiency, profitability, and environmental responsibility of maritime transportation operations.

In the first part, the stack loading problem with load-bearing limit is considered. Among the different objectives of the problem, minimizing the total number of unordered stackings and minimizing the total number of used stacks are the two important ones, which ensure efficient loading and unloading schedules, as well as reduce storage costs, respectively. The load-bearing setting, where each container has its own weight and bearing weight, is frequently considered in box packing operations but rarely in the existing studies on the stack loading problem. However, the load-bearing constraint on containers is very important for stack loading, because safety is of paramount importance. It is the first study on the stack loading problem with the load-bearing constraint with an aim to minimize the number of stacks and the number of unordered stackings. We show that this problem is strongly NP-hard even when the number of stacks is given and equals 2. For the case where the number of stacks is given and jobs on the bottom tiers are fixed, we show that the problem can be solved by dynamic programming in pseudo-polynomial time. For the general problem, based on a two-index integer linear programming formulation and a tabu search heuristic, we develop a binary-search-based matheuristic. Our experimental results demonstrate the efficiency and effectiveness of the newly developed metaheuristics.

In the second part, the crane scheduling problem at seaport container terminals with energy-saving is studied. During loading and unloading steps, energy is consumed when cranes lift containers, while energy is often wasted when cranes drop containers. In this part, we consider a new mechanism of single crane to schedule containers. The aim is to reuse the energy of containers that are already lifted and to reduce the total energy consumption of the whole scheduling plan. We propose a basic model on a one-dimensional storage area and give a novel interval-based optimal algorithm for the unit-length case. Moreover, we extend to the arbitrary length case and construct a corresponding path cover problem on the interval digraph. Path cover on the general digraph is known to be NP-complete, while the special case, when the digraph is circle-free, can be solved in polynomial time by reducing to the maximum matching problem.

In the last part, the traveling salesman problem with pickup and delivery problem with time window and ride-time constraints is proposed. The problem is an important generalization of the vehicle routing problem and a basic distribution management problem that can be modeled for many real-world problems and consists of designing a set of minimum cost routes, originating and terminating at a central depot, for a fleet of vehicles which services a set of customers with known demands. The problem considered ride-time constraints as well as time window constraints. Three problem formulations including basic arc-based, path-based, and tour-based are proposed. The cut-and-column generation exact method and a comprehensive solution framework using dynamic programming to generate the initial solution as well as using large neighborhood search metaheuristic algorithm are introduced. Computational results show that the proposed solution framework is effective.

Date of Award	14 Aug 2024
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Minming LI (Supervisor)