Sage Journals: Discover world-class research

Abstract

Fourth party logistics is an urgent need for economic and social development, and its research focuses on path optimization. Comprehensively considering the choice of third party logistics suppliers, routes, and transportation modes, this study proposes a multi-objective transportation optimization model based on queuing theory, which minimizes cost, time, and carbon emissions. In addition, to solve the problems of infeasible solutions in fourth party logistics route optimization (4plrp), a priority-random based strengthen elitist genetic algorithm is proposed. Experiments show that the algorithm has good convergence and stability in solving small/large 4plrp and is superior to six typical algorithms, such as the elite genetic algorithm.

Keywords

Fourth party logistics route optimization multi-objective optimization multigraph priority-random based encoding genetic algorithm

Introduction

With the rapid development of e-commerce, merchants transfer their logistics business to third party logistics (3pl) companies for services to reduce costs. However, with the continuous expansion of the logistics market, 3pl has gradually shown its limitations, such as single-service projects, low level of informatization, and lack of cooperation among enterprises, making realizing the optimal allocation of social resources difficult.^1,2 In response to these shortcomings, fourth party logistics (4pl) emerge and meets the complex actual transportation needs by integrating 3pl logistics resources.^3,4

Path problem is one of the most important problems in logistics, which has always been a hot topic in people’s research. The fourth party logistics routing problem (4plrp) is more complex compared with the traditional 3pl routing.⁵ In addition to considering route selection, 4pl as a leading logistics service provider must comprehensively consider factors, such as transportation capacity, transportation cost, and reputation index of different 3pl suppliers, making the 4pl path a kind of multigraph. Compared with the third party logistics routing problem (simple graph), 4plrp has a larger solution space, so solving this problem is more difficult.⁶ At present, several scholars have researched on this topic.

In the establishment of mathematical models, many studies regard the objective function of transportation cost and transportation time to reduce enterprise costs and improve customer satisfaction. For example, Li and Huang⁷ mainly studied the problem of minimum total cost under multiple transportation mode selections in 4pl. Deng et al.⁸ proposed a route optimization model that minimizes the total cost under centralized and decentralized mixed transport modes. Cui et al.⁹ discussed a multi-origin single-destination 4pl path study with fuzzy duration and cost discount. The above studies mostly take transport time as the constraint variable and cost as the objective function because the solving process of multi-objective is highly complex. However, with the deepening of multi-objective studies, some scholars also take transport time as the objective function. Sivaramkumar et al.¹⁰ studied the routing problem of multi-target vehicles with time Windows, striving to minimize the total distance traveled by all vehicles, the total number of vehicles used, and the total gap between ready time and the issuing time. The above models generally assume that the waiting time of the nodes (e.g. vehicles that pass through and need to undergo loading, unloading, handling, and information entry) is constant. This process is a queuing problem, but the queuing theory is usually used to study the service problems of the desk waiting^11,12 and working holiday systems.^13,14 Few studies consider the queuing waiting problem in 4plrp literature. Moreover, most of the above models do not consider carbon emissions. The global environment is deteriorating. According to the U.S. “E & E News” website, the global CO₂ emission reached 36.8 billion tons by the end of 2019. Therefore, the transportation field, as one of the largest sources of greenhouse gases, has attracted great attention, and reducing carbon emissions has become an inevitable trend of logistics development.^15,16 Moreover, energy conservation and emission reduction are one of the strategic plans for the long-term development of relevant enterprises and an important measure to promote the sustainable development of the ecological environment and economy. Therefore, today’s logistics distribution should not only be studied from the perspective of enterprise cost and customer time satisfaction, but also consider carbon emissions.

In terms of model solving, the genetic algorithm (GA) is a random search method with the advantages of multi-directional optimization. The convergence results of GA have a slight correlation with the initial value, so GA is widely used in scheduling,^17,18 process parameter optimization,¹⁹ path optimization,²⁰ etc. Chen et al.²¹ used GA to solve 4plrp with 10 nodes. Yan et al.²² embedded the Hooke-Jeeves method with good local optimization ability in GA and improved GA’s solving ability of 4plrp, aiming at the problem that GA is prone to fall into the local optimal solution. Liu et al.²³ studied 4pl logistics tasks and resource scheduling problems, proposed an improved non-dominated sorting GA (NSGA-II) to solve the problem of multi-objective function in 4plrp to a certain extent. However, the above algorithms use conventional coding methods, such as binary and real coding, and their decision variable dimension is equal to the number of multigraph edges. When the nodes of the multigraph exceed 30, the edges of the multigraph are generally as high as thousands, where the GA above generally hardly obtains high-quality solutions or even feasible paths.⁹ Aiming at this problem, Cui et al.⁹ proposes a multi-array encoding method, uses two arrays to represent a chromosome. Among them, the first array represents the city ordinal number, and the second one represents the 3pl selected among cities. This coding method makes all individuals of a population legal when initialized but fails to guarantee the legitimacy of the descendants generated by cross mutation, thereby limiting the convergence of the algorithm. Huang et al.⁶ proposed two algorithms (improved node-based and derived-based GA) to solve the problem of an unfeasible path in 4plrp. However, these two algorithms depend on their proposed path repair strategy, and the legitimacy of the generated offspring needs to be guaranteed by repair, thereby limiting search efficiency. Therefore, this study focuses on GA to avoid illegal paths.

