Surrogate-based optimization approach for capacitated hub location problem with uncertainty

Abstract

CJ Logistics has started to consider opening single new hub facility to expand the current transportation network system. This naturally leads to formulating a research question “where should the new hub facility be located in South Korea to minimize total transportation cost of the network system operated by the company?”. This research aims to answer the question by proposing a surrogate-based optimization approach. In addition to finding an optimal location of the new hub facility, this research performs sensitivity analysis to study the correlation between hub capacity (i.e., the source of uncertainty) and transportation cost. The results indicate that (1) total transportation cost after the establishment of the new hub facility at the optimal location is reduced by approximately 14% compared to the current transportation network system and (2) the currently operated hub facility located in Daejeon has the greatest influence on total transportation cost; while the existing hub facilities located in Cheongwon, Yongin, and Gunpo have little impact on total transportation cost after the construction of the new hub facility. It is expected that the outcome of this research helps the company systematically manage the transportation network system when the new hub facility is constructed.

Keywords:

• Capacitated hub location problem
• uncertainty
• design of experiment
• linear programming
• machine-learning-based surrogate modeling
• Monte-Carlo simulation
• sensitivity analysis

1. Introduction

The growth of e-commerce in South Korea has continuously led parcel service providers to think of a plan that minimizes the amount of time for delivery. CJ Logistics, a front-running leader in the industry, has enabled next-day parcel delivery service by implementing a hub-and-spoke system notionally illustrated in Figure 1. The company operates five hub facilities and 270 sub-terminals with 16,000 vehicles for timely delivery of a maximum of 5.28 million boxes in a day (Jin & Kim, 2018). Although the hub-and-spoke system operated by the company has significantly reduced delivery time from hub facilities to customers, it appears that the company will soon confront a transportation network saturation point as parcel supply in South Korea continues to grow. In response to this concern, the company has started to consider opening single new hub facility to expand the current delivery service network, naturally leading to the following research question “where should the new hub facility be located in South Korea to minimize total transportation cost of the current delivery service network?”. This research aims to answer the aforementioned research question by proposing a surrogate-based optimization approach that leverages design of experiment (DoE), linear programming, machine-learning-based surrogate modeling (i.e., Multi-Layer Perceptron (MLP)), and Monte-Carlo simulation. In addition to finding an optimal location of the new hub facility, this research performs sensitivity analysis on the correlation between hub capacity (i.e., the source of uncertainty) and transportation cost. The main contribution of this research is to propose a novel approach using the surrogate-based optimization approach for a capacitated hub location problem with the aim of helping logistics companies evaluate potential candidates for an optimal location of a new hub facility more systematically. The remainder of this paper is organized as follows: Literature Review, Proposed Methodology, Results and Discussion, and Conclusion.

Figure 1. Notional sketch of a hub-and-spoke system.

2. Literature review

A hub location problem has been widely studied by various researchers from different backgrounds. For example, transportation hub location problems have been investigated with the aim of locating hub facilities systematically to minimize total transportation cost, whereas telecom network systems have been studied to provide a movement of electronic messages in a more efficient manner (Campbell & O’Kelly, 2012). Particularly, when it comes to a transportation hub location problem, Goldman (1969) first introduced an optimal location problem in a network with the aim of minimizing total transportation cost associated with the network. The objective of the optimal location problem formulated by Goldman in 1969 was to determine a point x in the network minimizing total transportation cost. Although it is true that Goldman first introduced the optimal location problem in a network, it is noteworthy that O’Kelly (1986a, 1987) first presented mathematical formulations for a hub location problem (i.e., p-hub median problem) through air transportation network studies. O’Kelly specifically concentrated on analysing hub and spoke networks with the aim of finding an optimal network solution by allocating p-hubs while satisfying a series of constraints.

The p-hub median problem has been studied by various types of approaches since Goldman and O’Kelly formulated the problem conceptually as well as mathematically. The first type of approach is to use integer programming formulations. For example, Campbell introduced the first linear integer programming formulation (Campbell, 1994), Skorin-Kapov et al. developed the new mixed integer formulation (Skorin-Kapov et al., 1996), and Ernst et al. proposed the different linear integer programming formulation (i.e., reducing variables and constraints to solve larger problems) for a single allocation p-hub median problem (Ernst & Krishnamoorthy, 1998). Another type of approach is to utilize heuristic algorithms given that the p-hub median problem is a Non-deterministic Polynomial (NP) hard problem. For instance, Sue presented the simulated annealing algorithm to solve the p-hub median problem (Abdinnour-Helm, 2001) with the aim of finding near optimal solutions.

