Multi-objective Optimization Genetic Algorithm for Multimodal Transportation

Abstract

The multimodal transportation is an effective manner in reducing the transportation time and cost. However, the programming of multimodal transportation is very complex and belongs to NP difficulty problems. Therefore, an optimal model based on the graph structure was firstly formulated for the multimodal transportation with two optimal objectives including the transportation time and the transportation cost. An optimized algorithm with two layers was then proposed after characterizing the formulated model. The upper level was applied to find the global optimal Pareto fronts and the transportation path, whereas the lower level was to find the optimal path and the transportation manner. At last, a numerical simulation was performed to validate the model and the proposed algorithm. The results show that the proposed algorithm can find a series of Pareto front solutions, which indicates that the formulated model and proposed algorithm are effective and feasible.

1 Introduction

As the economic globalization continues to intensify, resources, products, and markets are scattered all over the world. Market demands are changing rapidly and competition is becoming increasingly fierce. How to make all members in the logistics business closer to each other in the supply chain? The information in the process of business processing is highly integrated to achieve collaborative operation of the supply chain, shorten the relative length of the supply chain, make the logistics business on the supply chain smoother, yield higher, and respond faster. Meeting the needs of customers has become an urgent issue in management science and engineering. The multimodal operation is an important task of logistics and transportation organization and has become an effective measure for the fourth party logistics company to improve its competitiveness and thus reduce logistics costs. Compared to a single mode of transport, multimodal transport can increase efficiency, enhance safety and flexibility, and at the same time meet the requirements of the cargo carrier. However, compared to a single mode of transport, due to multi-participation, multiple objectives need to be taken into account. This makes multimodal transportation planning much more complicated and difficult. Therefore, it is very important to develop a multi-objective optimization algorithm for multimodal transportation planning.

At present, scholars have studied the modeling and algorithm problems of multimodal transport planning from different perspectives. However, most of works belong to single-objective optimization problems. There are few studies on multi-objective optimization problems that consider cost and transit time. For example, Angelica Lozano et al. [1] studied the shortest feasible path problem under multimodal transportation and solved it by using the sequential algorithm. Boussedjra and Moudni [2] adopted a bi-directional research strategy to establish an intermodal transport network model and presented the shortest path algorithm between source and destination. Some scholars consider multi-objective optimization when passengers use multiple transport modes. Brands et al. [3] studied the multi-objective optimization problem of multimodal passenger transportation in urban passengers considering uncertain demand. The results show that the demand is uncertain. The Pareto frontier solution of multi-objective optimization has a great influence on them. They [4] also applied this algorithm to solve multimodal network design problems. Zhang et al. [5] applied the uncertain optimization method to study the shortest path of passenger multimodal transport. They considered the difference in transit time and transportation cost caused by the uncertainties of different transport modes. The goal of the double-objective optimization problem was verified by numerical methods. Osuji et al. [6] studied the multi-objective transportation problem based on fuzzy optimization. Zhang et al. [7] proposed a generalized shortest path algorithm for solving optimal transportation routes based on the multimodal transport model established by Reddy. Wei et al. [8] considered the time-varying conditions of cost, transit time, and risk in the transportation process, and established the short-circuit model of time-varying multimodal transportation through the deformation of the transportation network and solved it. Zhang et al. [9] established an optimal distribution model for multimodal transport networks, and quantitatively analyzed the rational organization mode of multimodal transport to minimize total costs. Wang et al. [10] proposed an optimization model for transportation modes based on the analysis of the transport characteristics of various transportation modes and presented a solution algorithm. Wei et al. [11] established the shortest time path-transportation cost model for multimodal transportation, and proposed the iterative algorithm to solve the shortest path. Yang et al. [12] studied the multimodal transport model with time windows, proposed a bi-level optimization model, and used ant colony algorithm to achieve path optimization. These studies have established and solved the multimodal transport model for a single logistics transport task under certain conditions, which belongs to the single-objective optimization problem.

From the above analysis, it can be seen that there are still few researches on the multi-objective optimization of logistics multimodal transport planning problems. The research on modeling methods and algorithms still needs to be in-depth. Therefore, based on the previous research [13], this paper intends to investigate multi-objective modeling and solving algorithms for multimodal transport planning. In the previous research, considering the integration of multimodal transport and multi-agent logistics operations with time windows, a multimodal transportation optimization model based on graph structure was established and a two-layer search algorithm was designed to solve it. For further in-depth research, this paper proposes to build a multi-objective optimization model based on a multimodal transport network that considers transportation time and transportation cost in Sect. 2. In Sect. 3, a two-layer multi-objective hybrid Taguchi algorithm is proposed. The numerical examples verify the established models and algorithms in Sect. 4. Section 5 will conclude it.

