Abstract

A common challenge faced by liner operators in practice is to effectively allocate empty containers now in a way that minimizes the expectation of costs and reduces inefficiencies in the future with uncertainty. To incorporate uncertainties in the operational model, we formulate a two-stage stochastic programming model for the stochastic empty container repositioning (ECR) problem. This paper proposes a separable piecewise linear learning algorithm (SPELL) to approximate the expected cost function. The core of SPELL involves learning steps that provide information for updating the expected cost function adaptively through a sequence of piecewise linear separable approximations. Moreover, SPELL can utilize the network structure of the ECR problem and does not require any information about the distribution of the uncertain parameters. For the two-stage stochastic programs, we prove the convergence of SPELL. Computational results show that SPELL performs well in terms of operating costs. When the scale of the problem is very large and the dimensionality of the problem is increased, SPELL continues to provide consistent performance very efficiently and exhibits excellent convergence performance.

1. Introduction

The acceleration of global economic growth and the expansion of global trade networks have led to an increasing demand for cargo transportation. The explosion of global trade has also been accompanied by the increasing use of containers as an economic and safe mode of transportation. A container that is fully loaded with cargoes from the shipper is transported to destination ports and delivered to the consignee and unloaded. Then, the container is emptied and stored at the destination port until it is booked for another consignment. However, when there is an imbalance in the number of export and import containers, some ports have a surplus of empty containers while others have a deficit. Under this situation, empty containers must be repositioned from surplus ports to deficit ports.

The trans-Pacific trade lane is taken as an example: according to UNCTAD [1], the annual container flow from Asia to North America (i.e., the eastbound) increased to 17.8 million twenty-foot equivalent units (TEUs), while that in the opposite westbound directions increased to 8.6 million TEUs, which generated the imbalance of container flow for 9.2 million TEUs in 2017. A similar situation has been reported for the container flows between Asia and Europe. Song [2] point out that the repositioning cost for empty containers is 27% of the global fleet running cost, and 20% of total container movements by ocean transportation are empty. Thus, empty container repositioning is a crucial issue for practitioners, and liner shipping companies must find an effective way to reposition their empty containers.

1.1. Motivation

Several planning models have been developed for liner companies to improve the efficiency of ECR [3–9]. Some research has examined deterministic situations [10, 11]. However, in the highly competitive shipping industry, operational-level planning requires decision-making with uncertainties. Although the shipping company knows the exact demand according to the long-term contracts and makes delivery schedule based on demand information, liner operators face many uncertainties, such as port congestion, weather, and supply and demand fluctuation. These uncertainties might need liner operators to change the planned decision adaptively. Consequently, taking into account the uncertain nature of parameters in the ECR problem has attracted considerable attention from academics and practitioners.

This study is primarily motivated to solve the ECR problem faced by a major Chinese shipping company that we work with. Interview with the company reveals that, among the various uncertainties, the uncertainty of future demands, remaining vessel’s capacities, and supply are the most influential. Transportation and repositioning decisions in the ECR problem are considered wait-and-see decisions in practice. Given the dynamically changing environmental information in the shipping industry, the ECR decisions must be adjusted whenever new information is updated. Hence, we develop a two-stage stochastic model in the rolling horizon policy to deal with the dynamically changing demands, remaining vessel’s capacities, and supply in this study.

A well-known approach for dynamic decision-making is stochastic programming in which the uncertainty is characterized by a known probability distribution of parameters [7, 12, 13]. However, data forecasting accuracy, such as demand forecasting with historical data, is usually low and data estimation is difficult in practice. It is impossible to achieve complete knowledge about the distributions of uncertainties with historical data. Moreover, the stochastic ECR problem with a large number of scenarios is computationally intractable [7]. To overcome this limitation, we use a time-space network to illustrate the stochastic ECR problem and propose a separable piecewise linear learning algorithm (SPELL) to solve the problem. SPELL does not require any information about the distribution of uncertain parameters, and the learning steps in SPELL can provide information for updating the expected cost function adaptively by using sample information on the objective function itself. Furthermore, since our ECR problem has a network structure (time-space network), when we use a separable approximation and the approximation function is piecewise, we can solve the problem as a pure network flow problem, which is a well-known polynomial solvable problem. Therefore, the large-scale stochastic ECR problem can be efficiently solved, and we show the efficiency of our approach numerically in this study.