In addition to finding a deterministic solution for hub location problems, there have been a few attempts to address hub location problems under uncertainty such as demand. For example, S. A. Alumur et al. (2012) analysed two sources of uncertainty (i.e., the set-up costs for the hubs and the demands to be transported between the nodes) and proposed a comprehensive model that considers the two sources of uncertainty when concerning a hub location problem. Contreras et al. (2011) particularly concentrated on uncapacitated hub location problems in which uncertainty was associated to demands and transportation cost. The authors specifically employed a Monte-Carlo simulation-based algorithm that integrated a sample average approximation scheme to solve the problems. Wandelt et al. (2022) proposed a methodology for dealing with the air/rail multiple hub allocation problem with uncertainty on travel demand. The authors evaluated the performance of the proposed methodology compared to the CPLEX software especially with aim of significantly reducing computational costs while obtaining reasonable optimality of the solution.

Recently, Sibel A. Alumur et al. (2021) published a paper with the aim of providing perspectives on modeling hub location problems by identifying important gaps in the hub location problem literature. The authors claimed that the key for successfully addressing hub location problems is how to properly model the problem. In other words, it is important to examine details of problem definition beyond just defining objective function and constraints mathematically (Wandelt et al., 2022), indicating that we should properly capture real-world details and incorporate into a simulation environment to ultimately reduce the gap between reality and simulation. This naturally results in greatly increasing computational costs; thus, it seems that there is a need to balance between model quality (e.g., one may want to obtain a solution as exact as possible no matter what computational challenges are) and solution difficulty (e.g., one may explore near optimum solutions while significantly reducing computational costs) when hub location problems are studied. For example, Rostami et al. (2018) used an outer approximation method to linearize the hub location problem and then solved it using a branch-and-bound algorithm. The authors claimed that the problem was solved at reasonable computing times. Other linearization strategies have also been used to handle computational challenges (Azizi et al., 2016, 2018).

This research puts more efforts into relaxing solution difficulty than maintaining model quality by developing a framework with the emphasis on the following aspects: (1) it avoids incorporating unrealistic simplifying assumptions to increase model quality but trying to reflect real-world constraints, (2) instead of approximating or linearizing the problem, it employs a surrogate-based optimization approach that leverages DoE, linear programming, machine-learning-based surrogate modeling, and Monte-Carlo simulation to ultimately address a large-scale capacitated hub location problem (i.e., six hub facilities and 270 sub terminals) with uncertainty (i.e., currently operated hub facility capacity), and (3) it acknowledges the limitations of the surrogate-based optimization approach to generate an exact solution (i.e., an optimal location of the given problem); however, it can be compromised in a way that it would be better to provide near-optimal solutions, to the best of our knowledge, given that the best optimal location may not be acceptable in the South Korea territory due to many constraints in the reality such as policy issues. Additional details about the proposed methodology will be discussed in the next section.

3. Proposed methodology

This research proposes a methodology with the aim of providing a framework designed to address a large-scale capacitated hub location problem with uncertainty (i.e., hub capacity). The proposed methodology, which is notionally delineated in Figure 2, employs the advanced design methods (Kim et al., 2018, 2020) and consists of four different steps: (1) specifying lower and upper bounds with respect to design variables, (2) implementing DoE techniques to explore a design space in a more efficient manner, (3) creating a machine-learning-based surrogate model using the simulation results from the Transportation Problem (TP) algorithm, and (4) running Monte-Carlo simulations to perform sensitivity analysis. More specifically, Step 1 is to constraint the design space (i.e., South Korea territory) by specifying lower and upper bounds with respect to longitude and latitude. This step is needed to accommodate the company’s request; for example, the company does not want to construct a new facility in the edge of the territory. Once the design space is determined, Step 2 is to implement DoE techniques. Particularly, this research uses the Central Composite Design (CCD) technique to capture corner points of the design space and the Latin Hypercube Sampling (LHS) technique to capture inner points of the design space. Step 3 is to create a machine-learning-based surrogate model (i.e., MLP) using the simulation results generated from the TP algorithm. After successfully validating the surrogate model, Step 4 is to run Monte-Carlo simulations to conduct sensitivity analysis with the aim of identifying correlation between total transportation cost and latitude/longitude or hub capacity as needed.