This study aims at addressing the problem of waiting in queue for vehicles to serve at the node center. Queuing theory is integrated into 4plrp, comprehensively considering the choice of 3pl supplier, route, and transportation mode. A mathematical model is also built to minimize transportation costs, time, and carbon emissions. In addition, inspired by literature,²⁴ this study proposes a priority random-based strengthen elitist GA (prSEGA) for large 4plrp. The prSEGA has the following advantages. (1) The decision variable dimension is equal to the number of multigraph nodes, thereby greatly reducing the decision variable dimension. (2) The path obtained by the priority-random encoding method is the complete path from the origin to the destination node, which improves the convergence of the algorithm. (3) The elite retention strategy is used to directly copy the highly adaptive individuals to the offspring, thus improving the algorithm’s convergence speed.

The rest of this paper is organized as follows. Section 2 introduces the multi-objective mathematical model. Section 3 designs prSEGA, Section 4 provides an example and compares the performance of the prSEGA with several typical genetic algorithms. Section 5 concludes the study.

Problem description and mathematical modeling

Problem description

4pl companies must maximally reduce transportation costs, time, and carbon emissions according to a comprehensive choice of 3pl suppliers, routes, and transportation modes to provide customers with high-quality transportation solutions. The following assumptions are proposed. A batch of goods is transported from the origin $v_{1}$ to the destination $v_{7}$ . First, multiple paths are available to choose from. Second, multiple 3pl vendors can provide shipping services between the two nodes (the corresponding transportation cost of a 3pl supplier with high ability and reputation is high, and thus, selecting a 3pl supplier according to the actual demand is necessary). Third, 3pl supplier can select multiple modes of transportation.

The above practical problems are then transformed into mathematical problems. Figures 1 and 2 show that the 4pl path problem above can be described as a multigraph $G (V, E)$ problem with multiple attributes, such as cost, time, vehicle transport capacity, and historical reputation. $V (| V | = n)$ represents the set of nodes, that is, the set of transit centers. E denotes the collection of edges or the numbered set of 3pl vendors who can undertake tasks. 1 and 2 indicate the 3pl supplier numbers that can be selected between the two nodes, and (1), (2), (3), and (4) represent the modes of transportation available to the 3pl supplier. When the node of the transportation mode is changed, the corresponding transfer time and transfer costs must be undertaken. When performing services at the node for aspects, such as loading, unloading, and information entry, the queuing waiting condition occurs because the node centers are limited in size and are used by multiple 3pl companies. Thus, a certain waiting time and cost are generated.

Figure 1.

4plrp transport network multigraph.

Figure 2.

Multiple modes of transport between adjacent nodes multigraph.

Model assumptions

Hypothesis 1: Vehicle arrival at the node center and the node center for service correspond to the queuing theory process.²⁵ Each vehicle reaches the node center independently, and the service time of the node center follows the negative exponential distribution.

Hypothesis 2: The central service desk of the node is represented as 1, the space is unlimited, and infinite queuing is allowed.

Hypothesis 3: When performing a transportation task on two nodes, only one 3pl vendor can be selected, and that vendor can only select one transportation mode. Moreover, the change of 3pl supplier and transportation mode is not taken into account in the course of transportation.

Parameter definition

$r_{ij}$ represents the number of 3pl vendors between nodes $i \to j$ and $i, j \in (1, 2, \dots, n)$ , and m denotes a collection of transportation modes.

$C_{ijk}^{l}$ , $T_{ijk}^{l}$ , $P_{ijk}^{l}$ , and $A_{ijk}^{l}$ respectively indicate the unit cost, unit time, transportation capacity, and historical reputation consumed by the selected 3pl vendors. No. k transports cargo from nodes i to $j$ through the transportation mode l, $k \in (1, 2, \dots, r_{ij})$ , $l \in m$ .

$C_{i}^{l, u}$ , $T_{i}^{l, u}$ , and $P_{i}^{l, u}$ respectively indicate the unit cost, unit time, and processing capacity when transportation mode l is transformed into transportation mode $u$ in the node i, $l, u \in m$ .

$C_{i}$ represents the waiting cost of goods per unit weight at node i.

$e_{i}$ indicates the carbon emissions per unit weight of cargo in transportation mode l.

$d_{ij}^{l}$ is the distance between the nodes i and $j$ when transportation mode l is selected.

q represents the quality of the goods shipped by the 4pl.

$λ_{i}$ is the average number of vehicles arriving at the center of node i in unit time.

$μ_{i}$ is the average service rate of node center i, and $\frac{1}{μ_{i}}$ is the average service time.

A represents the reputation index of customer requirements.

R is a complete path chosen between the starting point and the destination.

$x_{ijk}^{l} (R)$ , $y_{i}^{l, u} (R)$ , and $Z_{i} (R)$ are all 0–1 variable, when 3pl supplier No. k and transport mode l undertake the transportation between node i and $j$ , $x_{ijk}^{l} (R) = 1$ . Otherwise, $x_{ijk}^{l} (R) = 0$ .

When transport mode l is changed to $u$ in node i, $y_{i}^{l, u} (R) = 1$ , otherwise, $y_{i}^{l, u} (R) = 0$ .

When carrying the transport task at the node i, $Z_{i} (R) = 1$ , otherwise, $Z_{i} (R) = 0$ .