1.2. Literature Review

The ECR problem has attracted considerable attention in academia [14, 15]. Generally, these studies can be categorized into the strategic, tactical, and operational levels. At the strategic level, the decisions include price strategy and competition and encroachment and canvassing strategy [16, 17]. At the tactical level, most decisions concern the service network design problem [18–21], ship deployment, and fleet sizing [9, 11]. Threshold policies are also studied at this level [22, 23]. At the operational level, a highly dynamic environment is characterized, and most decisions focus on the transportation of empty containers among terminals/depots [5, 7]. This study aims to provide operational-level decisions for shipping companies.

Several researchers have considered the uncertain nature of parameters in ECR problems. For instance, Crainic et al. [3] introduced two dynamic formulations for the allocation of empty containers in single- and multicommodity cases given that both demand and supply are stochastic in nature. Cheung and Chen [24] proposed a two-stage stochastic network formulation of the ECR problem under uncertainties. This two-stage modelling successfully combines the deterministic and uncertain information of the problem and requires the approximation functions to be strongly convex. Erera et al. [12] and Shan et al. [21] developed a robust optimization framework for dynamic ECR problems that are modelled by using time-space networks. This robust approach modelled the uncertain supply and demand by using intervals regarding the nominal forecast value, and the repositioning plan can be adjusted under a set of recovery sections. This approach is consistent with the current repositioning operation and can be easily applied. Francesco et al. [13] proposed a stochastic programming model with uncertain data for ECR and solved the model using multiscenario optimization. However, the multiscenario model built by Francesco et al. [13] is subject to a small number of scenarios model. Long et al. [7] formulated a two-stage stochastic programming model for ECR and solved the program with the sample average approximation (SAA). They utilized the scenario aggregation to handle an extremely large number of scenarios. However, in these study, the distribution of uncertain parameters is assumed to be estimated in advance. In this study, we will propose a separable piecewise linear learning algorithm which does not require any information about the distribution of uncertain parameters in advance, and this algorithm can solve large-scale ECR problems efficiently.

To incorporate uncertain parameters, we model the problem as a two-stage stochastic program. Studies have proposed various approximation schemes for two-stage stochastic programs that can be grouped into four categories: scenario methods that use fixed samples to approximate the underlying probability space [7, 25, 26]; stochastic gradient techniques that update the solutions by using stochastic subgradients as directions [27]; primal and dual decomposition methods [28, 29]; separable approximation methods [30–37] that replace the expected recourse function with separable approximation functions. The scenario method is very efficient, but the distribution of uncertain parameters is assumed to be estimated in advance, and its solution might not always converge to the optimal one. Meanwhile, the stochastic gradient technique has been proven to be convergent by projection [38], and the drawback is that the algorithm is inefficient. Given these characteristics, we combine the stochastic subgradient technique with the separable approximation method and propose the SPELL algorithm. SPELL does not need to know the distribution of the uncertain parameters in advance. Furthermore, SPELL can utilize the network structure of the ECR problem and solve the problem as a pure network flow problem very efficiently. To our knowledge, for the maritime empty container repositioning problem, no existing study utilized the network structure of the ECR problem, and applied the separable piecewise linear learning algorithm to solve the large-scale stochastic ECR problem efficiently. This study is to fill in this gap for maritime transportation.

Among the above methods, the methods by Godfrey and Powell [32] and Cheung and Powell [30] are the most relevant to our study. Godfrey and Powell [32] proposed the adaptive piecewise concave approximation (CAVE) algorithm, which demonstrated exceptionally good experimental performance, but they did not provide any provable convergent results. To achieve convergence to optimal solutions, Cheung and Powell [30] proposed a convergent approximation algorithm (SHAPE), but it differs from our study in two main aspects. First, SHAPE uses a sequence of strongly convex approximation functions, while SPELL uses separable piecewise linear approximation functions. Since the ECR problem has a network structure, strong convexity requires a nonlinear term in approximation functions that might destroy the pure network structure and demands additional computational effort. Second, SHAPE may be stuck in a corner solution when the second stage is stochastic linear programs without the projection step. By contrast, we introduce projection steps [36, 37] to help SPELL to jump out from a local optimum and achieve a global optimum.

1.3. Contribution