2 Modeling of Multimodal Transportation

In order to facilitate modeling and analysis, the virtual network is defined as follows. Let G = (V, E, M) be the network graph under consideration. It is the abstraction of logistics nodes and traffic connections in the geographical map under consideration. V is a set of the nodes in the actual logistics transportation network correspond. E is a set of edges, corresponding to all possible transportation paths. M is a collection of transportation modes. To facilitate problem solving, the following assumptions are made.

Hypothesis 1 the same shipment cannot be transported separately;

Hypothesis 2 there are multiple modes of transport between two adjacent transfer stations to choose from, but only one mode of transport can be selected;

Symbol description:

x _ijm :

commodity is shipped at (i, j) with mode m;

$c_{ijm}$ :

unit shipment price of commodity at (i, j) with mode m;

d _ijk :

shipment length at (i, j) with mode m;

$v_{m}$ :

unit shipment velocity for mode m;

$tt_{ikl}$ :

the unit transfer time from mode k to l at node i;

$tc_{ikl}$ :

the unit transfer cost from mode k to l at node i;

$\omega_{i}^{kl}$ :

changing sign from mode k to l at node i;

$q_{ijm}$ :

Commodity volume at (i, j);

$D_{i}$ :

Schedule time at node i, $D_{i}$ = 0 for no schedule time;

G = (V, E, M) is a multimodal transport network with time windows, which includes reducing total transportation time and transportation costs. The decision variables are $x_{ijm}$ and $\omega_{i}^{kl}$. The multi-objective optimization model with the goal of transportation cost and transportation time is as follows:

$$ {{Z_{1} = \hbox{min} \left\{ {\sum\limits_{ij} {\sum\limits_{m} {c_{ijm} q_{ijm} d_{ijm} x_{ijm} } } + \sum\limits_{ij} {\sum\limits_{i} {\sum\limits_{kl} {q_{ijm} \omega_{i}^{kl} tc_{ikl} } } } } \right\}}} $$

$$ Z_{2} = \hbox{min} \left\{ {\sum\limits_{ij} {\sum\limits_{m} {d_{ijm} /v_{m} } } + \sum\limits_{ij} {\sum\limits_{i} {\sum\limits_{kl} {\hbox{max} (D_{i} ,q_{ijm} tt_{ikl} )} } } } \right\} $$

(1)

S.T.