Figure 2. Overview of the proposed methodology.

3.1. Data collection

The company (i.e., CJ Logistics) provides the following datasets for implementing a modeling and simulation environment: (1) sub-terminal location (i.e., latitude and longitude), (2) supply box information, (3) hub facility location, (4) hub capacity information, (5) real distance and cost information for different routes, (6) truck carrying capacity, and (7) number of trucks allocated to destinations. The dataset associated with number of trucks allocated to destinations is used especially for a validation purpose in a way that the real number of trucks are compared against number of trucks assigned in the simulation environment.

3.2. Design of experiment

DoE, a sampling technique that maximizes the amount of information with a limited set of experiments (Giunta & Wojtkiewicz, 2003), is utilized to systematically explore the design space (i.e., South Korea territory) with two design variables (i.e., latitude and longitude). Two representative DoE methods are employed: (1) the LHS technique (Stein, 1987) is used to capture inner locations of the design space and (2) the CCD technique is utilized to capture corner locations of the design space. Lower and upper bounds with respect to the design variables are specified according to the policy of the company. This indicates that the proposed methodology is designed to address a constrained optimization problem (i.e., finding an optimal hub location within the specified range). Figure 3 notionally shows how a set of samples (i.e., blue dots) are distributed in the constrained design space. Each sample point shown in Figure 3 represents a candidate for an optimal hub location with the particular latitude and longitude. The candidate is modeled as one of the main hub facilities operated by the company in a simulation environment. Once the new hub facility is fed into the modeling and simulation environment, the TP algorithm estimates simulated transportation cost with the aim of minimizing costs related to distribution of parcel from a few sub terminals to a few hub facilities. All of the sample points are simulated by the TP algorithm to generate a set of input (i.e., latitude and longitude) and output (i.e., transportation cost) mapping.

Figure 3. Constrained design space with hub location candidates.

3.3. Transportation problem

The TP algorithm, a special type of Linear Programming, is employed as a modeling and simulation engine for estimating simulated transportation cost given origin-destination flows. The optimization problem formulated for this research is as follows:

$\mathit{minimize}\mathit{\hspace{0.17em}}\sum _{\mathit{i}=1}^m\sum _{\mathit{j}=1}^n{c}_{\mathit{ij}}{x}_{\mathit{ij}}$

Subject to:

$x_{\mathit{ij}}\ge 0\mathit{\hspace{0.17em}}\left(\mathit{i}=1,2,\cdots \mathit{m};\mathit{j}=1,2,\cdots \mathit{n}\right)$

$\sum _{\mathit{i}=1}^m{x}_{\mathit{ij}}=\mathit{Deman}{d}_i$

$\sum _{\mathit{j}=1}^n{x}_{\mathit{ij}}=\mathit{Suppl}{y}_i$

The objective function is designed to minimize transportation cost while satisfying various constraints (e.g., hub demand, sub supply, and truck carrying capacity) to reflect real-world operational perspectives of the company. It is important to note that the company has used a classification code, which is a number assigned to a group of destination, to sort parcels at an origin terminal in a more efficient manner (Park & Kim, 2020). Due to the company’s classification code regulation, it is sometimes observed that particular routes are not allowed for vehicles to transport from a sub terminal to a hub facility. This naturally invokes us to implement one constraint (i.e., Big-M method) where high penalty costs are typically applied to the particular routes in a simulation environment. In addition, dummy hub facilities are implemented in the simulation environment to convert the optimization problem from unbalanced TP to balanced TP. Figure 4 delineates the schematic of the transportation network system used in this research.

Figure 4. Schematic of the network system implemented for this research.

Given that this research is designed to particularly address a capacitated hub location problem, hub capacity information for existing hub facilities is fed into a simulation environment. Once all the necessary datasets (e.g., hub capacity) are prepared properly, the PuLP library (Mitchell et al., 2011) is initiated with the constructed network system to estimate total transportation cost as well as allocate number of trucks to the hub facilities. For a validation purpose, the TP algorithm implemented in this research is validated with the real number of trucks allocated at the particular date (i.e., Thursday, May 15, 2018) and the corresponding transportation cost. The validation results indicate that there is a 2.2% difference between reality and simulation especially for the transportation cost, implying that the TP algorithm generates valid results as long as input data (e.g., supply, demand, and truck capacity) are provided accurately.