The main aim of this study is to solve the real-time maritime ECR problem with uncertainties efficiently. In summary, contributions of this paper are fourfold. First, we propose a two-stage stochastic program model for the ECR problem with uncertainties. Since this model takes into account most port operational requirements and the actual shipping service schedule, it is very easily applied in the shipping industry. The stochastic model which considers some uncertain parameters may provide more robust decisions, and therefore the operational cost of ECR can be further reduced. Second, we propose the SPELL algorithm with limited information on distribution of uncertain parameters, and the learning steps in SPELL can provide information for updating the expected cost function adaptively through a sequence of piecewise linear separable approximation. Moreover, SPELL can utilize the network structure of the ECR problem and solve the large-scale problem very efficiently. Third, we theoretically prove the convergence of SPELL for two-stage stochastic programs. Finally, we conduct a performance analysis through the practical-scaled numerical experiments. The computation results reveal the efficiency of the proposed algorithm, which does not need to know the distribution of the uncertain parameters in advance.

The rest of this paper is organized as follows. Section 2 discusses the problem definition and mathematical models. Section 3 presents the SPELL algorithm for the two-stage stochastic ECR problem. Section 4 presents the performance analysis of SPELL through the computational experiments. Section 5 concludes the paper and presents directions for future research.

2. Problem Formulation

Our problem focuses on the operational level decisions of the ECR problem. Due to the global trade imbalance, the empty containers in surplus regions like North America have to be repositioned to deficit regions like Asia. One of the trans-Pacific shipping routes as shown in Figure 1 is taken as an example. The itinerary of this route forms a loop. We can arbitrarily deem that this itinerary starts and ends at Qingdao. Let represent the index of ports on a round trip for the route service . Then, we can define Qingdao as Port 1, Ningbo as Port 2, Shanghai as Port 3, Busan as Port 4, New York as Port 5, Norfolk as Port 6, and Savannah as Port 7. Shippers usually pick up the required empty containers from the port (), consolidate their cargoes into these containers, and then take the laden containers back to the port to wait for vessels. These laden containers are then loaded on a vessel and will be transported to the cargo receiver for unpacking at the destination port (). After unpacking, the empty container can either be moved/stored at the port () for future reuse or be repositioned to another port () to meet the shippers’ demand. However, it usually takes a long time to deliver the across-region containers. For instance, the transit day from New York to the first arrived port in Asia (Qingdao) is 42 days. Thus, shipping companies should place their orders about 6 weeks in advance to satisfy the demand in Asia.

Figure 1 

A transpacific shipping service route operated by the shipping liner COSCO. Source: COSCO [39].

In practice, whether the demand orders in the deficit region could be satisfied mainly depends on the empty container inventory stored at ports in the surplus region as well as the remaining capacities of vessels. Moreover, due to the long lead time of empty containers, liner operators usually make ordering decisions based on forecasting with historical data. However, it is usually difficult to obtain accurate forecasting for more than two or three weeks. Therefore, liner operators will be hard pressed to make operational level decisions for ECR, and inefficient ordering decisions might be made owing to low forecasting accuracy. To overcome this limitation, we propose a stochastic programming model that considers three major sources of randomness in the ECR problem, namely, the demands at ports, the supplies at ports, and the remaining capacities of vessels for empty containers. This model does not need to know the distribution of the uncertain parameters in advance. Other uncertain factors, such as the transportation time between two ports, are not considered.

Without loss of generality, we make several assumptions in our model. First, we assume that the shipping service schedule is fixed and given in the planning horizon. This assumption is valid given that the planning horizon of our model is short (several weeks) and that the service schedule is not changing frequently. Second, after laden containers are unloaded from vessels at their destination ports, they become empty and can be reused or repositioned to other ports. Third, when the demands cannot be satisfied by the empty container inventory at surplus ports, we have to lease, buy, or temporarily use containers provided by other shipping companies, all of which involve a penalty cost [7]. Note that we do not make decisions on laden container transportation in this study, and the same assumption is common in the literature (e.g., [7, 40]). Unlike empty containers, laden containers have fixed origins and destinations. Furthermore, the laden container transportation and ECR problems are usually considered separately in the shipping industry. Therefore, we do not treat the number of laden containers to be shipped from one port to another port as a decision variable; instead, we assume that this number is given. Our model makes ECR decisions after the laden container transportation is planned.