Model establishment

According to the stated assumption, the arrival of transport vehicles at the node center for service is considered a queuing theory problem. Moreover, only one service desk exists in the node center, thereby allowing for infinite queuing and infinite space. This situation is a kind of the simplest queuing system-single service desk waiting system model $M / M / 1 / \infty$ . Hence, the average stay time per unit weight cargo of the transport vehicle at the node center is $W_{i} = \frac{1}{μ_{i - λ_{i}}}$ .²⁶

To sum up, the establishment of the 4plrp multi-objective model is as follows:

m i n {\sum_{l \in m} \sum_{i = 1}^{n} \sum_{j = 1}^{n} \sum_{k}^{r_{i j}} C_{i j k}^{l} q x_{i j k}^{l} (R) + \sum_{l, u ϵ m} \sum_{i = 1}^{n} C_{i}^{l, u} q y_{i}^{l, u} (R) + \sum_{i = 1}^{n} C_{i} q \frac{1}{μ_{i} - λ_{i}} Z_{i} (R)}

(1)

\min {\sum_{l \in m} \sum_{i = 1}^{n} \sum_{j = 1}^{n} \sum_{k}^{r_{ij}} T_{ijk}^{l} x_{ijk}^{l} (R) + \sum_{l, u ϵ m} \sum_{i = 1}^{n} T_{i}^{l, u} y_{i}^{l, u} (R) + \sum_{i = 1}^{n} \frac{1}{μ_{i} - λ_{i}} Z_{i} (R)}

(2)

\min \sum_{l \in m} \sum_{i = 1}^{n} \sum_{j = 1}^{n} \sum_{k}^{r_{ij}} e_{l} d_{ij}^{l} {qx}_{ijk}^{l} (R)

(3)

s.t.

{qx}_{ijk}^{l} (R) \leq P_{ijk}^{l}

(4)

{qy}_{i}^{l, u} (R) \leq P_{i}^{l, u}

(5)

{Ax}_{ijk}^{l} (R) \leq A_{ijk}^{l}

(6)

R = {v_{s}, \dots, v_{i}, k, v_{j}, \dots, v_{e}} \in G

(7)

Equations (1)–(3) are objective functions. Equation (1) indicates that the cost of transportation is minimized and consists of the costs in transit, changing the transportation mode, and waiting in the node center. Equation (2) represents the minimization of transportation time, with the time function consisting of time in transit, time incurred by changing the transportation mode, and the queuing time. Equation (3) indicates a minimization of carbon emissions. Equation (4) suggests that the transport capacity of the 3pl supplier selected for the shipment of goods should be greater than or equal to the transport capacity required by the customer. Equation (5) means that when the goods pass through the node, the throughput capacity of the node is greater than or equal to the transportation capacity required by the customer. Equation (6) reveals that the reputation index of the 3pl supplier in the selected path should be greater than or equal to the reputation index A of customer requirements. Equation (7) shows that the transport route selected between the beginning and destination of the batch of goods is a complete path.

When dealing with the multi-objective optimization problem, the weight coefficients $α_{1}$ , $α_{2}$ , and $α_{3}$ ( $α_{1} + α_{2} + α_{3} = 1$ ) are directly assigned to each sub-objective. Then, they are transformed into a single-objective optimization problem for solving. However, the dimensions of each sub-objective function are inconsistent, and the magnitude of the value is also different. Assigning weights directly will make the sub-objectives with large numerical values optimal, but not all sub-objectives will become optimal. Therefore, in this study, each sub-objective is initially normalized, and then, the weight coefficient is given for linear weighting. Taking the sub-objective $Z_{1}$ as an example (the other two sub-objectives $Z_{2}$ and $Z_{3}$ are not considered), the mathematical model is established to minimize cost $Z_{1}$ and maximize cost $Z_{1}$ . Then, the algorithm proposed in this study is used to solve the problem to obtain the minimum value $Z_{1 \min}$ and maximum value $Z_{1 \max}$ . This study adopts the strategy of solving the extreme value multiple times because the convergence result of GA has some randomness. The objective function is expressed as follows:

Z = min (α_{1} \frac{Z_{1} - Z_{1 \min}}{Z_{1 \max} - Z_{1 \min}} + α_{2} \frac{Z_{2} - Z_{2 \min}}{Z_{2 \max} - Z_{2 \min}} + α_{3} \frac{Z_{3} - Z_{3 \min}}{Z_{3 \max} - Z_{3 \min}})

(8)

where

Z_{1} = {\sum_{l \in m} \sum_{i = 1}^{n} \sum_{j = 1}^{n} \sum_{k}^{r_{ij}} C_{ijk}^{l} {qx}_{ijk}^{l} (R) + \sum_{l, u ϵ m} \sum_{i = 1}^{n} C_{i}^{l, u} {qy}_{i}^{l, u} (R) + \sum_{i = 1}^{n} C_{i} q \frac{1}{μ_{i} - λ_{i}} Z_{i} (R)}

(9)

Z_{2} = {\sum_{l \in m} \sum_{i = 1}^{n} \sum_{j = 1}^{n} \sum_{k}^{r_{ij}} T_{ijk}^{l} x_{ijk}^{l} (R) + \sum_{l, u ϵ m} \sum_{i = 1}^{n} T_{i}^{l, u} y_{i}^{l, u} (R) + \sum_{i = 1}^{n} \frac{1}{μ_{i} - λ_{i}} Z_{i} (R)}