After validating the TP algorithm, a new hub facility is added to the existing network system in the simulation environment. It is important to note that the new hub’s capacity is determined based on the company’s forecasting report. A location of the new hub facility is specified in the simulation environment according to the sample points from the results of the hybrid DoE. A total of 200 sample points (i.e., 200 different locations) are simulated by the TP algorithm to generate output results, namely total transportation cost for 200 cases, that are eventually used for creating and validating a surrogate model.

3.4. Machine-learning-based surrogate modeling

This research employs one of the supervised machine learning methods, namely MLP (Rumelhart et al., 1986), to generate a non-linear surrogate model that represents the design space (i.e., South Korea territory) of the design variables (i.e., latitude and longitude). The MLP-based surrogate model implemented in this research entails the following fully connected layers: (1) an input layer to receive latitude and longitude values, (2) an output layer that makes a prediction with respect to transportation cost, and (3) two hidden layers that are considered as a computational engine for finding the best weight parameters during a training process. Figure 5 shows a diagram of the MLP-based surrogate model structure used for this research.

Figure 5. Diagram of the MLP-based surrogate model structure.

To find the best weight parameters of the MLP-based surrogate model, this research utilizes the Adam algorithm (Kingma & Ba, 2014), an extended version of the stochastic gradient descent method, with an iterative procedure mapping a set of input values to a set of output values through hidden layers with the aim of creating a regression model that minimizes an error between predicted and actual values. It is important to note that free hyper-parameters of the MLP-based surrogate model (i.e., number of hidden nodes, learning rate, batch size, and regularization penalty parameter) are determined by a trial-and-error approach.

To evaluate the accuracy of the MLP-based surrogate model, the 200 sample points (i.e., 200 candidates for an optimal location of a new hub facility) generated from the step of DoE are decomposed into a training dataset (140 points, 70%), a validation dataset (40 points, 20%), and a testing dataset (20 points, 10%). It is worth mentioning that one point refers to the situation where one candidate for a new hub facility location is constructed in the simulation environment and the TP algorithm is run for the current network system with the new hub facility to generate the simulated transportation cost. Then, the coefficient of determination (i.e., R-squared) is first computed to get a sense as to whether the model works as intended. As a high value of the coefficient of determination does not imply that a regression model is accurate, the Root Mean Square Error (RMSE) is calculated to estimate the standard deviation of the error (i.e., how residuals are spread out). In particular, two different types of RMSE distributions, which include (1) Model Fit Error (MFE) that represents how well a regression model fits data points and (2) Model Representation Error (MRE) that refers to how well a regression model predicts an actual response, are investigated. Since the MFE (i.e., training error) is not sufficient for the MLP-based surrogate model evaluation process, this research specifically concentrates on the MRE (i.e., validation error) to ensure the predictive capability of the MLP-based surrogate model. It is worth mentioning that the K-Fold method (Anguita et al., 2012) is utilized to address potential over-fitting issues of the MLP-based surrogate model. Figure 6 shows the results of the actual by predicted plot for transportation cost in which values are removed due to security concerns. As shown in Figure 6, the transportation cost predicted by the MLP-based surrogate model is almost identical to the actual transportation cost estimated by the TP algorithm. Furthermore, the predicted transportation cost is randomly scattered along the perfect fit line (i.e., black solid line), indicating that the surrogate model works as intended given that the absolute maximum error is less than 1%.

Figure 6. Actual by predicted plot for the MREs.

3.5. Monte-Carlo simulation

Given that the accuracy of the MLP-based surrogate model is reasonably acceptable according to the results of the model evaluation process, this research utilizes the Monte-Carlo simulation technique to see the trend of resulting outcome distributions by mapping input and output values. Figure 7 notionally describes the Monte-Carlo simulation process flow diagram implemented in this research. To generate the output (i.e., transportation cost) distribution, it is imperative to specify lower and upper bounds of the design variables (i.e., longitude and latitude) properly. Min/max values for the bounds of the design variables are determined by the company. Uniform sampling distribution with the min/max values is used for the design variables. The Monte-Carlo simulation is then performed with 100,000 sample points that are randomly generated from the uniform distribution of the design variables. The obvious upside of this approach is to enable a framework to run large number of simulation cases very rapidly. In this research, five seconds are only needed to populate 100,000 output values given that the MLP-based surrogate model is accurate.