Our problem focuses on short-term decision-making while considering the influence of these decisions in the planning horizon. To illustrate the stochastic ECR problem, let us consider a time-space network of the ECR problem as in Figure 2. This network has been divided into two parts: in stage 1, all parameters are deterministic and known, while some parameters in stage 2 are unknown when a decision is made in stage 1. The repositioning decision made in stage 1 determines the initial state when solving the problem in stage 2. S is a cross-region service. In this study, we consider each region separately. ECR decisions related to ports in the target region are made, while the coordination with other regions is not considered. We only consider the information in the target region when decisions on the number of empty containers into/out of the target region are made. To make the two-stage stochastic ECR model easy to understand, we first introduce the following deterministic ECR model.

Figure 2 

Time-space network for ECR.

2.1. Deterministic ECR Model

We first assume that all parameters in the planning horizon are known and then formulate a deterministic ECR problem. Then, we incorporate uncertain parameters into our model and propose a two-stage stochastic ECR model for the stochastic ECR problem. Table 1 presents the notations.

We consider several cost elements for the ECR problem, including empty container lifting-on cost , empty container lifting-off cost , inventory costs of empty container , empty container transportation cost , and empty container penalty cost , which can be formulated as follows:

Afterward, we formulate the deterministic ECR problem () as

Constraint (3) denotes the service flow constraint that considers the balance of container flows for each service route. Constraint (4) is the port flow constraint that guarantees the balance of container flows at each port for each time. Constraint (5) is the capacity constraint. Constraint (6) guarantees that the number of empty containers unloaded from a vessel is less than the number of empty containers on this vessel. Constraint (7) guarantees that all the decision variables should be nonnegative.

2.2. Two-Stage Stochastic ECR Model

To incorporate uncertain information, we develop a two-stage stochastic ECR problem. In stage 1, all information is known and all parameters are deterministic, while in stage 2, some parameters (supply , demand , and remaining capacities of vessels, ) are uncertain when decisions are made in stage 1 [7]. At the beginning of stage 1 (we refer the first week as stage 1 in this study), liner operators make repositioning decisions in the target region and across regions. The decisions will be made again when new information is updated later. Let denote a realization of the unknown parameters when decisions at stage 1 are made, but these parameters are known when the second stage decisions are made.

We then develop the following two-stage stochastic model ():where given a realization and a set of in-bound flows to stage 2, the optimal value of the stage 2 problem is given by

In the above model, equations (8) to (11) define the stage 1 problem, and the objective function of stage 1 is to minimize the total operational cost. is the operational cost of stage 1, and is the expected operational cost of stage 2. Equations (12) to (15) define the stage 2 problem. The decision variables and denote the decision variables of the stages 1 and 2 problems, respectively, while and denote the stages 1 and 2 vectors of cost coefficients, respectively. In addition, denote the constraint matrices for stage 1, while denote the uncertain parameters for stage 2 constraint metrics. denotes the container state of stage 1. It is the empty container inventory at each port and at each vessel at the end of stage 1. denotes the vector of the initial empty container state of stage 2 for a given . Decisions in the stage 1 are communicated to the stage 2 through the state variable . Constraints (9) and (11)fd15 include the constraints of the deterministic ECR problem (), the ship capacity constraint, the service route flow balance constraint, and the port flow balance constraint. Constraint (10) sets the empty container state at the end of stage 1 and shows the inventory at each port and vessel at the end of stage 1. Constraint (14) sets the initial container state of stage 2. For a given , the initial container state in stage 2 must be equal to the ending container state in stage 1.

3. Solving Methodology

The main challenge for solving two-stage stochastic programs in most practical cases is that the expected recourse function,, is excessively complex due to uncertainty. In this section, a new separable piecewise learning algorithm (SPELL) is proposed to approximate the expected cost function of the ECR problem.

Let denote the approximation function. Essentially, SPELL is a combination of the stochastic subgradient technique [27] and the separable approximation method [24]. The stochastic subgradient technique updates the solutions of problem () by using stochastic subgradients as directions [27]. These subgradients can be obtained from the scenario at each iteration, and the approximate function can be updated successively as follows:where is a smoothed estimate of the gradient of the expected cost function at iteration . For this method, convergence is achieved by projection [38] although the disadvantage is that the method is not efficient. Meanwhile, the separable approximation method replaces the expected recourse function with separable approximation functions as follows [24]:

Note that our ECR problem has a network structure. If the separable function is linear or piecewise linear, and the expected recourse function in equation (8) can be replaced with in equation (17), then the stochastic ECR problem can be solved as a pure network flow problem, which is a well-known polynomial solvable problem.

According to their advantage and disadvantage mentioned above, we combine equations (8), (16), and (17) to form an approximation of the expected operational cost function at iteration as follows:

The basic idea is that we would like to approximate the expected cost function of the stochastic ECR problem () via an initial convex approximation with an iteratively updated linear correction term . The information from the linear correction term generated at iteration can improve the initial approximation . Note that we use a convex initial approximation function , whereas the SHAPE algorithm by Cheung and Powell [30] uses strongly convex approximation functions. Although the strong convexity can guarantee the convergence of SHAPE, the strong convexity requires a nonlinear term in the approximation function that may destroy the pure network flow problem structure of our ECR problem and demands more computational effort. But, when the second stage is stochastic linear programs, the SHAPE may be stuck in a corner solution. In order to jump out of the local optimum, the projection step that implement the stochastic subgradient method is introduced in SPELL. Our computational results shows the effectiveness and efficiency of the projection step, and our analytical results in the appendix also prove the convergence of SPELL.

In this study, the stochastic subgradient is not calculated in the usual manner. As shown later in Proposition 1, can learn the information from the previous iterations and update itself adaptively. In contrast, our method uses the following approximation form:where is a gradient of at iteration , is stochastic subgradient of at , that is, , and is the step size and is measurable.

Then, is updated as

The advantage of updating is that the stochastic subgradients used in the previous iterations, namely, , can be retained. Thus, the objective function in iteration involves a weighted average of stochastic subgradient in previous iterations. We call this a learning step because in each iteration, we are exploring the approximation function at previous randomly sampled scenarios. We discuss the learning step in the following proposition.

Proposition 1. The approximation function at iteration can be written as , where is a weight average of the stochastic subgradient in previous (k − 1) iterations and is piecewise linear.

Proof. Based on equation (18), the approximation of the expected cost function at iteration is the initial approximation plus a linear term as follows:where is the cumulative change of up to iteration . Taking the first derivation of in equation (21), we haveBased on equations (20) and (22), we can obtain as follows: Thus, we can obtain the relationship between and as follows:From equation (24), we can conclude that is a linear combination of and is piecewise linear. Thus, can be updated by the information learnt from the previous samples.
The basic idea of SPELL is that at iteration , we compare the slopes of gradient with the stochastic subgradient . Afterward, we use the difference of these two slopes to update linearly. When the solution is stuck in a corner solution, we implement the projection step to jump out of the local optimum. Let be the orthogonal projection onto [38]. We apply the algorithm in Figure 3 to find a sequence of solutions .
Generally, SPELL maintains two-level loops as shown in Figure 3. In the first-level loop, there are a series of update processes, in which the approximation function can be updated iteratively. However, if the solution is stuck in a corner solution and the local optimum detector is triggered, then SPELL will enter the second-level loop, which contains a series of projection steps. In the first update process, we construct an initial convex approximation function and obtain the initial solution We then sample a realization of random parameters (supply , demand , and remaining capacity of vessels ) solve the corresponding deterministic problem, and calculate the stochastic subgradient of the expected cost function, Subsequently, the approximation function can be updated by learning the information from the difference between and , and we can obtain a new solution in Step 4. However, if the newly obtained solution has an exactly identical subgradient vector as a solution which means the newly obtained solution triggers the local optimum detector, then SPELL will enter in Step 6 and implement a series of projection steps in the second-level loop to jump out of the local optimum. Without these projection steps, if and , the SPELL algorithm proceeds directly to Step 3, and the approximation function will be not updated in Step 3. Thus, the SPELL algorithm might become stuck in the corner solution. On the other hand, if is different from , SPELL will not enter into the projection step and proceed directly to the next update process, and the entire update process is repeated. Note that, when SPELL triggers the local optimum detector and enters into the projection step, it might need several iterations to jump out. Eventually, the algorithm will be terminated when the total absolute change in over a certain number of iteration is low (e.g.,). In the above SPELL algorithm, represents the iteration number, and it updates when SPELL starts a new iteration to obtain a new solution (in Steps 4 and 6); represents the number of SPELL crossing the projection steps, and it updates when SPELL satisfies the condition in Step 5; represents the number of the first iteration of the update process, and it updates when SPELL enters a new update process in Step 3.
Differences between Shape and Spell. The most remarkable difference between SHAPE and SPELL is that SHAPE uses strongly convex approximation functions, whereas SPELL uses separable piecewise linear convex approximation functions. Strong convexity requires a nonlinear term in the approximation function that may destroy the pure network structure of the ECR problem and demand additional computational effort. To overcome the limitation of the SHAPE algorithm, the SPELL algorithm introduces the projection step to construct approximation functions, which are not strictly convex. As shown in the numerical experiment later, without the projection step, the SPELL algorithm might also become stuck in the corner solution for the ECR problem. Furthermore, our analytical results in the appendix prove the convergence of SPELL.
Since SPELL adjusts the approximation by a linear term at each iteration, the following property is obtained.

