Research on Logistics Distribution Routing Optimization Based on Ant Colony Algorithm

Abstract

Logistics distribution is the core of logistics, and the optimization of vehicle routing problem is the key to logistics path optimization. Choosing a reasonable delivery route is of great significance for improving the efficiency of logistics distribution and reducing logistics cost. In view of the choice of logistics distribution route, first of all, introduce the traveling salesman problem (TSP problem), introduce the ant colony algorithm and build its mathematical model. Secondly, the important parameters in the ant colony algorithm are tested and analyzed, and the reasonable range of value is determined. Finally, taking the logistics of Nan gang District of Harbin as an example, the use of Matla B simulation results show that the scheme can optimize the logistics distribution route and improve the delivery efficiency.

1 Introduction

In recent years, with the economic globalization and the deepening of China’s economic system reform, modern logistics distribution has gradually become the core industry requirement to promote the development of our country’s economy. The quality of logistics distribution plan determines the efficiency of logistics distribution to a large extent. In October 2016, the office of the State Council issued the opinion on the policies and measures to promote the healthy development of the logistics industry. It pointed out that the efficiency of logistics distribution should be improved, the competitiveness of logistics enterprises increased, and the policy support for the logistics industry was strengthened so as to promote the healthy and efficient development of the logistics industry. Therefore, in order to optimize the logistics transportation route and choose a reasonable distribution plan, it is necessary to study the optimization of logistics distribution route.

In academic circles, the study of solving the optimization of logistics distribution path has attracted extensive attention of many researchers at home and abroad, such as mathematics, computer communications, and so on. Among them, foreign comparisons are representative: Dantzig and Rmaser [1] proposed the optimization of logistics distribution path for the first time in 1959. The problem is quickly aroused by experts from various disciplines such as world operations research, logistics science, combinatorial mathematics and other related people, and become the front of operations research and combinatorial optimization. Along problems and research hot spots; In 1989, Willard [2] applied the tabu search method to vehicle routing optimization for the first time. By designing a repetitive virtual logistics center, the vehicle routing optimization problem was transformed into a traveling salesman problem, and the 2-opt method was used to solve the vehicle routing optimization scheme. In 1995, the research progress and development of vehicle routing problems were discussed in eighth volumes published in the book “operations research and management science manual”, which was published by Desrosiers [3]. In 2008, Donati [4] and other ant colony algorithms were used to study vehicle routing problem with vehicle speed varying with time. In contrast, the domestic research on this aspect is relatively backward in the early 1990s, but it has been developed in the early 1990s, but there are also some research results on the optimization of vehicle distribution path. It is more representative: in 2001, Chen [5] proposed a hybrid operator in genetic algorithm to improve the ant colony algorithm and proved the algorithm to be effective by solving the TSP problem. In 2006, Lang [6] reviewed the latest progress of the vehicle routing optimization problem in the distribution vehicle optimization scheduling model budget method. In 2012, Wang [7] and so on proposed improved ant colony algorithm and introduced heuristic factor and parameter adaptive adjustment. In 2013, Li [8] and so on pointed out the superiority of ant colony algorithm in solving the problem of large nonlinear system optimization, and improved the basic ant colony algorithm according to the characteristics of the logistics vehicle scheduling system and proved the algorithm. The correctness of it. To sum up, the research on the distribution path is mainly qualitative, and the quantitative research mainly focuses on the improved ant colony algorithm itself, and the research on the setting and optimization of the algorithm parameters is very few. Based on the policy of national logistics industry, this paper aims to select the rational distribution route and optimize the logistics distribution path, and tries to introduce the optimization problem of the traveler (TSP problem) to explain the ant colony system model, and verify the parameter value of the ant colony algorithm through the simulation experiment, and determine the selection range of the parameter value. At the same time, taking the logistics of SF in Nangang District of Harbin as an example, the Matlab tool simulation experiment is used to optimize the route. Finally, the aim of this paper is to optimize the logistics distribution path based on ant colony algorithm.

2 Analysis of TSP Problem Based on Ant Colony Algorithm