(10)

Z_{3} = \sum_{l \in m} \sum_{i = 1}^{n} \sum_{j = 1}^{n} \sum_{k}^{r_{ij}} e_{l} d_{ij}^{l} {qx}_{ijk}^{l} (R)

(11)

Algorithm design

This study proposes prSEGA to solve the problem of poor convergence of conventional GA to solving 4plrp. The algorithm adopts the proposed priority-random based encoding method, and the decoded path is the complete path from the origin to the destination node. During evolution, the accuracy and efficiency of solving large-scale multigraph problems are improved by directly retaining the population with large fitness. The framework of the proposed prSEGA can be summarized as follows:

Step 1 Initialize parameters: population size NP, maximum evolutionary algebra NG, crossover rate Pc, and mutation rate Pm.

Step 2 Initialize a population of NP individuals according to the proposed priority-random based encoding method.

Step 3 Calculate the objective function value and the fitness value of each individual.

Step 4 Select NP individuals as parents according to the championship selection method.

Step 5 Perform partially matching crossover operation and inversion mutation operation to generate NP offspring.

Step 6 Calculate the objective function and fitness values of each offspring.

Step 7 Combine the NP parents and the NP offspring to obtain 2N individuals.

Step 8 Select NP individuals as parents according to the elitist selection method.

Step 9 Check whether the maximum allowable number of generations NG is reached. If not, go to Step 4; otherwise, go to Step 10.

Step 10 Stop the process and output the best solution.

Proposed priority-random based encoding method

Conventional GA usually directly takes edges of a multigraph as 0/1 variables, and it is difficult to obtain a feasible path when solving large-scale 4plrp. This study proposes a priority-random based encoding method to solve this problem. Table 1 shows the specific decoding process.

Table 1.

The priority-random based encoding method.

Algorithm 1: The priority-random based encoding method
Input: Multigraph $G = (V, E)$ , with n nodes and m edges
Output: A complete route R from the source node to the destination node
1	The source and destination nodes of the multigraph are noted as $v_{1}$ and $v_{n}$ , respectively.
2	A non-repeating priority sequence from 1 to n is randomly generated as a decision variable
3	Candidate nodes for each node are generated based on the multigraph
4	The starting node is initialized: $v_{s} \leftarrow v_{1}$
5	The route is initialized: R $= {v_{s}}$ ,
6	while $v_{s} \neq v_{n}$ do
7	Among the candidate nodes of node $v_{s}$ , the node $v_{c}$ with the highest priority is selected as the next path node
8	An edge $e_{sck}$ between nodes $v_{s} v_{i}$ and $v_{c}$ is randomly selected
9	The path is updated: $R \leftarrow R \cup {e_{ick}, v_{c}}$
10	The priority of the node $v_{s}$ is set to 0
11	The start node $v_{s}$ is updated: $v_{s} \leftarrow v_{c} v_{i} \leftarrow v_{c}$
12	Return $R$

Figure 3 shows the process of generating the complete path of multiple undirected graphs in Figure 1, which is based on the priority-random based encoding method. Altogether, the multiple undirected graphs have seven nodes, where $v_{1}$ and $v_{7}$ respectively are the origin and destination nodes. First, each node is assigned a non-repeating integer ranging from 1 to n as a priority, and the priority sequence is used as the decision variable, so the dimension of the decision variable is seven. Second, the corresponding adjacent nodes (namely candidate nodes) to each node are generated according to the adjacent relation among the multiple undirected graph nodes. Third, the starting node $v_{s}$ is initialized to $v_{1}$ and included in path R. At this point, for the starting node $v_{s}$ (node 1), the candidate nodes are nodes 2 and 3, with priorities 1 and 3, respectively. The node with the highest priority $v_{c}$ (node 3) is selected as the next connection point, and then, the edge between nodes $v_{s}$ (node 1) and $v_{c}$ (node 3) is randomly selected as the path. Next, the priority of the node $v_{s}$ (node 1) is set to 0 to avoid loop formation. Node $v_{c}$ (node 3) is then updated to the starting node $v_{s}$ for the next encoding. The above steps are repeated until the starting node $v_{s} = v_{7}$ , and finally, a complete path from the origin to the destination node is obtained.

Figure 3.

The priority-random based encoding method.

Therefore, the priority-random based encoding method has the following advantages. (1) Compared with the conventional encoding method, the proposed method greatly reduces the dimension of the decision variable and improves the solution efficiency of the large-scale multigraph. (2) The path obtained by decoding is the complete path from the origin to the destination node, which improves the convergence of the algorithm. (3) The proposed decoding method has good portability and can be easily transplanted into an existing GA.

Fitness function

The fitness function, also known as the evaluation function, is a criterion for selecting high-quality individuals in a population according to the objective function. When solving the minimum value problem, the negative number of the objective function is usually taken as the fitness function of the algorithm. That is,

F = - Z

(12)

where $Z$ is the calculation result of equation (8). However, this method has some limitations. The calculated individual fitness value may have an unreasonable distribution problem, and reflecting individual characteristics is difficult. Therefore, this study conducted a scale transformation adjustment based on equation (12). The formula of fitness $F'$ is as follows:

{\begin{matrix} F' = a_{1} F + a_{2} \\ a_{1} = \frac{(a_{3} - 1) F_{avg}}{F_{\max} - F_{avg}} \\ a_{2} = \frac{(F_{\max} - a_{3} F_{avg}) F_{avg}}{F_{\max} - F_{avg}} \end{matrix}

(13)

Among them, $F_{avg}$ is the average fitness of the original, $F_{\max}$ is the maximum value of original adaptability, and $a_{3}$ is the best number of individual replication, with a range of 1.0–2.0. This study takes $a_{3} = 1.5$ .

Crossover and mutation operation

The general crossover method leads to repeated coding in the offspring, whereas the decision mutation in the proposed priority-random based encoding method is a non-repeating priority sequence. Hence, this study adopts a partial matching crossover (PMX) operation.²⁷ Figure 4(a) explains the specific process of PMX. First, two intersections are randomly generated, and the number mapping relationship between the two intersections is recorded. Then, the numbers between the two intersections in the parent generation are exchanged directly to generate the offspring. If the number already exists in a child, then the above mapping relation is used to replace it. When child 1 obtained after the direct exchange is 214|764| 6, 4, and 6 already exist, so 4 and 6 are replaced by 3 and 5 respectively according to the mapping relationship. The above replacement should be repeated if duplicate numbers still exist after replacement.

Figure 4.

Partially matching crossover operation and inversion mutation operation: (a) Partially matching crossover operation and (b) inversion mutation operation.

This study uses an inversion mutation operation, as shown in Figure 4(b). First, two mutation points are randomly generated. Second, the sequence between the two mutation points of the parent generation is directly reversed, and then, the offspring is obtained.

Notably, the offspring obtained by PMX and reversal mutation can still be decoded into a complete path from the origin to the destination node.

Selection operation

This study adopts two selection methods to improve the convergence of the algorithm, namely, tournament and elitist selection methods. First, select N individuals in the population according to the championship principle, that is, the parents. Then generate N offspring through crossover and mutation, and merge the offspring and the parents to form a 2N population. Finally, to retain the elite individuals in the population, the top N individuals with the highest fitness are selected based on the Elitist selection method, and then the selection operation is completed.

Example analysis

In this section, four sets of experiments verify the performance of the algorithm prSEGA in this paper on the 4plrp model. The first three sets of experiments compare the convergence speed, solution stability, and large-scale multigraph solving ability of prSEGA and six typical algorithms (elitist genetic algorithm (EGA),²⁸ strengthen elitist genetic algorithm (SEGA),²⁹ simple genetic algorithm (SGA),³⁰ generational gap simple genetic algorithm (GGAP-SGA),³¹ stud genetic algorithm (studGA),³² class-steady-state genetic algorithm (steadyGA)³³). The fourth group of experiments solves the models of different weight combinations to provide the optimal transportation scheme for 4pl companies. prSEGA adopts the feasibility rule to deal with constraints. The other six typical algorithms have poor convergence when solving the mathematical model in this study. So the penalty function method is used to deal with the constraints.

4plrp examples

The 4plrp can be represented by an undirected multigraph, as shown in Figures 1 and 2. The study uses the following method to generate some multigraphs.

Step 1. Generate n nodes. Nodes numbered 1 and n represent the source and destination, respectively. If the difference between the two node numbers is less than four, then six edges are generated between them to represent the combination of different 3pl and transportation methods.

Step 2. Randomly generate the waiting cost of goods per unit weight $C_{i}$ , the average number of vehicles arriving at the center in unit time $λ_{i}$ , the average service rate $μ_{i}$ , and processing capacity $P_{i}^{l, u}$ for each node, where $C_{i} \in [2, 5], λ_{i} \in [2, 7], μ_{i} \in [5, 10] and P_{i}^{l, u} \in [2, 5]$ .

Step 3. Randomly generate Euclidean distance $d_{ij}^{l}$ between two nodes, where $d_{ij}^{l} \in [150, 350]$ .

Step 4. Randomly generate the unit cost $C_{ijk}^{l}$ , unit time $T_{ijk}^{l}$ , transportation capacity $P_{ijk}^{l}$ , historical reputation $A_{ijk}^{l}$ for each edge, where $C_{ijk}^{l} \in [6, 15], T_{ijk}^{l} \in [3, 12], P_{ijk}^{l} \in [6, 15], A_{ijk}^{l} \in [8, 20]$ .

Five examples with 5, 10, 20, 50, and 100 nodes are generated to fully compare the performance of prSEGA and other six typical algorithms. In the five examples, the parameters are set as follows: the quality of the goods $q = 6$ , reputation indicators required by customers $A = 9$ .

Contrastive analysis of the convergence rate of the algorithm

For fairness in testing, the crossover rate, mutation rate, population size, and maximum evolutionary algebra of prSEGA and six typical algorithms are set to 1, 1, 80, and 100, respectively. For the mathematical model, the weight is set as $α_{1} = α_{2} = α_{3} = \frac{1}{3}$ . Figure 5 shows the test results of the five-node example. The objective function value calculated by prSEGA is relatively small. The reason is that the prSEGA adopts the priority-random based encoding method, and the obtained paths are all complete paths from the origin to the destination node. Considering that other algorithms cannot obtain the complete path, a penalty term is imposed on the objective function, so the objective function value is large. Among the six algorithms, the convergence value of SEGA is the lowest, but the path is illegal. Moreover, prSEGA has the fastest convergence speed (2nd generation) and the smallest convergence value (0.0423), so prSEGA is superior to other algorithms.

Figure 5.

Convergence speed diagram of seven algorithms.

Contrastive analysis of solution stability of the algorithm

In this section, algorithm parameters, mathematical model parameters, and numerical cases are consistent with Section 4.2. Then run these seven algorithms 10 times, take the convergence value and running time of each run, and visualize them to further compare the stability of each algorithm. Figure 6(a) shows that prSEGA obtains the same convergence value (0.0423) each time, and the convergence value is smaller than the other six algorithms. Figure 6(b) depicts that although steadyGA has the shortest running time, its convergence value is large, so the algorithm falls into the local optimal solution prematurely. Except for steadyGA, prSEGA has the shortest running time and stable running. PrSEGA can obtain the optimal solution in a stable time, that is, it is more stable than other algorithms.

Figure 6.

The stability of seven algorithms: (a) Convergence value of seven algorithms running 10 times and (b) Running time of seven algorithms running 10 times.

Effect of the problem scale on the algorithm

The paper chooses the four data of 10, 20, 50, and 100 nodes for testing to further compare the ability of these seven algorithms to solve 4plrp of different sizes. In the mathematical model, the weight is set as $α_{1} = α_{2} = α_{3} = \frac{1}{3}$ . Table 2 shows that the “Algorithm” represents the seven algorithms. “Nodes” and “Edges” represent the number of nodes and edges, respectively. These two parameters reflect the scale of the problem. The algorithms are run 10 times, and the parameters considered in the algorithms are population size “NP,” the number of generation “NG,” the best solution “Best,” the average value “Avg,” the Standard deviation “Std,” the average running time of the algorithm “Rtime,” and the average convergence algebra of the algorithm “AvgGen.”

Table 2.

The solution results of seven algorithms under different size 4plrp.

Algorithm	Nodes	Edges	NP	NG	Best	Avg	Std	Rtime/s	AvgGen
EGA	10	192	100	100	1.8	2.68	0.65	1055.93	42
SEGA	10	192	100	100	1.91	2.6	0.57	989.97	38.2
SGA	10	192	100	100	2.05	2.34	0.2	1081.42	57
GGAP_SGA	10	192	100	100	2.58	3.01	0.34	1096.83	39
studGA	10	192	100	100	6.04	6.61	0.48	1750.78	5.6
steadyGA	10	192	100	100	5.7	6.04	0.32	74.96	91.4
prSEGA	10	192	80	100	0.024	0.024	0	139.442	16.8
EGA	20	672	100	100	8.24	8.56	0.23	3468.09	50.2
SEGA	20	672	100	100	7.13	8.02	0.62	3204.64	41.6
SGA	20	672	100	100	7	7.58	0.52	3521.84	74.4
GGAP_SGA	20	672	100	100	8.04	8.55	0.44	3427.39	45
studGA	20	672	100	100	12.34	12.74	0.23	4363.08	7.4
steadyGA	20	672	100	100	11.84	12.62	0.47	178.15	85
prSEGA	20	672	300	100	0.062	0.068	0.003	1404.804	61.4
EGA	50	1152	100	100	42.02	42.54	0.6	11310.65	56.4
SEGA	50	1152	100	100	39.29	42.6	2.37	11053.95	46.2
SGA	50	1152	100	100	39.81	42.17	1.82	11673.24	87.4
GGAP_SGA	50	1152	100	100	43.32	45.29	1.36	11589.98	48
studGA	50	1152	100	100	52.31	53.57	0.66	12906.47	8.2
steadyGA	50	1152	100	100	50.98	53.17	1.26	496.47	86.6
prSEGA	50	1152	400	100	0.117	0.133	0.01	3179.923	85.2
EGA	100	2352	100	100	338.49	348.8	7.8	20873.52	53.6
SEGA	100	2352	100	100	335.23	346.65	8.44	20676.94	48
SGA	100	2352	100	100	331.81	338.56	4.18	21137.17	86.2
GGAP_SGA	100	2352	100	100	358.17	363.68	5.9	21476.71	43.6
studGA	100	2352	100	100	391.93	400.35	5.2	22771.99	6.4
steadyGA	100	2352	100	100	394.69	399.36	5.42	841.75	91
prSEGA	100	2352	700	100	0.08	0.154	0.042	5707.978	62.5

The bold values represent the solution results under different size 4plrp of the proposed algorithm prSEGA. In order to facilitate data comparison and highlight the advantages of the proposed algorithm, we use bold to indicate this set of data.

Table 2 shows that the “AvgGen” of all algorithms are less than the set “NG,” that is, all algorithms have converged under the set parameters. When the number of nodes is 10, the optimal solution “Best” of the other six algorithms is not less than 1.8. However, as shown in formula (8), the value of the objective function is no more than 1 on the premise that the optimal solution obtained is feasible. Therefore, these six algorithms have been unable to obtain a feasible solution. The prSEGA obtains the smallest convergence value (less than 1) when solving 4plrp of these four sizes, the “Std” is small, that is, the solution stability is great. In addition, prSEGA adopts the feasibility rule to deal with the constraints, so the resulting solutions are all feasible solutions. Furthermore, the solution time of prSEGA is usually less than that of other algorithms. Therefore, prSEGA can obtain better optimal solutions when solving small/large scale 4plrp.

Effect of $α_{1}$ , $α_{2}$ , and $α_{3}$ on the decision

In this section, the effect of $α_{1}$ , $α_{2}$ , and $α_{3}$ on the decision is tested with an example of five nodes. The crossover rate, mutation rate, population size, and maximum evolutionary algebra were set at 1, 1, 80, and 100 respectively. The algorithm runs five times and takes the minimum value as the final result. The greater the weight assigned to a sub-objective, the more the decision-maker is inclined to reduce the value of the sub-objective. Figure 7 shows the experimental results. The two data in the white box in the figure are taken as an example. Table 3 shows the corresponding path information. Taking the first set of data as an example, the weights assigned to sub-objective $Z_{1}$ , $Z_{2}$ , and $Z_{3}$ are 0.4, 0.5, and 0.1 respectively, and the resulting path is as follows: 1→1(3)→4→1(2)→7→2(2)→10, that is, starting from node 1, the 3pl supplier No. 1 uses the transportation mode (3) to transport the goods to node 4, and so on. The difference between the first and second groups of routes is that different 3pl suppliers and transportation modes are selected during the process from nodes 7 to 10. Table 4 shows detailed information. The transport capacity and reputation indexes of these two modes meet the constraints. According to the weights, the second group is more inclined to reduce the transportation time than the first group, so the No. 1 3pl supplier and transportation method (4) with shorter transportation time are selected.

Figure 7.

The optimal value under different weight coefficients.

Table 3.

Path information.

	weightings ( $α_{1} α_{2} α_{3}$ )	objective function value	Path
the first group	(0.4,0.5,0.1)	0.0311	1→1(3)→4→1(2)→7→2(2)→10
the second group	(0.4,0.6,0.0)	0.0192	1→1(3)→4→1(2)→7→1(4)→10

Table 4.

3pl supplier information.

Origin	destination	3pl supplier	transportation mode	unit cost	unit time	transportation capacity	historical reputation
7	10	2	(2)	6	7	11	17
7	10	1	(4)	8	3	10	19

Conclusion

Due to the limited size and manpower of the node center, the transportation task may not receive the service immediately. Hence, a queue waiting phenomenon may occur. To solve this problem, the process of transport vehicles arriving at node centers to receive services is assumed to be a queuing process. In addition, reducing carbon emissions is already imminent, and logistics enterprises should actively take practical actions to protect the environment. Therefore, this study establishes a path optimization model to minimize transportation cost, time, and carbon emissions based on the route, 3pl supplier, and transportation mode selection.

This study proposed a priority-random based strengthen elitist genetic algorithm to solve the infeasible solutions problem in 4plrp. The main innovation of this algorithm is to propose a priority-random based encoding method. That is, the dimension of the decision variable is equal to the number of multigraph nodes, and the decoded path is the complete path from the origin to the destination node. Besides, this encoding method has good portability and can be easily transplanted into existing GAs.

The proposed prSEGA is compared with the other six typical algorithms. The experiment shows that when solving the mathematical model in this study, these six algorithms all fall into the local optimal solution, and the paths obtained are all illegal. However, prSEGA has good convergence performance and solution stability when solving small/large 4plrp.

Under the background of big data, modern logistics often has evident randomness. In the future, the issue of 4plrp under uncertain conditions can be discussed.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research work is supported by the National Natural Science Foundation of China (Grant No. 71303094), the Key Research Project Sponsored by National Social Science (Grant No. 19AGL021), and the National Natural Science Foundation of China (Grant No. 71871105). The comments of the selfless reviewers are cordially appreciated.

ORCID iD

Wei Hong

References

Aguezzoul

. Third-party logistics selection problem: a literature review on criteria and methods. Omega 2014; 49: 69–78.

Cho

JJ-K

Ozment

Sink

. Logistics capability, logistics outsourcing and firm performance in an e-commerce market. Int J Phys Distrib Logist Manag 2008; 38: 336–359.

Tao

Chew

Lee

, et al. A column generation approach for the route planning problem in fourth party logistics. J Oper Res Soc 2017; 68: 165–181.

Qian

Huang

Zhang

, et al. Mechanism design of incentive-based reverse auctions with loss-averse 3PLs under incomplete attributes. PLoS ONE 2018; 13: 1–20.

Huang

Ren

Lee

, et al. 4PL routing optimization under emergency conditions. Knowl Based Syst 2015; 89: 126–133.

Huang

Ren

Lee

, et al. Model and algorithm for 4PLRP with uncertain delivery time. Inf Sci 2016; 330: 211–225.

Huang

. The optimization model and its algorithms for multiple transportation modes selection in the fourth party logistics. Adv Mat Res 2011; 383–390: 2249–2255.

Deng

Zheng

. Route optimization model in collaborative logistics network for mixed transportation problem considered cost discount based on GATS. J Ambient Intell Humaniz Comput 2019; 10: 409–416.

Cui

Huang

Yang

, et al. Fourth party logistics routing problem model with fuzzy duration time and cost discount. Knowl Based Syst 2013; 50: 14–24.

10.

Sivaramkumar

Thansekhar

Saravanan

, et al. Multi-objective vehicle routing problem with time windows: improving customer satisfaction by considering gap time. Proc IMechE, Part B: J Engineering Manufacture 2015; 231: 243–252.

11.

Chiti

Fantacci

Rizzo

. An integrated software platform for airport queues prediction with application to resources management. J Air Transp Manag 2018; 67: 11–18.

12.

Hammond

Crow

Hartman

. New management policies to improve the effectiveness of multi-station service organizations. Decis Sci 2010; 23: 1009–1022.

13.

Guo

. Strategic behavior and social optimization in partially-observable Markovian vacation queues. Oper Res Lett 2013; 41: 277–284.

14.

Geng

Liu

, et al. Stationary analysis for the fluid model driven by the M/M/cM/M/c working vacation queue. J Math Anal Appl 2013; 403: 423–433.

15.

Chen

Liu

, et al. Performance measurement system and strategies for developing low-carbon logistics: a case study in China. J Clean Prod 2017; 156: 395–405.

16.

Zhang

L-Y

Tseng

M-L

Wang

C-H

, et al. Low-carbon cold chain logistics using ribonucleic acid-ant colony optimization algorithm. J Clean Prod 2019; 233: 169–180.

17.

Morillo Torres

Barber

Salido

. A new model and metaheuristic approach for the energy-based resource-constrained scheduling problem. Proc IMechE, Part B: J Engineering Manufacture 2019; 233: 293–305.

18.

Wang

Zou

Wang

. A Tabu-GA-based parallel machine scheduling with restrained tool resources. Proc IMechE, Part B: J Engineering Manufacture. Epub ahead of print 25 June 2020. DOI: 10.1177/0954405420928691.

19.

Taherkhani

Basti

Nariman-Zadeh

, et al. Achieving maximum dimensional accuracy and surface quality at the shortest possible time in single-point incremental forming via multi-objective optimization. Proc IMechE, Part B: J Engineering Manufacture 2019; 233: 900–913.

20.

Kim

S-H

Jeon

, et al. A study on path optimization method of an unmanned surface vehicle under environmental loads using genetic algorithm. Ocean Eng 2017; 142: 616–624.

21.

Chen

Song

Xiu

, et al. Directed graph optimization model and its solving method based on genetic algorithm in fourth party logistics. In: Proceedings of the IEEE international conference on systems, man and cybernetics. Conference theme – system security and assurance, Washington, DC, 8 October 2003.

22.

Yan

Yujuan

Zujian

, et al. A hybrid method combining genetic algorithm and Hooke-Jeeves method for 4PLRP. In: Proceedings of the 2014 IEEE/CIC international conference on communications in China-workshops (CIC/ICCC), Shanghai, China, 13 October 2014, pp.36–40. New York: IEEE.

23.

Liu

Zhang

Zhu

, et al. Novel multi-objective resource allocation and activity scheduling for fourth party logistics. Comput Oper Res 2014; 44: 42–51.

24.

Lin

Gen

. Priority-based genetic algorithm for shortest path routing problem in OSPF. In: Gen

Katai

McKay

, et al. (eds) Intelligent and evolutionary systems. Heidelberg: Springer, 2009, pp.91–103.

25.

Yao

C-Z

Lin

J-N

Liu

X-F

, et al. Dynamic features analysis for the large-scale logistics system warehouse-out operation. Physica A 2014; 415: 31–42.

26.

Kumar

Sharma

Singh

. Bidirectional multi-optical line terminals incorporated converged WSN-PON network using M/M/1 queuing. Opt Fiber Technol 2017; 39: 78–86.

27.

Ting

Lee

. Multi-parent extension of partially mapped crossover for combinatorial optimization problems. Expert Syst Appl 2010; 37: 1879–1886.

28.

Gero

MBP

García

del Coz Díaz

. A modified elitist genetic algorithm applied to the design optimization of complex steel structures. J Constr Steel Res 2005; 61: 265–280.

29.

Hsieh

S-T

Sun

T-Y

Liu

C-C

. Potential offspring production strategies: an improved genetic algorithm for global numerical optimization. Expert Syst Appl 2009; 36: 11088–11098.

30.

Vose

. Modeling simple genetic algorithms. Evol Comput 1995; 3: 453–472.

31.

Xibo

Weili

. Adaptive genetic algorithms based on generational gap information. J Southeast Univ (Natural Science Edition) 2004; 34: 53–57.

32.

Eiben

Schoenauer

Schwefel

. Parallel problem solving from nature. In: Proceedings of the 5th international conference, Amsterdam, 27–30 September 1998.

33.

El-Shorbagy

. A hybridization of sine cosine algorithm with steady state genetic algorithm for engineering design problems. In: Hassanien

Azar

Gaber

, et al. (eds) International conference on advanced machine learning technologies & applications. Cham: Springer, 2019, pp.143–155.

Queuing theory-based optimization research on the multi-objective transportation problem of fourth party logistics

Abstract

Keywords

Introduction

Problem description and mathematical modeling

Problem description

Model assumptions

Parameter definition

Model establishment

Algorithm design

Proposed priority-random based encoding method

Fitness function

Crossover and mutation operation

Selection operation

Example analysis

4plrp examples

Contrastive analysis of the convergence rate of the algorithm

Contrastive analysis of solution stability of the algorithm

Effect of the problem scale on the algorithm

Effect of α 1 , α 2 , and α 3 on the decision

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References

Effect of $α_{1}$ , $α_{2}$ , and $α_{3}$ on the decision