Figure 3 

The flowchart of the SPELL algorithm.

Proposition 2. For any two points and , if then for any

The proposition holds because the approximation functions are updated by linear terms.

As shown in Figure 3, if the newly obtained solution in Step 4 has the exactly identical subgradient vector as solution , then according to Proposition 2, we can conclude that there will be no update in in the next iteration. Then, SPELL may be stuck into the corner solutions. Therefore, we need the projection step in Step 6 to help SPELL jump out from a local optimum.

Proposition 3. For any two iterations in the update process, say and , for any .

The proposition holds because the approximation functions are not updated when SPELL performs the projection steps. Thus, if the newly obtained solution produced by Step 6 can pass the locally optimum detector, then it can help SPELL to jump out from a local optimum and proceed to the next update process.

4. Computational Experiment

We conduct extensive computational experiments based on a real-world shipping service network to evaluate the performance of SPELL. All computational experiments are implemented on a computer with an Intel (R) Core (TM) i7-7567 CPU at 3.5 GHz and 16 GB of RAM with Java and IBM ILOG CPLEX 12.6. We initially introduce the practical ECR problem and present the effectiveness and efficiency performance of SPELL. Afterward, we demonstrate the performance of SPELL under various distributions. Finally, we present the convergence performance of SPELL.

4.1. Test Case

To evaluate the performance of SPELL, we generated three different scale test instances with various numbers of ports and service routes. In this study, we selected the real-world shipping service routes operated by the shipping liner COSCO [39] to generate three different scale problem instances. Table 2 lists the network parameters for three problem instances.

In Table 2, instance P1 is a small-scale instance that consists of five intra-Asia service routes (AK12, AK2, AK47, AK49, and AK5) and nine ports. Instance P2 is a medium-scale network with 30 ports, 17 intra-Asia service routes, and two types of containers (20 and 40 ft standard containers). Instance P3 is a large-scale network with all the 56 ports, 17 across-region service routes, 17 intra-Asia service routes, and four types of containers (20, 40, and 45 ft standard and 40 ft high cube containers). We define the first week as stage 1 and the second week to the end of the planning horizon as stage 2. At the beginning of stage 1, all information in stage 1 is known, whereas some parameters in stage 2 are unknown. When these parameters are identified at the beginning of stage 2, the liner operator optimizes the shipping decisions. We set half of the rotation time of the service route as the lead time. The rotation times of the 17 across-region services are shown in the parentheses under Table 2. To evaluate the performance of SPELL under different distributions of the uncertain parameters, we consider three kinds of distribution: normal, exponential, and uniform. In this study, the step size of our algorithm is set to .

To construct the initial piecewise linear function , we solve a deterministic ECR problem in which the uncertain parameters are replaced by the sample mean values. Then, we can obtain . For each , we can construct the initial approximation function bywhere is a positive parameter and . Note that is an integer in the ECR problem. We use here to illustrate the granularity of the initial function. For the projection, we calculate the following least-square problem:

4.2. Effectiveness and Efficiency Performance Analysis