Figure 7. Notional sketch of the Monte-Carlo simulation for input–output mapping.

4. Results and discussion

Given that the proposed methodology presented in the previous section was validated against real-world operational data in an appropriate manner (e.g., there is little difference between real-world operations, namely the baseline case, and simulation results generated by the TP algorithm; the transportation costs predicted by the MLP-based surrogate model are almost identical to the simulated transportation costs by the TP algorithm), this section is dedicated to answering and discussing two research questions formulated from the beginning of this research by using the proposed methodology: (1) where should the new hub facility be located in South Korea to minimize total transportation cost of the current delivery service network? (Section 4.1) and (2) what is the correlation between total transportation cost and hub capacity (i.e., the source of uncertainty), especially for the currently operated hub facilities (i.e., Okcheon, Cheongwon, Yongin, Gunpo, and Daejeon), when there is a need to rebalance hub capacity over the entire transportation network system after the construction of the new hub facility at the optimal location? (Section 4.2).

4.1. Where should the new hub facility be located in South Korea?

With the aim of finding an optimal location (i.e., minimizing total transportation cost) of the new hub facility, the results of the 100,000 Monte-Carlo simulation runs were analysed to see the trends of the transportation cost with respect to latitude and longitude. Figures 8 and 9 show the trends where (1) the simulated transportation cost decreases as latitude increases within the specified upper/lower bounds and (2) the simulated transportation cost has the minimum point in terms of longitude within the specified upper/lower bounds. Please note that each black dot represents one of the Monte-Carlo simulation runs. The optimal location was then implemented as the location of the new hub facility to the existing transportation network system in the simulation environment for calculating total transportation cost. As a result, it appeared that total transportation cost was reduced compared to the current transportation network system operated by the company. However, it is important to note that the optimal location of the new hub facility may not be feasible in reality as there may be potential barriers associated with residential concerns and policy issues; thus, the barriers may not allow the company to build the new hub facility to the optimized location. In response to these concerns, near-optimal solutions where total transportation cost would not be exactly same but almost identical with the optimum point were explored. This enabled the company to determine the best location of the new hub facility in a more appropriate manner by taking advantage of flexibility with respect to the optimal solutions. Figure 10 shows how to explore near-optimal locations of the new hub facility in the constrained boundary. Due to security concerns, we were determined to not show exact location information (e.g., name of the cities). With the new optimal location determined by exploring the near-optimal solutions, it was found that total transportation cost was reduced by approximately 14% compared to the current transportation network system.

Figure 8. Monte-Carlo simulation results for transportation cost w.r.t. latitude.

Figure 9. Monte-Carlo simulation results for transportation cost w.r.t. longitude.

Figure 10. Near optimum exploration for the new hub facility location.

4.2. What is the correlation between total transportation cost and hub capacity (i.e., the source of uncertainty)?

After discussing about potential benefits of the establishment of a new hub facility with the company, we recognized that the company would want to change hub capacity for all existing hub facilities (i.e., Okcheon, Cheongwon, Yongin, Gunpo, and Daejeon) to rebalance hub capacity over the entire transportation network system operated by the company. This naturally motivated us to perform sensitivity analysis on the correlation between existing hub capacity variability and total transportation cost. Lower and upper bounds with respect to the capacity of the existing hub facilities operated by the company were determined according to the company’s policy. The proposed methodology was then re-utilized with the same procedure (i.e., DoE, the TP algorithm, machine-learning-based surrogate model, and Monte-Carlo simulation) but with different design variables (i.e., capacity for the currently operated hub facilities). It is assumed that (1) the location of the new hub facility determined based on the optimization study is fixed and (2) the capacity value of the new hub facility (i.e., constant value) is specified according to the company’s policy; thus, the value is also fixed in the simulation environment. It is important to note that the MLP-based surrogate model structure is different from the previous one, as shown in Figure 11, even though the same methodology was employed.

Figure 11. Diagram of the MLP-based surrogate model structure used for sensitivity analysis on hub capacity uncertainty.

