Coordinated optimized scheduling of locks and transshipment in inland waterway transportation using binary NSGA‐II

• DOI: http://doi.org/10.1111/itor.12720
• Date: 01 May 2020
• Author: Xiaorong Wang,Hongjun Sun,Bin Ji,Xiaohui Yuan,Yanbin Yuan
• Published date: 01 May 2020

Intl. Trans. in Op. Res. 27 (2020) 1501–1525

DOI: 10.1111/itor.12720

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Coordinated optimized scheduling of locks and transshipment

in inland waterway transportation using binary NSGA-II

Bin Jia,b, Hongjun Sunc, Xiaohui Yuana,d,∗, Yanbin Yuaneand Xiaorong Wangd

aSchool of Hydropowerand Information Engineering, Huazhong University of Science and Technology, Wuhan 430074,

China

bSchool of Traffic & Transportation Engineering, Central South University, Changsha410075, China

cShanghai Marine Equipment Research Institute, Shanghai 200031, China

dState Key Laboratory of Operationand Control of Renewable Energy & Storage Systems, China Electric Power Research

Institute, Beijing 100192, China

eSchool of Resource and Environmental Engineering, Wuhan University of Technology, Wuhan 430070, China

E-mail: cumtjibin@126.com [Ji]; hongjunsun@163.com [Sun]; yxh71@163.com [X. Yuan];

yuanyanbin_whut@163.com [Y.Yuan]; xrwang@epri.sgcc.com.cn [Wang]

Received 4 July2018; received in revised form 11 August 2019; accepted 25 August 2019

Abstract

Traffic congestion in inland waterways caused by insufficient throughput capacity of locks has become a

compelling problem in developed inland shipping countries. In order to avoid excessive time wastedin waiting

for lock service, it is suggested that some types of cargoes should be unloaded at the quays and trans-

ported by road/train to their destinations, which is called water–land transshipment. By this means, the

ships are divided into two groups that either pass the lock or are transshipped at the quays, engendering

the lock and water–land transshipment co-scheduling (LWTC) problem. This paper focuses on the LWTC,

where the roll-on roll-off ships, passenger ships, and general cargo ships that can be transshipped and other

ships that can only pass the lock are considered in a lock-quay co-scheduling system. The LWTC problem

is decomposed into an outer-layer main 0-1 optimization problem and two inner-layer subproblems: lock

scheduling and berth allocation. A multiobjective optimization model is proposed for the LWTC problem

based on its two-layer structure. To solve the LWTC problem, a hybrid heuristic method is proposed, where

a modified binary nondominated sorting genetic algorithm II is proposed to solve the main problem, and

the two subproblems are solved by specific heuristics. The proposed model and hybrid method are tested

on instances extracted from historical data of traffic at Three Gorges Dam, the results of which demon-

strate the feasibility of the model and the superiority of the proposed hybrid heuristic method over other

comparisons.

Keywords:lock; transshipment; multiobjective optimization; binary NSGA-II

∗Corresponding author.

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

1502 B. Ji et al. / Intl. Trans.in Op. Res. 27 (2020) 1501–1525

1. Introduction

Waterway transport always plays an important role in the transportation system for its reliable, effi-

cient, and environmentally friendly nature, where dams are often constructed for flood prevention,

power generation, and shipping improvement (Yuan et al., 2015; Passchyn et al., 2016). However,

the different water levels caused by the dam are also a barrier for ship navigation, where ship locks

are one of the most common auxiliary facilities used to transfer ships (Bugarski et al., 2013). To

make good use of the locks and transfer the ships efficiently, one needs to optimize the processes

for ships passing the lock, which is known as lock scheduling problem.

Ting and Schonfeld (1996, 1998, 1999, 2001) analyze the impact of different lock scheduling

policies on ship delays and costs. Two patterns of tow sequencing, namely, shortest processing

time first (SPF) and maximum processing time saving first are proposed and their performance is

compared to that of first come first served (FCFS) rule in terms of reducing average ship delay

at a single lock (Ting and Schonfeld, 1996). To deal with the scheduling of serial interdependent

locks, the SPF rule is modified to take the ship delays at adjacent locks into consideration (Ting

and Schonfeld, 1998). The fairness of lock service is considered by assigning a fairness threshold

to each ship and the service priority depends on its processing time and threshold (Ting and

Schonfeld, 2001). In Ting and Schonfeld (1999), instead of scheduling the lock, the speeds of the

ships are controlled based on the estimation of their best arrival times with respect to the minimal

delays. Serial locks that extend 600 feet in the Upper Mississippi River (UMR) were studied earlier

(Campbell et al., 2007; Smith et al., 2007; Nauss, 2008; Campbell et al., 2009; Smith and Nauss,

2010). On that river, barges are joined together into tows for transport, which have to be transferred

by locks whose dimensions are often smaller than those of the tows. As a result, the tows have to be

split into smaller groups of barges to meet the capacity of chambers and rejoined for the next phase

of their travel. Campbell et al. (2009) and Smith and Nauss (2010) analyze different strategies for

managing the congestion at locks and use a discrete-event simulation model, which is introduced

in Campbell et al. (2007) and Smith et al. (2007), to evaluate the performance of these strategies. In

addition, optimal sequencing of the tows after lock disruption in the UMR is presented in Nauss

(2008). However, the research mentioned above does not focus on the generalized lock scheduling

problem because the ship placement problem is not taken into consideration. Besides, the methods

concerned in this research are empirical scheduling rules such as FCFS rule and its variants. In

Verstichel et al. (2014), a generalized lock scheduling problem is studied, which is decomposed

into lockage operation scheduling, chamber assignment, and ship placement subproblems. A mixed

integer linear programming model is proposed for the generalized lock scheduling problem, which

is proved capable of solving small-scale lock scheduling problemsto optimality by Gurobi. To speed

up the optimizing procedure, a logic-based Bender’s decomposition method is proposed to solve

the same generalized lock scheduling problem (Verstichel et al., 2015). Though the exact methods

presented in Verstichel et al. (2014, 2015) can achieve optimal results for the lock scheduling

problem, the computation time becomes prohibitively large when dealing with large-scale problems.

Regarding this point, stochastic metaheuristic algorithms are proposed in Verstichel et al. (2011),

which cannot provide any insight on the quality of the solutions. Some other research focuses on

the two lock co-scheduling system at the Three Gorges, which is composed of a lock with two

single-direction parallel chambers upstream and another lock with three double-direction parallel

chambers downstream. Different co-scheduling algorithms such as hybrid-simulated annealing

C

2019 The Authors.

International Transactionsin Operational Research C

2019 International Federation ofOperational Research Societies