For the stochastic ECR problem, obtaining optimal solutions is generally intractable. Therefore, it is impossible to compare the solution produced by a method with the optimal solution. One possible way is to develop some bounds on the optimal solution and then use these bounds to evaluate the quality of a solution. In this study, we use PB (posterior bound), a myopic algorithm, and the L-shaped algorithm [41] as benchmarks to test the effectiveness and efficiency of SPELL. To obtain PB, we need to solve a deterministic network flow problem with all realized parameters. Such a posterior optimization involves no uncertainty because decisions with anticipation of future demands are allowed. Therefore, the cost of PB is low and normally unreachable, and it is used as the lower bound [42]. The myopic algorithm simply solves a deterministic problem at the current stage while ignoring uncertainties in the second stage. Thus, we use the results produced by the myopic algorithm as the upper bound. For the L-shaped algorithm, it is very efficient, a group a linear programming problems with a series of cutting planes must be solved. And, we can use the results produced by the L-shaped algorithm to test the efficiency of SPELL. To evaluate the effect of the projection step, we also implement SPELL without the projection step, which is called SPELL-NON, in the following section.

In the experiment, 2000 samples have been run for each instance to obtain the sample means of PB. The solutions of the myopic algorithm, L-shaped algorithm, SHAPE, SPELL, and SPELL-NON can also be obtained. In this study, we select the initial functions with

The results on the total operational cost are listed in Table 3. Column 1 shows the problem instance. Columns 2 to 5 record the solutions obtained by PB, myopic, L-shaped, SPELL-NON, and SPELL. The experiment results demonstrate that SPELL can achieve near-optimal solutions, which are extremely close to the PB (within 0.11% gap from PB). The solutions of SPELL, SPELL-NON, and L-shaped algorithm are better than those of the myopic algorithm. For the small-scale instance, the operational cost obtained by SPELL is 2.67% lower than that of the myopic algorithm. For the large-scale instance, the operational cost obtained by SPELL is 7.57% lower than that of the myopic algorithm. Therefore, compared with the deterministic model, our stochastic model can reduce the operational cost of the ECR problem. Notably, the larger is the instance, the relative improvement of the stochastic model is more significant. Furthermore, SPELL slightly outperforms SPELL-NON because the projection steps in SPELL can help jumping out of local optimum. Hence, the projection step is effective in SPELL. In most practical-scaled stochastic ECR problems, the speed of calculation is one of the major concerns of practitioners, and thus we list the computation time for different algorithms in Table 4.

As shown in Table 4, SPELL is more efficient than the L-shaped algorithm because SPELL can utilize the network structure of the ECR problem while approximating the objective function. The larger is the scale of the instance, the more efficient SPELL is. The L-shaped algorithm is time consuming because 2000 samples are used in this experiment, which corresponds to a large number of cuts for the L-shaped algorithm. Compared with SPELL-NON, SPELL is time consuming because the projection step in SPELL is effective and the calculation of the projection requires more computation time.

4.3. Performance under Various Distributions

In this section, we aim to examine whether the distribution of the uncertain parameters (supply , demand , and remaining capacities of vessels, ) affects the performance of SPELL or not. Since the normal distribution has been implemented in Section 4.2, we consider two other distributions in this section: the exponential and uniform distributions. The results on the total operational cost for the exponential and uniform distributions are presented in Tables 5 and 6, respectively, and the computation time for the different algorithms is presented in Table 7.

As shown in Tables 5 and 6, the performance under exponential and uniform distributions is consistent with those of uniform distribution in Section 4.2. SPELL can achieve near-optimal solutions. According to Table 7, SPELL and SPELL-NON are also more efficient than the L-shaped algorithm. Moreover, the projection steps are effective because SPELL-NON requires more computation time than SPELL. Thus, the results are consistent with the fact that SPELL do not require any information on the distribution of the uncertain parameters.

4.4. Convergence Performance Analysis

From the perspective of liner operators in the shipping industry, one of the major concerns in solving the practical-scaled ECR problem is the rate of convergence. Thus, in this section, we will evaluate the convergence rate of SPELL. To measure the rate of convergence of different methods, we implement each algorithm for 40, 160, 640, 1200, and 4000 iterations and compare the solutions of algorithms side by side as the number of iterations increases. For our SPELL and myopic algorithms, the number of iterations refers to the number of samples used, whereas the number of iterations refers to the numbers of cuts for the L-shaped algorithm.

The results are summarized in Table 8. The figures in the table record the deviation from PB after a certain number of iterations. Table 8 also lists the computation time per iteration. We present the experimental results on the three-scale problem instances, which vary in the dimensionality of the recourse function.