$$ \sum\limits_{j} {q_{ijm} - \sum\limits_{i} {q_{jim} } } = \left\{ {\begin{array}{*{20}c} {Q\quad \,\,\,\,if\,i = O\,} \\ { - Q\quad if\,i = D} \\ {0\quad \;\;otherwise} \\ \end{array} } \right.\,\,\,\,\forall \;i \in V,\;m \in M $$

(2)

$$ \hbox{max} (D_{i} ,q_{ijm} tt_{ikl} ) + d_{ijm} /v_{m} - A_{j} = 0\,\,\,\forall \;i,\;j \in V,\;(i,\;j) \in E,\;m \in M $$

(3)

$$ l_{i} \le A_{i} \le u_{i} ,\,\,\forall \;i \in V $$

(4)

$$ \sum\limits_{m} {x_{ijm} } \le 1\,\,\,\forall \;(i,\;j) \in E,\,\,m \in M, $$

(5)

$$ \omega_{i}^{kl} = \left\{ {\begin{array}{*{20}l} 1 \hfill & {k \ne l} \hfill \\ 0 \hfill & {k = l} \hfill \\ \end{array} } \right., $$

(6)

$$ x_{ijm} \in \{ 0,\;1\} \,\,\forall \;(i,\;j) \in E,\,\,m \in M. $$

(7)

The first optimization objective function in Eq. (1) is to reduce the total transportation cost, and the second optimization goal is to reduce the total transportation time. Equation (2) is the traffic balance condition in the network flow. Formula (3) ensures the tolerance of time requirements. Equation (4) represents that the node should meet the predetermined time window constraints. Formula (5) indicates that there is at most one transport mode for each link. The values of variables (6) and (7) are limited.

3 Multi-objective Genetic Algorithm Based on Time Window

In order to make the multimodal transportation model closer to the real scene, we studied the customized time window, the transportation distances of different transportation modes, different transportation speeds, the conversion costs and conversion time of different nodes, which is different from the previous issue of multimodal transportation routes. There are multiple edges between some nodes. Moreover, once the mode of transportation has changed at certain nodes, additional conversion costs and time are still included. The problem has become very complicated, and the key is to find it difficult to find a best multimodal transport network. Therefore, a two-layer multi-objective hybrid Taguchi algorithm is proposed to find the optimal transport path.

The dual-layer multi-target hybrid Taguchi algorithm consists of two layers. The upper layer aims to find the overall global optimal Pareto frontier and transportation mode, while the lower layer searches for the local optimal Pareto frontier of the fixed path and transport mode. The lower level optimization method determines the upper feasible solution space. The multimodal transport path problem model can be reduced to the following two-level multi-objective optimization problem.

$$ \min_{{(x_{ijm} ,\omega_{i}^{kl} )}} Z = \{ Z_{1} ,Z_{2} ) $$

S.T.

$$ \omega_{i}^{kl} \in \arg \min_{{\omega_{i}^{kl} }} \{ Z_{1} ,Z_{2} \} , $$

(8)

$$ \sum\limits_{j} {q_{ijm} - \sum\limits_{i} {q_{jim} } } = \left\{ {\begin{array}{*{20}c} {Q\quad \,\,\,\,if\,i = O\,} \\ { - Q\quad if\,i = D} \\ {0\quad \;\;otherwise} \\ \end{array} } \right.\,\,\forall \;i \in V,\;m \in M, $$

(9)

$$ \hbox{max} (D_{i} ,q_{ijm} tt_{ikl} ) + d_{ijm} /v_{ijm} - A_{j}^{{}} = 0,\,\,\forall \;i,\;j \in V,\;(i,\;j) \in E,\;m \in M, $$

(10)

$$ l_{i} \le A_{i} \le u_{i} ,\,\,\forall \;i \in V, $$

(11)

$$ \omega_{i}^{kl} = \left\{ {\begin{array}{*{20}l} 1 \hfill & {k \ne l} \hfill \\ 0 \hfill & {k = l} \hfill \\ \end{array} } \right., $$

(12)

$$ \sum\limits_{m} {x_{ijm} } \le 1\,\,\,\,\forall \;(i,\;j) \in E,\,\,\,m \in M, $$

(13)

$$ x_{ijm} \in \{ 0,\;1\} \,\,\forall \;(i,\;j) \in E,m \in M. $$

(14)

3.1 Solution Algorithm for the Upper Level

The task of this layer is to find the global Pareto frontier and provide effective and feasible transport paths for the lower levels. As far as multimodal transport path optimization is concerned, if network agents have only one mode of transport to choose from, the shortest path algorithm should be the optimal solution. Taking into account the existence of various modes of transport, it is very difficult to directly apply the k shortest path algorithm. To this end, multimodal transport networks are transformed, standardized, and weighted.

• Algorithm 1. Initial feasible path population generation

  • Step 1: Read the data of the multimodal network.

  • Step 2: Calculate the normalized weighting matrix according to the weights

  • Step 3: Calculate k shortest paths using the K-shortest path algorithm

• Algorithm 2. Check and replace operation

  • Step 1: If the path is feasible, stop it;

  • Step 2: Generate a random weight factor. Calculate normalization matrix and apply K shortest path algorithm to calculate k shortest paths;

  • Step 3: Select a feasible path from the K feasible paths to replace the infeasible path.

3.2 Optimization Algorithm for the Lower Transportation Mode

Since the position of the Pareto front before the optimization is not known, it is hoped that the chromosomes of the initial population can be evenly dispersed throughout the feasible solution space, and there is a potential advantage of using the Taguchi experimental method to generate these chromosomes.

• Algorithm 3. Generation of the initial population of transport modes

  • Step 1: Read the path provided by the upper layer

  • Step 2: All the edges in the path have the same transport method available? If applicable, apply to select chromosomes and go to step 4. If not, go to step 3

  • Step 3: Divide the path into several sections based on the same available transport method. Sides with the same available transport methods are connected together. Each section chooses its own orthogonal table.

  • Step 4: Calculate the shipping cost and time for each chromosome.

  • Step 5: Sort the chromosomes according to the fast non-dominated sorting method.

  • Step 6: Select the chromosome based on chromosome rankings.

The Taguchi experiment method also incorporates crossovers in order to inherit good genes from the father. This article uses a two-level orthogonal array with l factors, where l is the length of the feasible path. Two levels correspond to the parents of two chromosomes.

• Algorithm 4. Crossing based on taguchi experimental method

  • Step 1: Randomly select the parents of the two paired pools;

  • Step 2: Select the orthogonal table according to the length of the chromosome;

  • Step 3: Use orthogonal experiments to generate progeny;

  • Step 4: Sort children according to the fast non-dominated sorting method;

  • Step 5: Select two chromosomes based on the chromosomes.

3.3 Two-Level Multi-target Taguchi Genetic Algorithm

Based on the above analysis, the two-level multi-object Taguchi genetic algorithm can be summarized as follows.

• Algorithm 5. Bi-level multi-target Taguchi genetic algorithm

  • Step 1: Read the array and graphics structure. Read the initial value of all parameters.

  • Step 2: parameter settings: For the upper level, including population size, crossover rate and mutation rate. For the lower layer, population size, crossover rate, mutation rate

  • Step 3: Apply algorithm 1 to generate the initial population of feasible paths

  • Step 4: Upper Population Evolution

  • If (stopping conditions are not met) proceed

  • Start

  • Step 4.1: Apply Algorithm 3 to generate the initial population of transport methods for each feasible path

  • Step 4.2: Lower population evolution

  • If (stopping conditions are not met) proceed

  • Start

  • Step 4.3: Select: Select chromosomes to cross, crossover probability. Continue to choose until the number of selected chromosomes is half of it.

  • Step 4.4: Crossover: Crossing selected chromosomes using algorithm 4

  • Step 4.5: Variation: The probability of variation in each chromosome

  • Step 4.6: Sort all chromosomes using fast non-dominated sorting

  • Step 4.7: Keep the next generation of the previous chromosome

  • End

  • Step 5: Select: Intersect each chromosome with crossover probability. Continue to choose until the selected number of chromosomes reach to half of it

  • Step 6: Cross: Crosses the selected chromosome. If the crossed path is feasible, then go to Step 8

  • Step 7: Execute Algorithm 2

  • Step 8: Variation: The probability that each chromosome will mutate. If the crossover path is feasible, then go to Step 10.

  • Step 9: Execute Algorithm 2

  • Step 10: Use the fast non-dominated sorting method to sort all chromosomes

  • Step 11: Preserve the next chromosome of the next generation

  • End

4 Numerical Simulation

In order to verify the models and algorithms constructed, based on the logistics network in Eastern China, it is assumed that there are a batch of containers that need to be transported. The transport can be carried out in 35 city nodes. The transportation methods include roads, railways and waterways, but not all cities have three links. An example was constructed with 35 nodes and 136 edges. Figure 1 shows the map of logistics and transportation in eastern China. Many major cities along the Yangtze River rely on waterways, railroads and trucks for transportation. There is a simple and effective model in the multimodal network environment. The model can provide some good trade-off solutions. These nodes next to the Yangtze River can be connected to each other by barges, such as to nodes 1, 3, 9, …, 93. The following parameters $G_{1} = 220,\,p_{c1} = 0.1,\,\,p_{m1} = 0.1,\,\,G_{2} = 50,\,\,p_{c2} = 0.2\,\,{\text{and}}\,\,p_{m2} = 0.2$ are used in the simulation. The stop condition is simply to reach the highest iteration of the predetermined upper and lower levels. The two predetermined maximum iterations are 20 generations.

Fig. 1.

Logistics transportation network in China eastern region

There are three common modes of transportation, namely roads, railways and waterways. The total transportation costs include transportation costs and transportation costs. The mode of transportation determines the cost of transportation. Transit costs include labor costs and equipment costs during transportation. The transfer container is a standard container, 8 feet high, 8 feet wide and 20 to 55 feet long. Containers can be transported by trucks, railroads and barges. In general, containers can hold 15 tons. Because there is no universal standard to describe the shipping rate, transshipment rate, transportation speed and transit time. This article uses the relevant data provided by [14] as the basis for calculation, as shown in Tables 1, 2 and 3. The transport rates and speeds given in Table 1 are shown in Tables 2 and 3, respectively.

Table 1. Transportation rates and speed

Table 2. Transfer rate (cost for each container)

Table 3. Transfer time (time for each container)

Consider one task is 1000 containers from node 1 (Shenzhen) to node 93 (Dandong). The goods are more focused on the quality of transportation. Assuming that the transportation continues until it reaches the destination, simulations are performed. The results are shown in Fig. 2. The Pareto solution and other non-dominated optimal solutions are given in the figure. These solutions become alternatives to the carrier’s decision. The carrier needs to select according to the shipper’s requirements (Table 4).

Fig. 2.

No-dominated solution plan

Table 4. Transportation path and manner from Shenzhen to Dandong

5 Conclusion

A multi-objective modelling and optimization algorithm for multi-modal transport optimization of fourth-party logistics was proposed. Based on the description of model problems, a multi-objective optimization model for multimodal transport planning with time window constraints was established using graph-like structures. The optimization of different task requirements was solved. The calculation results show that the algorithm can solve a series of Pareto frontier solutions that meet the requirements based on the user’s demand for transportation time and transportation costs. This shows that the proposed algorithm is feasible and effective. This article does not consider the issue of the transfer of jobs between agents. This will be investigated further in the future.