2.1 TSP Problem Definition and Mathematical Description

The traveling salesman problem (TSP problem) introduced in this paper is a special case of path optimization. In recent years, because of its simplicity and adaptability, the TSP problem has been used as a testing platform for new ideas and methods for solving combinatorial optimization problems. The essence of this is that for n cities, the distance between them is known, and a traveler travels from one city to all the cities, and each city can only pass once, finally back to the starting point, so that the total distance is shortest. The mathematical method is described as: a collection of n cities $C = \{ c_{1,} c_{2,} \ldots c_{N} \}$, the distance between each city is $d(c_{i,} c_{j} ) \in R^{ + }$,$c_{i,} c_{j} \in C(1 \le i,j \le N)$.

Objective function: $T_{D} = \sum\limits_{I = 1}^{N - 1} {d(c_{\Pi } (i),c_{\Pi } (i + 1))} + d(c_{\Pi } (N),(c_{\Pi } (1))$.

The smallest city sequence: $\{ c_{\varPi } ( 1),c_{\Pi } ( 2), \ldots c_{\Pi } ({\text{N}})\}$, Among them, $_{\Pi } ( 1),_{\Pi } ( 2), \cdots_{\Pi } ({\text{N}})$ is the full arrangement of $1,2, \ldots N$.

2.2 Overview of Ant Colony Algorithm and Implementation Steps of Solving TSP Problem

2.2.1 An Overview of Ant Colony Algorithm

Ant colony algorithm is a probabilistic algorithm for finding optimal paths. In 90s of last century, Italy scholar M. Dorigo simulated the path selection method of ants searching for food, and then came to an algorithm. As a bionic algorithm, ant colony algorithm has strong robustness. It is easy to integrate with other algorithms to improve the performance of the algorithm. Global optimization has become a powerful tool for solving complex combinatorial optimization problems. In recent years, there are many ways to study path optimization based on genetic algorithm and particle swarm optimization, in which the genetic algorithm has good global search ability, but it has no characteristics of active optimization and has no memory. Although particle swarm optimization can effectively optimize the parameters of the system, its local optimization ability is poor; Therefore, ant colony algorithm is the first choice for path optimization.

To facilitate the description of the ant colony model, first define the following variables:

M:

Ant number;

n:

Number of cities;

$d_{ij}$ :

Distance between (I, j)cities, $i,j = 1,2, \ldots ,n$;

$\zeta_{ij}$ :

The number of pheromones on the t time path (i, j), $i,j = 1,2, \ldots ,n$;

$\varphi_{ij}$ :

The visibility of the path reflects the degree of Enlightenment from the city to the city, $\varphi_{ij} = \frac{1}{{d_{ij} }}$;

$\alpha$ :

The number of pheromones on the t time path;

$\beta$ :

The relative importance of enlightening information;

$\rho$ :

Pheromone Volatilization Coefficient;

$\Delta \zeta (i,j)$ :

The amount of information added to a path (I, J) in a cycle;

$\Delta \zeta_{ij}^{k}$ :

The pheromone intensity of ant K placed on the edge of L (I, J);

$p_{ij}^{k} (t)$ :

The probability of an ant turning from a city to a city at a time;

$tabu_{k}$ :

The amount of pheromone remained in the path passed by the ants in another iteration;

$Q$ :

Taboo table, record the city where ants are walking now, and will not choose cities from the table next visit.

2.2.2 The Steps to Solve the TSP Problem

Based on the above variables, the optimization steps of ant colony algorithm are summarized as follows:

Step 1: parameter initialization

Initialization parameters m, α, β, ρ, Q, Command t = 0, Cycle times Nc = 0, The maximum cycle number is $Nc_{\hbox{max}},$ The amount of information on each path at the initial time is $\zeta_{ij} (0) = C$ (C is a constant), $\Delta \zeta_{ij} (0) = 0$.

Step 2: construction path

M ants are randomly placed in n cities, and the taboo list of each ant is updated to make the first element the ant’s current city.

Step 3: determine the transfer probability

At t, the probability of ant K moving from city to next city is:

$$p^{k} \left( {{\text{i}},{\text{j}}} \right) = \left\{ {\begin{array}{*{20}l} {\frac{{\left[ {\zeta \left( {i,j} \right)} \right]^{\alpha } *\left[ {\varphi \left( {i,j} \right)} \right]^{\beta } }}{{\mathop \sum \nolimits_{{s \in J_{k} \left( t \right)}} \left[ {\zeta \left( {i,s} \right)} \right]^{\alpha } *\left[ {\varphi \left( {i,s} \right)} \right]^{\beta } }}if\,j \in J_{k} } \hfill & {} \hfill \\ {0 } \hfill & {otherwise} \hfill \\ \end{array} } \right.$$

At the same time, the j is put into the taboo table of ant K, so cycle, until all the ants complete the tour of the n city; $J_{k}$ indicates that the next step can allow access but not access to the logistics point;

Step 4: determine the path length

Calculate the travel path length $L_{k} (k = 1,2, \ldots m)$ of each ant, and record the current optimal traversal sequence and path length.

Step 5: pheromone update

After all ants find a legal path, they update the information:

$$\zeta_{ij} \left( {t + 1} \right) = \left( {1 - p} \right)\zeta_{ij} \left( t \right) + \sum\nolimits_{m} {\zeta_{ij}^{k} \left( {t,t + 1} \right)}$$

(2)

$$\vartriangle \zeta_{ij}^{k} \left( {{\text{t}},{\text{t}} + 1} \right) = \left\{ {\begin{array}{*{20}l} {\frac{Q}{{L_{k} }}} \hfill & {If\, the\,ant\,passes \left( {i,j} \right)} \hfill \\ 0 \hfill & { otherwise} \hfill \\ \end{array} } \right.$$

Among them, Q indicates that the trajectory of ants is normal (101000). ${\text{L}}_{k}$ indicates the length and the path of the ant K in this tour.

Step 6: to each side $(i,j)$, $\Delta \zeta_{ij} = 0$, $Nc = Nc + 1$.

Step 7: judge whether $Nc$ reaches $Nc_{\hbox{max} }$, if $Nc \le Nc_{\hbox{max} }$, then turn to Step 2; otherwise, go to step 8;

Step 8: output results. The optimal solution of this experiment is output.

Based on the description of the model above, the operation flow chart of the ant colony algorithm is compiled, as shown in Fig. 1.

Fig. 1

Flow chart of the running program of ant colony algorithm

3 Optimization and Analysis of Parameter Setting of Ant Colony Algorithm

From the above mathematical model, we can see that if the parameter is not set properly, it will lead to slow solution and poor quality of the solution. Therefore, the determination of reasonable parameter values will help to improve the convergence speed and global optimization ability of the algorithm. In the ant colony algorithm, there are mainly three parameters that affect the performance of the algorithm, that is, pheromone elicitation factor α, expected heuristic factor β and pheromone volatilization coefficient ρ. Based on this, this paper mainly analyzes and tests the three parameters of alpha, beta and Rho, and then determines the reasonable value.

3.1 Pheromone Elicitation Factor Alpha and Expectation Heuristic Factor Beta Analysis

Pheromone heuristic factor alpha reflects the intensity of the information accumulated by ants in the process of movement to the leading role of the following ants. It also reflects the intensity of the ants’ effect on the random factors in the path search: the greater the alpha value, the stronger the amount of information accumulated for the path selection of the succeeding ants. The possibility of ants to choose the previous path is greater, the ant cooperation is strengthened and the convergence speed is quicker, but the search randomness is weakened, the search space becomes smaller and the algorithm is easily trapped in the local optimal, which will reduce the global search ability of the algorithm, and when the alpha value is too low, the search speed will be reduced, which will lead to the algorithm difficult to find. The global optimal solution [9], the general alpha value range is 0.5–5.

Beta reflects the strength of the ant’s path length to the ants’ guiding role in the course of the movement. The greater the beta value, the stronger the guiding role of the heuristic information to the ants’ path selection, the faster the algorithm converges, but it weakens the randomness of the ant colony in the optimal path search, and the algorithm is easy to fall into the local optimal, and when the beta value is too small It will make the ant quickly fall into local optimum, greatly reducing the global optimization ability of the algorithm [9], the value of the general beta is 1–5.

In this paper, the effect of alpha and beta on the performance of ant colony algorithm is discussed. When taking beta = 5, the alpha is {0.5, 1, 2, 5}, and the other default values are: n = 15, m = 22, Q = 100, Nc = 200, P = 0.1. The data used in the experiment are derived from the Eil51 city problem, and the data are detailed in Appendix 1. The results of the experiment are shown in Table 1.

Table 1 Simulation results of combination of alpha and beta algorithms

When the alpha = 1 is taken, the beta is {1, 2, and 5}, and the other default values are n = 15, m = 22, Q = 100, Nc = 200, and Rho = 0.1, and the TSP problem data used in the experiment is derived from the Eil51 city problem. The results of the experiment are shown in Table 2.

Table 2 Simulation results of combination of alpha and beta algorithms

The experimental results show that if the fast convergence performance of the ant colony algorithm is increased and the accuracy of the search process is required, the combination of alpha and beta values should be selected at the same time. Therefore, based on the experimental results, the parameter values in this paper are selected as: alpha = 1, beta = 5.

3.2 Numerical Analysis of Pheromone Volatiles

The size of Rho is directly related to the global optimization ability and convergence speed of the ant colony algorithm. In general, the number of [0, 1] and 1- Rho represent the degree of the pheromone’s retention, which indirectly reflects the strong and weak relationship between the ants. The greater the value of Rho, the more volatile of the path pheromone, the less the residual pheromone on the path, the smaller the attractiveness to the subsequent ants, the weakening of the collaboration, and the reduction of the convergence speed. The smaller the value of Rho, the greater the value of the retention coefficient 1- Rho, the longer the retention time of the pheromone, the greater the possibility of the search of the previously searched path. The positive feedback function of this algorithm is strengthened, although it can speed up the convergence speed, it will reduce the randomness and search ability of the algorithm [10]. The value of pheromone Volatilization Coefficient in this paper is set to {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9}, and the other default values are n = 15, m = 22, Q = 100, Nc = 200, and the TSP problem data used in the experiment are derived from the Eil51 city problem. The results of the experiment are shown in Table 3.

Table 3 Simulation results of pheromone volatilization coefficient P algorithm performance

In order to select the pheromone volatility 1- Rho in ant colony algorithm, we must consider the two performance indexes of global search ability and convergence speed, and make a reasonable choice according to the two performance indexes. Based on the above experimental results, the pheromone volatilization coefficient is set to 0.5.

The selection of parameter values directly affects the global convergence and solving efficiency of the ant colony algorithm. By analyzing and setting up three important parameters, such as information Su Qifa factor alpha, expected heuristic factor beta and pheromone volatilization coefficient rho, the parameter selection value is determined, and then the convergence speed and global search of the algorithm are improved. The effect of ability provides a parameter basis for improving the efficiency of path optimization.

4 Case Verification—Take Harbin Nan Gang District Shun Feng Logistics Distribution Route as an Example

As the capital city of Harbin, Heilongjiang is the largest commercial center in the north of Northeast China. The modern logistics industry in Harbin started late. According to the statistical yearbook of Harbin, after 2014, the freight transportation was mainly carried by civil aviation, its total amount reached 38 thousand tons, and up to 43 thousand tons [11] in 2015, and the transport volume of goods increased year by year. Although the logistics industry in Harbin has some advantages compared with other cities in the province, there is still a big gap compared with other provincial capitals. In 2014, the freight volume of Zhengzhou reached 22802 tons, and the freight volume of Hangzhou reached 293 million 350 thousand tons, and the freight volume of Guangzhou reached 965 million 530 thousand tons [12]. In the same year, the total freight transport volume of Harbin reached 101 million 690 thousand tons. From this, we can see that the development level of logistics industry in Harbin is still low. In April 2017, the Heilongjiang Ministry of Commerce issued the implementation opinion of Heilongjiang Province on promoting the development of trade and logistics industry, and pointed out that promoting the construction of express logistics park to promote the rapid and healthy development of the express industry in the province. In May of the same year, the Harbin Municipal Committee held the demonstration meeting of “Harbin logistics industry” “development plan of 13th Five-Year”, and discussed the development plan of Harbin logistics industry. Therefore, based on the policies of Heilongjiang and Harbin, it is of great practical significance to optimize the logistics distribution route and improve the distribution efficiency in Harbin.

4.1 Data Selection

On this paper, through the Baidu map coordinate system, a total of 15 SF express delivery points in Nangang District of Harbin are selected. The self extraction of these self extracts is mainly concentrated in the places with large passenger flow around the University, the shopping center, the residential area and so on. Harbin Shun Feng Logistics in the city and the county area of 81 self promotion, and there will be two times a day, 11 a.m. and 6 p.m. after the completion of the loading of goods to their respective distribution, and then notify the customer to the nearest point of view to pick up the goods. This paper focuses on the optimization of the distribution path of 15 express delivery points in the Nan gang District of Shun Feng Logistics in the morning time. A cargo container vehicle from the general distribution point of Nan gang district is sent to the other 14 self lifting points. Each time, only once, after all the self lifting, the cargo is returned to the starting point and does not consider the congestion. The shortest path of the process. Specific data information is detailed in Table 4.

Table 4 Self lifting latitude and longitude coordinates of SF logistics in Nan gang District

4.2 Data Processing

In order to simplify the calculation of data, this paper takes the distance of two point coordinates instead of the actual distance and transforms the coordinate data. At the same time, it is convenient for data processing. In this paper, we choose the data after the decimal point of latitude and longitude as the coordinate data. As the latitude and longitude across the earth is a 1/360 of a latitude and longitude circle, it is about 111 km. Therefore, the latitude and longitude is converted to the data of rice as a unit, and the specific data are as follows:

${\text{Coordinate}}\,{\text{after}}\,{\text{conversion}} = {\text{latitude}}\,{\text{and}}\,{\text{longitude}}*11{,}000\,\,{\text{m}}$[14].

The converted data are shown in Table 5 as follows:

Table 5 Coordinate values after conversion of X, Y data

4.3 Parameter Setting

Through the analysis of the parameters in the previous article, n = 15, m = 22; alpha = 1; beta = 5; rho = 0.5 are selected in this case; the maximum cycle times NC_max = 200; the release of the pheromone Q = 100. The setting of specific parameters is shown in Table 6. The detailed code is shown in annex two.

Table 6 Correlation parameter values of ant colony algorithm

4.4 Path Optimization of Ant Colony Algorithm

• The results are as follows: MATLAB simulation results are as follows:

• The shortest path (Shortest_Route) is 1-6-11-14-4-7-8-12-15-13-9-2-5-10-3-1.

• The shortest path length (Shortest_length) is 49113.73 m.

• The shortest path graph and convergence curve are shown in the following figure respectively (Figs. 2 and 3).

  Fig. 2

  

  Shortest path

  Fig. 3

  

  The average distance and the shortest distance

It can be found that the average path of the pheromone volatilization is still fluctuating because of the effect of pheromone volatilization, and the global optimization is still carried out, and it does not fall into the local optimal. Therefore, the effect of the ant colony algorithm on the optimization of distribution path is proved.

5 Conclusion

Logistics distribution is an important part of logistics activities. It is the main research direction of this paper to optimize distribution routes and improve distribution efficiency. In this paper, we use ant colony optimization algorithm and experimental simulation to determine reasonable parameter values to study logistics distribution routing optimization problem. Taking the logistics of SF in Nangang District of Harbin as an example, the shortest distribution route was determined by Matlab simulation experiment, which verified the feasibility and efficiency of the ant colony optimization algorithm and parameter value in the previous article. Finally, we achieve the purpose of selecting reasonable distribution routes and optimizing logistics distribution routes.