As shown in Table 8, column 2 lists the methods used in the experiment. Columns 3 to 7 contain the percent deviation from the PB, and column 8 presents the computation time per iteration. The results demonstrate that SPELL can produce high-quality solutions rather quickly and achieve consistent performance under different problem instances. In particular, when the scale of the problem is very large and the dimensionality of the problem is increased, SPELL continues to provide consistent performance with a short computation time per iteration. This feature makes SPELL attractive for liner operators in solving the practical-scaled ECR problem. Compared with the L-shaped algorithm (bender decomposition-based algorithm), SPELL is more competitive for high-dimensional problems because separable approximations typically scale much more easily to the very high-dimensional problem. Accordingly, SPELL is a promising method for the stochastic ECR problem. Due to its simplicity and fast runtime, SPELL is an attractive candidate for problems where the computational cost for one experiment is high.

5. Conclusion

In order to incorporate uncertainties in the ECR problem, we build a two-stage stochastic model with uncertain demand, supply, and ship capacity, and this model could be easily applied to the shipping industry. To solve the model, we propose a separable piecewise linear learning algorithm which does not require any information about the distribution of uncertain parameters, and the learning steps can provide information for updating the expected cost function adaptively by using sample information on the objective function itself. Moreover, the proposed algorithm can utilize the network structure of the ECR problem and can solve the large-scale stochastic ECR problem very efficiently. To evaluate the performance of the algorithm, we solve three scale problems which are based on three real-world shipping service networks operated by the shipping company COSCO. Numerical experiments indicate that SPELL is efficient and effective. Moreover, the proposed method is found to be very competitive for high-dimensional ECR problems. In order to achieve a global optimum, a projection step that implements the stochastic subgradient method is performed to jump out from a local optimum, and the computational result shows the effectiveness of the projection step in SPELL. As the two-stage model lives with the assumption that we know the future at the end of the first stage, it is unable to handle sequential decisions. We may extend the two-stage problem to the multistage problem which does not require such an assumption to solve the maritime ECR problem in our future study.

Appendix

A. Convergence Theorem of SPELL

In this appendix, we state the convergence of the theorem of SPELL. Subsequently, we list several properties of the approximation that are used to prove the convergence of SPELL. Finally, we present the proof for our theorem.

Without loss of generality, we make the following assumptions: (A.1) is convex and compact (A.2) is convex, finite, and continuous on  (A.3) is bounded such that for each ; is bounded such that for each  (A.4) Piecewise linear function is convex, implying that (A.5) The step size is -measurable and satisfies In addition to the assumption from (A.1) to (A.5), the following assumption is required to characterize the piecewise linear convex approximation functions. (A.6) There exists a constant and a positive , such that for any two points if , then . If there exists and such that then . If , then the function becomes purely linear; if , then the function corresponds to a strongly convex function.

Given assumptions (A.1) to (A.6), we obtain the following theorem of SPELL.

Theorem 1. If (A.1)–(A.6) are satisfied, then the sequence of generated by the algorithm SPELL converges almost surely to the optimal solution of problem (8).

To prove Theorem 1, we need to use the Martingale convergence theorem and three lemmas.

Martingale Convergence Theorem. A sequence of random variables , which are -measurable, is said to be a supermartingale if the sequence of conditional expectations exists and satisfies .

Theorem 2 (from [43], p.26). Let be a positive supermartingale. Then, converges to a finite random variables a.s.

The above definition indicates that is essentially the stochastic analogue of a decreasing sequence.

On the basis of the convexity property, the optimal solution for problem (i) in Figure 3 at iteration is characterized by the following inequality:

To obtain Theorem 1, we require the following three lemmas. The first lemma indicates that the difference between the solutions of two consecutive update processes is bounded by the step size and magnitude of the stochastic gradient. The second lemma shows that the approximation is finite, and the third lemma indicates that (which will be explained later) is bounded.

Lemma 1. For any two iterations and , solutions and produced by SPELL satisfy the following:

Proof. Consider a special case, where and correspond to two consecutive iterations. Let and . On the basis of (A.3), we know thatOn the basis of the updating rule of the approximation function, we can obtainWe substitute with in equation (A.6) and obtainWe rearrange the terms to obtain the following expression:If iteration and are not in the same update process, this implies that Based on assumption (A.6), we know that .
On the basis of equations (A.3) and (A.6) and , we obtainWe apply Schwartz’ inequality to obtain the following expression:Thus, . The following expression is applicable:For any , and . Therefore,For any and for any . Therefore,