One of the most important issues in port connectivity refers to the availability of accessible waterways and their traffic management. This puts a lot of pressure especially into capacity restricted transport corridors, where their inefficient use may not only result in a loss of the port competitiveness but also in an increase of the volume of ship emissions polluting the environment. In this context, the Waterway Ship Scheduling Problem is proposed; its goal is to schedule incoming and outgoing ships through different waterways for accessing or leaving the port in such a way that the ships’ waiting time is minimized. This objective allows, on the one hand, to avoid bottlenecks or congestions through scheduling the waterway traffic, and on the other hand, reduce vessel emissions while they are waiting at the anchorage either for entering or leaving. A mathematical model and heuristics are proposed. Real scenarios based on the Yangtze Delta (Shanghai) are tackled for assessing the performance of the heuristic and the improvement upon real-world terminal operations.
The maritime traffic growth forces port operators to efficiently reduce the ships’ waiting time when accessing their infrastructures if they want to increase or maintain their market share (Verstichel et al., 2011), reduce ship emissions (see Du et al., 2011, 2015) that contribute to increase greenhouse gases and harmful pollutants, and upgrade the port position in the port hierarchy through enhancing the port accessibility (Caldeirinha and Felício, 2014). In this regard, as indicated by Notteboom (2006), 93.6% of the delayed schedules are attributable to port access and terminal operations. This characteristic becomes even more relevant at some container terminals like in the port of Shanghai, where – according to practitioners – there is a multitude of ships daily requiring to pass through the Yangtze Delta waterways. Therefore, since the waterways play an important role at some maritime container terminals (Notteboom, 2008), it is sought to efficiently use them in order to avoid bottlenecks or congestions that may be translated into a loss of competitiveness. Moreover, the use of inland waterways as a transportation mode at container terminals is becoming even more relevant when we consider its increasing integration with other transport modes within multi-mode freight network schemes (Lowe, 2005, UNESCAP1 ). This close intermodality pursues to cope with the spatial or logistic restrictions that appear at some container terminals and it adds to the issues to be dealt with in port connectivity in the globalized economy.
From a green-logistics standpoint, on the one side, terminal operators are interested in reducing ship emissions while maintaining the quality of the service and, on the other side, shipping companies require smooth services to avoid unnecessary waiting times that cause a negative economic and environmental impact related to fuel consumption and route timing. Some works in the specialized literature have studied the relationship between the ships’ waiting time and their emissions. Du et al. (2011) indicate that the waiting time of the ships has an important influence on the volume emissions, where having flowing operations can help shipping companies to reduce emissions as well as help ports to have control over that. In the same line the work by Kontovas and Psaraftis (2011) investigates the reduction of emissions in maritime intermodal container networks, indicating that one of the main alternatives to reduce CO2 emissions is related to the reduction of the vessel waiting time. Song (2014) studies the ship emissions inventory (CO2, CH4, N2O, PM10, PM2,5, NOx, SOx, CO and HC) and their associated social cost in the Yangshan port at the south of Shanghai (China). In their work they include the waiting of the ship at the anchorage as well as at the berth as segments for evaluating the ship emissions. Their results show that although waiting at the berth has a greater impact than waiting at the anchorage, both activity modes result in sources of emissions. Fagerholt et al. (2010) in the context of shipping routes indicated that the more vessels’ waiting time the more the potential to reduce fuel consumption increases; this highlights the importance that waiting times have on consumption and emissions. Therefore, improving the waterway access operations by avoiding unnecessary waiting time at their entrance may lead not only to operational and social cost savings but also to an enhancement of the level of environmental quality of service through minimizing emissions.
In maritime shipping delayed schedules attributable to port access affect terminal productivity especially at some highcongested terminals, that are largely influenced by port access operations related to waterways. To be generic, a waterway can be defined as a capacity restricted transport corridor filled with water, e.g., a passage within inland rivers, lakes or bays which are navigable. A typical waterway consists of navigable waters, navigational aids and water conditions. Often natural as well as artificial waterways may be referred to as capacity restricted transport corridors, depending on their specific characteristics. They have to meet several conditions so as to serve the ships. First of all, an eligible waterway should provide sufficient depth. Secondly, the width of the waterway is also a crucial criterion. Usually, a waterway is two-directional and its width should exceed the sum of the breadth of the two navigating ships at the opposite direction with additional abundant width for the sake of safety, but occasionally it just refers to the isolated passing of individual vessels.
Only a few works focus their attention on waterway scheduling. Dai and Schonfeld (1998) discuss the estimation of waterway delays using metamodels and queuing theory. Taylor et al. (2005) develop a simulation-based software system for barge dispatching and boat assignment in an inland waterway. Some other works are more related to the use of locks. Smith et al. (2009) analyse the Upper Mississippi River waterway. This is a major inland waterway that includes 29 locks. They present a discrete simulation model as a suitable procedure for improving the practice prevailing first-come firstserved strategy used. Smith et al. (2011) propose complex decision rules based on a heuristic scheduler and a mathematical integer problem for improving the performance of the locks. Verstichel et al. (2014) study the positioning of the ships into lock chambers; they present a mathematical formulation and a solution approach for solving it. Other works focus their attention on the traffic planning on canals. Günther et al. (2010, 2011) deal with the bidirectional ship traffic on the Kiel Canal. They consider the canal as an alternating collection of canal segments and sidings. They present a mathematical formulation for designing the liner route and shipping networks. The aim of their model is to minimize the total passage time of ships, where this time includes the lock and siding waiting times. Yang et al. (2014) present an integer programming model to optimize the container liner network on the Yangtze River. They consider the Yangtze constrained only to a single water channel rather than several alternatives and all ports queue alongside the waterway. Their approach aims to reduce the transportation costs, that are the operation and fuel costs of the selected route. They consider the same operation times in each port. Ulusçu et al. (2009) study the traffic along the Istanbul Strait and develop an algorithm for scheduling the incoming ships for the specific considerations of the strait.
Despite the fact that in the related literature some works address one or the other waterway scheduling problem, the proposed approaches are restricted to the specifications of the studied waterways or designing the routes for visiting terminals along them. In this regard, in this work one of our goals is to present a more general approach for addressing the scheduling of the traffic along the waterways. Moreover, this concept also allows us to address the specific logistic scenario that takes place at the entering waterways of the Shanghai Port (China).2 An entrance waterway is one kind of waterway that connects a sea or inland river main waterway and the harbour water. It is widely acknowledged that one of the criteria to judge a port is its connectivity and it may be operationalized in a simplified way by means of its water depth. However, if one port does not have an entrance waterway with good depth and width condition, ships with large draft still cannot enter no matter how deep the berth-side is. That is why an entrance waterway is of great importance regarding connectivity. For example, the Yangtze Estuary Deep-water waterway as a main entrance of Shanghai port went through three complex and large-scale regulatory projects. Its original depth was 7 m (1998) which seriously restricted the development of the Shanghai shipping industry. Finally it reached a depth of 12.5 m (2010) which permits the passing of the fifth and the sixth generation of maritime container ships.
The previous discussions clearly draw the economical, operational, and environmental importance that scheduling ships along waterways has. This leads to the need of mathematical models and solution approaches for appropriately addressing this issue. With this goal in mind, the main contributions of this paper are:
– Propose the Waterway Ship Scheduling Problem (WSSP) in order to address the ship scheduling along waterways. This problem is modelled as Mixed Integer Linear Program (MILP) and addressed considering the real-situation taking place at the Yangtze Estuary, Shanghai. In this regard, according to a survey conducted with the Shanghai International Port Group (SIPG), there is a large number of ships applying to pass the waterway per day and a great proportion of them fails to apply for the appropriate time of passing, because of not considering the geographic constraints of the Yangtze Estuary such as draft, breadth and night navigation.
– As Kontovas and Psaraftis (2011) indicate there are common policies used in terminals for reducing the ships’ waiting time and, consequently, emissions. Therefore, we develop and assess heuristics based on some common policies used at container terminals. This allows to evaluate the operational and environmental improvement by means of the reduction of the waiting time that can be obtained through the use of more sophisticated techniques such as the simulated annealing (SA) proposed in this work. In this sense, the proposed SA approaches allow to reduce the unnecessary emissions generated during the ships’ waiting time. In addition, the comparison with the model implemented in CPLEX and the heuristics shows that the SA is able to provide high-quality schedules which justify its use as part of a decision support system (DSS). In this real application, the DSS would be used for verifying all the ships and modify their time assignments.
– Provide a benchmark suite based on data provided by the container terminal of Waigaoqiao (Shanghai). On the other hand, since this problem can be translated to other scenarios, the benchmark suite includes other problem instances of different dimensions.
The remainder of this paper is organized as follows. Section 2 introduces specific characteristics of the Yangtze Estuary. The mathematical formulation of the Waterway Ship Scheduling Problem is presented in Section 3. In Section 4, the solution approaches proposed for solving this problem are depicted. Afterwards, Section 5 analyses the performance of our proposal in realistic scenarios. Finally, Section 6 provides our main conclusions extracted from the work and suggests several directions for further research.