Figure 12 shows the results of sensitivity analysis on hub capacity uncertainty and total transportation cost. As can be seen, it was observed that hub capacity variability of the facility located in Daejeon had the greatest influence on total transportation cost compared to the other hub facilities. The trends indicated that total transportation cost increased as hub capacity of the hub facilities in Daejeon and Okcheon increased, whereas hub capacity variability of the hub facilities in Cheongwon, Yongin, and Gunpo had little impact on total transportation cost. This implies that the company may have to carefully consider the impact of Daejeon’s capacity variability when the company needs to rebalance hub capacity after the establishment of the new hub facility. It is expected that the outcome of this analysis enables the company to balance hub capacity systematically over the entire transportation network system after the new hub facility is constructed.

Figure 12. Monte-Carlo simulation results for sensitivity analysis on hub capacity uncertainty.

5. Conclusion

This research starts by the efforts to support the decision-making process of the company with respect to finding an optimal location of a new hub facility (i.e., minimizing total transportation cost of the network system operated by the company) and further extends the scope of research by leveraging a proposed methodology to see the impact of hub capacity considered as the source of uncertainty. The proposed methodology consists of four different pillars: (1) DoE to explore the specified design space within the South Korea territory in a more efficient manner, (2) linear programming to estimate total transportation cost of the given network system operated by the company, (3) machine-learning-based surrogate modeling to generate a proper response surface in terms of the specified input (e.g., hub capacity) and output (e.g., transportation cost) variables, and (4) Monte-Carlo simulation to perform sensitivity analysis to study the correlation between input and output variables. Eventually, with the proposed methodology, the authors first could identify the optimal location of a new hub facility based on the results of sensitivity analysis showing the trends where the simulated transportation cost decreased as latitude increased, whereas the simulated transportation cost had the near-optimal points with respect to longitude within the pre-determined lower and upper bounds. According to the results of simulation, it is expected that total transportation cost after the establishment of the new hub facility at the optimal location is reduced by approximately 14% compared to the current transportation network system operated by the company. Second, the authors could study the correlation between total transportation cost and hub capacity, especially for the currently operated hub facilities. The results of sensitivity analysis show that the hub facility located in Daejeon had the greatest influence on total transportation cost; while the hub facilities located in Cheongwon, Yongin, and Gunpo had little impact on total transportation cost, implying that the company may have to carefully consider the impact of Daejeon’s capacity variability when the company needs to rebalance hub capacity after the establishment of the new hub facility. The main contribution of this research is to propose a novel approach using machine learning and the advanced design methods for a capacitated hub location problem with the aim of helping logistics companies to evaluate potential candidates for an optimal location of a new hub facility more systematically. In addition to providing the systematic approach as the outcome of this research, another contribution of this research is to provide a framework that is more efficient than traditional approaches (i.e., it must formulate an optimization problem and evaluate all possible cases) especially for a large-scale capacitated hub location problem with various uncertainty sources. The authors, however, acknowledge that the proposed approach may have some limitations on its implementation such as finding near-optimal solutions, which is originated from the nature of Monte-Carlo simulation, instead of the best optimal solution mathematically. This can be compromised in a way that it would be better to provide a variety of location candidates based on the near-optimal solutions given that the best optimal location may not be acceptable due to many constraints in the reality (e.g., policy issue).

Acknowledgements

This research is an extension of a Ph.D. summer internship project that was done at CJ Logistics in 2018. We would like to thank Byungdo Lee, Wansik Kim, and Junghoon Kim for their feedback on this research.

Disclosure statement

No potential conflict of interest was reported by the authors.

Data availability statement

The data are not publicly available due to restrictions (e.g., they contain company-sensitive information).

Additional information

Funding

No specific funding is granted for this research.

Notes on contributors

Junghyun Kim

Junghyun Kim is an assistant professor in the School of Applied Artificial Intelligence at Handong Global University and the director of Engineering Systems Design Laboratory. Prior to joining Handong Global University, he worked at American Airlines located in Dallas, Texas, as a full-time operations research analyst. He earned his Ph.D. in Computational Science and Engineering from the Georgia Institute of Technology. His research focuses on integrating three different areas of specialization (i.e., machine learning, optimization, and advanced design methods) and utilizing them to solve real-world problems in various engineering fields.