The current practice of the shipping company deploys a feeder network where all routes depart from the European port. It studies the impact of using a hub-and-spoke network that is composed of mother and daughter routes with the possibility of splitting pickups and deliveries. Computational studies carried out on problem instances based on realistic data show that significant cost reductions can in several cases be obtained by including the proposed network structure.
This paper presents a case study for a liner shipping company that transports goods between Norwegian ports and the European continental port at Rotterdam. The shipping company serves the major ports of Norway and accommodates different container types (from standard containers of a twenty-foot equivalent unit (TEU) and forty-foot equivalent unit to specialized containers). There is a given weekly demand to and from each Norwegian port and the continental port. Since the demand among Norwegian ports is so small, it can be considered as negligible.
Variant 1: Mother routes only
In the first network structure, which corresponds to the current practice of the case company, any route originates from the continental port and serves all or a subset of ports located alongside the Norwegian coastline. Such a route is referred to as the mother route and is sailed by so-called mother vessels. To maintain a weekly service frequency, each port has to be visited once a week. Thus, it is required that the number of mother vessels deployed on a mother route is equal to the number of weeks to complete that route (rounded up to the nearest integer). For instance, if a cycle takes ten days, one vessel cannot ensure a weekly service. Therefore, two vessels have to be deployed where the cycles of the first and second vessels start on days 1 and 8, respectively.
The shipping company can deploy a heterogeneous fleet of mother vessels, where the capacity of each vessel needs to be sufficiently high to accommodate the cargoes to be carried along its route. Since the flow of cargoes to be transported from the Norwegian ports to the continental port is higher than the reverse flow, we assume that a mother vessel starts by serving the northernmost part of its route and visits the other ports along its southbound journey. This results in a better average transit time per unit of cargo compared to adapting port visits during the northbound journey.
Nonetheless, we should precise that an even better average transit time can be obtained by considering both northbound and southbound journey visits for Norwegian ports. With this generalization, the resulting mother routes are slightly longer than the one with the southbound journeys only. The operational cost in such a system would become higher because of the additional sailing and port costs for the ports visited during the northbound journey.
Variant 2: Hub-and-spoke system with combined mother and daughter routes
Variant 2a: Only simple cycles as daughter routes
In Variant 2a, a daughter route can only be a simple cycle, where each port is visited one time, and the route starts and ends at the transshipment port. The total duration of each route must not exceed one week so that a weekly service is ensured for all visited ports.
Variant 2b: Daughter routes can be both simple cycles and butterfly routes
Label setting algorithm for route generation
The presented mathematical models for the different network structures are based on sets of valid mother and daughter routes. These sets can be pre-generated using the shortest path label setting algorithm, which is widely used in the literature for similar problems and is based on a dynamic programming approach to restricting the generated routes to only feasible and non-dominated routes.
Generation of mother and daughter routes
The label setting algorithm operates in sequential stages, where each stage corresponds to a partial route. A decision is made for each stage whether it is feasible and non-dominated or not. The starting port of all mother routes is the continental port. The next candidates correspond to going from the starting port to any of the Norwegian ports. Then, each such candidate is further extended to include only south-bound port visits since only south-bound journeys are allowed, as previously explained.
Furthermore, any candidate can be extended to go back to the continental main port, and a complete route is obtained (provided it respects the restriction regarding the maximum capacity among available mother vessels). The extension process is repeated in a similar way until no further port can be visited. By doing so, feasible mother routes are easily generated because only south-bound journeys are permitted and there is no time restriction on mother routes.
At this point, it is worth mentioning that to compute the total cost of mother route r required by , the route completion time is first computed according to sailing time and handled cargo on r. Then, the number of mother vessels that are deployed on r is set to the number of weeks the completion of the route takes. However, this information is not needed for and because the number of mother vessels is decided by the model.
The daughter routes are generated in a similar way. A daughter route can start at any Norwegian port and can be extended to any other Norwegian port. The starting port represents the transshipment port where mother and daughter routes are connected to deliver and pick up cargoes. In contrast to a mother route, a daughter route corresponds to one daughter vessel and, consequently, has both time and capacity restrictions. This means that the daughter routes have to be completed within one week, and the number of containers on board a daughter’s vessel cannot exceed its capacity at any time.
Second, the bunker costs of both partial routes are computed. Hence, when a partial route has a lower;
(i) a maximum number of containers on board and
(ii) bunker cost, it dominates the other partial route.
Route generation-based heuristic
Even though a label setting algorithm is used for route generation, the number of routes increases exponentially as the number of ports increases. Therefore, it can be required to reduce the set of routes given as input to the mathematical model in order to solve larger instances.
It is done by exploiting the following geographical characteristic of our case study problem, where the ports are located along a coastline (more or less along a vertical line). Most likely, the most cost-efficient routes have ports that are close to each other and go only in one direction rather than ones that “zig-zag” up and down along the coastline. Hence, whether it is for mother or daughter routes, a partial route is extended up to only the e–th nearest ports in the south-bound direction from the current port or returns to the initial port. Here, e is an input parameter to the procedure, which controls the size of the considered daughter routes and, thus, the number of routes generated in the process.
Also, an additional step is added for the daughter route generation so that a complete route is duplicated as many times as the number of visited ports, where each duplication has a different transshipment port among the visited ports.
Did you subscribe to our daily newsletter?
It’s Free! Click here to Subscribe!