A novel PSO-ACO fusion algorithm for logistics distribution vehicle routing optimization

Xiu-fan WANG，Feng LIANG

(1Jilin Communications Polytechnic, Changchun 130000, China)(2Changchun Vocational Institute of Technology, Changchun 130000, China)

Abstract: Traditional ant colony optimization (ACO) algorithm may suffer from ‘premature’ when planning the routing of logistics distribution, which results in a low speed of routing scheduling and optimization. In this paper, a novel logistics distribution routing planning algorithm is proposed by a subsequent combination of particle swarm optimization (PSO) and ant colony optimization. The proposed algorithm takes advantages of the strong global search ability and fast search speed of PSO to obtain the suboptimal solution. And then this suboptimal solution is transformed into the increment of initial pheromone in ACO. Finally, the exact solution is achieved via the positive feedback mechanism of ACO. Simulation results demonstrate that the proposed fusion algorithm, compared with ACO, generates the logistics distribution routing quickly and effectively, gains faster optimization speed and better convergence accuracy, and thus controls the cost of logistics distribution more reasonably.

Key words: Logistics vehicle, Particle swarm optimization, Ant colony optimization, Fusion algorithm

Vehicle routing problem (VRP) refers to the reasonable scheduling of the distribution vehicle driving path so that the vehicle can achieve the minimum cost, the shortest mileage, the shortest time and other goals under certain conditions, and then improve the profits of the enterprise [1-2]. Therefore, lots of researchers focus on the optimization of the distribution path and improving the efficiency of logistics distribution.

Honestly, to the best knowledge of the authors’, there are three kinds of algorithm to solve the VRP, namely precise solution algorithm, heuristic algorithm and intelligent optimization algorithm. The operation time of the precise solution algorithm usually increases sharply with the increase of the problem scale, which cannot solve the large-scale VRP case in a reasonable time. While, the heuristic algorithm uses scheduling rules to deal with the VRP, which can get the approximate optimal solution in a short time. However, due to the strict restrictions on the condition setting of the mentioned algorithm, it is limited to a great extent. In recent years, intelligent optimization algorithm has been applied to VRP, such as ant colony optimization (ACO) algorithm [3- 4], particle swarm optimization (PSO) algorithm [5], genetic algorithm, etc.. These aforementioned optimization algorithms show better search speed, global characteristics, and strong robustness. Unfortunately, with the increase of search routines, the aforementioned algorithms often fall into local extremum and appear ‘premature’ phenomenon, which may affect the search speed and optimization results seriously.

Based on the discussion above, we propose a novel PSO-ACO fusion algorithm for logistics distribution vehicle routing optimization, which is in a way of subsequent combination. The sub optimal solution of the VRP is obtained by utilizing the characteristics of fast convergence speed and strong search ability of PSO, and then it is transformed into the increment of initial pheromone in ACO. Furthermore, the exact solution of the problem is achieved by applying the advantages of high addressing accuracy of ACO. In this way, not only the ‘precocity’ phenomenon is avoided, but also the timeliness of vehicle scheduling is improved.

1 Problem formulation

The VRP is described as follows. Assuming that there are some distribution vehicles for goods delivery form the supply cargo to the need’s locations, the desire of solving the VRP is to optimize the routing of distribution vehicle, and consequently the corresponding evaluation indicators under the constraints of the required quantity and the load capability of distribution vehicles.

To carry out a mathematical description of the problem mentioned above, the distribution settings are given as follows. It is assumed that there arencustomers waiting for deliveries from the distribution centerAwithmdistribution vehicles. And the load capability of each vehicle isG. Meanwhile, the distance between customeriand customersjisdij(i≠j,i,j=1,2,…,n). The distance between customerjand the distribution center isdAj. The required quantity of each customer isNi. If the total length of the path for distribution vehicle isS, then we obtain the objective function

(1)

The constraint conditions are listed as follows.

(2)

(3)

Where：

(4)

(5)

(6)

2 Particle swarm optimizations

In order to give out a full scope of the proposed algorithm, the basic algorithm, namely PSO and ACO, are introduced firstly. PSO is a group based iterative optimization algorithm inspired by the predatory behavior of birds. Each particle of the algorithm represents a feasible solution of the problem, and then the optimal solution can be obtained through the cooperation between individuals. In the whole iterative process, each particle updates the final position according to both historical and global optimal positions.

The unconstrained function optimization problem is expressed as follows.

minf(x1,x2,…,xD)

xi∈[ai,bi],i=1,2,…,D

(7)

Where:f(x) is the objective function,Dis the dimension of independent variables, [ai,bi] indicates the search space ofxi. The update formulations of particle position and velocity are given as follows [6-7].

(8)

Where:xiis the iterative position of theith particle in the search space, and the corresponding fitness value ofxican be calculated via the objective function.viandpirepresent the iteration speed and the optimal position of theith particles, respectively. Andpgis the global optimal position of the group. The learning factors are given asc1andc2.ωis the inertial weight.r1andr2are random numbers in [0,1]. Consequently, the idea of PSO algorithm can be introduced as follows. Each particle in the searching space represents a possible solution vector. And then the optimal solution is achieved through multiple iterations. Based on the obtained optimal solution, the position and speed of the particles can be updated continuously so that we can carry out the global optimal solution. Briefly, the flowchart of PSO algorithm is shown in Fig.1.

Fig.1 The flowchart of PSO algorithm

3 Ant colony optimization

The main point of ACO algorithm comes from the method of searching the shortest path in the process of ants’ foraging. Starting from the cave, ants cooperate between groups and complete information exchange by releasing the pheromones, and try hard to find the shortest path towards the food source, as shown in Fig.2.

Fig.2 The process of ants’ foraging in group

Fig.2-1 displays the alternative paths from the ant cave to the food source. Fig.2-2 shows that, the probability of ants passing through each path is the same at the beginning of ants’ foraging, and also the number of pheromones released. Fig.2-3 demonstrates that the ants’ group finally choose a path with a high density of pheromone. This decision is made based on the knowledge that the density of pheromone units released in a relatively short path is larger than others. ACO algorithm based on ant foraging evolution gains the advantages of strong robustness and fast solution speed, which results in a widely application in vehicle routing optimization.

In general, the selection of the path for ants to find food sources depends on the density of pheromone and the amount of heuristic information. The probability of theijth path selection is formulated[8-10].

(9)

Where:Pij(t) indicates the probability of the selected path, andτij(t) represents the pheromones released by ants on the mentioned path.ηij(t) expresses the heuristic function, indicating the expected degree of ant’s path selection. Meanwhile,αis the information heuristics factor andβis the expectation elicitation factor.

A lot of pheromones may be left by ants during searching of the path. Once the selected path is short enough, there will be more pheromones accumulated on the path unit. This phenomenon may leads to the ‘premature’ problem in the search process of the shortest path, which requires updating the pheromones that can find the shortest path in time after each cycle. The updating law of pheromones is shown as follows.

(10)

Furthermore, there are different ways for updating pheromones. In Ant-Cycle model, the way to update pheromones is as follows.

(11)

Where:Qrepresents the strength of pheromones andLkis the sum of the length of paths passed by ants in one cycle.

4 PSO-ACO fusion algorithm

4.1 Algorithm principle and process

PSO algorithm has strong global search ability and fast search speed, while its convergence accuracy is low. On the other hand, the ACO algorithm shows blindness due to the lack of pheromone information in the initial stage, and also the strong global optimization ability requires a long iteration time. Despite these disadvantages, the search accuracy of ACO is high, which is a compensation for PSO algorithm and finally carries out the main idea of this work, namely the PSO-ACO fusion algorithm.

PSO-ACO fusion algorithm firstly obtains the suboptimal solution via PSO algorithm. Then, the suboptimal solution is transformed into an increment of the initial pheromone distribution in ACO algorithm. Finally, the positive feedback mechanism of ACO algorithm is applied to solve the exact solution of the VRP problem, so as to achieve better solution performance. The detailed steps of the proposed fusion algorithm are listed as follows.

Step1 colony parameter initialization.

Step2 calculate the fitness values for each particle.

Step3 update historical position for individuals and global position for the group based on the fitness values.

Step4 update the position and velocity for each particle by Eq. (8).

Step5 output the suboptimal routing obtained by PSO algorithm once the maximum iteration time is reached.

Step6 transform the suboptimal routing in Step 5 as the increment of the initial pheromone in ACO, which carries out the final pheromone distribution.

Step7 locate the ants on the initial points.

Step8 calculate the path length for each ant, and then search for the global optimal path in this iteration.

Step9 update the pheromone density in each routing.

Step10 once the maximum iteration time is reached, the algorithm is terminated such that the global optimal routing is obtained.

In summarize, the flowchart of the proposed PSO-ACO fusion algorithm is shown in Fig.3.

Fig.3 Process of PSO-ACO fusion algorithm

4.2 Convergence analysis

In order to verify the effectiveness of the proposed fusion algorithm, the algorithm is simulated and analyzed in CloudSim environment, and the corresponding parameters are shown in Table 1.

Table1 Simulation parameters

In the simulation process, the PSO-ACO fusion algorithm is compared with the ACO algorithm, and the results are shown in Fig.4～5.

Fig.4 Simulation results when M=100

As shown in Fig.4, compared with the single ACO algorithm, the proposed PSO-ACO fusion algorithm achieves the optimal solution within less iteration times. Quantitatively, for the case ofM=100, the time consumption of PSO-ACO is approximately 60 s, while 68 s for ACO. Further simulation results forM=200 shown in Fig.5 demonstrates that the convergence times of PSO-ACO and single ACO are 78 s and 85 s, respectively. Thus, we can conclusion that the convergence speed is improved significantly. Meanwhile, the addressing precision is optimized further, which satisfies the requirements of efficient and accurate vehicle scheduling.

Fig.5 Simulation results when M= 200

5 Case verification

In this section, the PSO-ACO fusion algorithm is applied to a logistics company’s goods distribution process to verify the effectiveness of the proposed method. It is known that a logistics company has 4 distribution vehicles, each with a maximum load of 5 tons and a maximum driving distance of 100 kilometers. It is required to provide services for 25 customers at the same time. The information of cargo station and customer location is shown in Table 2, where No. 1 represents the cargo station.

Table2 Customer location information

The purpose of vehicle scheduling algorithm is to optimize the goods distribution routing. In order to evaluate the effectiveness of the optimization algorithm, ACO and PSO-ACO are applied for the same case mentioned above to obtain the vehicle driving routing, as shown in Fig.6～7.

Fig.6 Routing of ACO algorithm

Fig.7 Routing of PSO-ACO algorithm

The two algorithms, namely ACO and PSO-ACO, are compared via the indicators, including total driving distance, total distribution time and distribution cost of vehicles. The distribution cost per kilometer is 12RMB, and the results are shown in Table 3.

Table 3 Indicators comparison

The results show that the total vehicle distribution distance of PSO-ACO fusion algorithm is only 70.6 km, which is 15.2 km (17.7%) less than ACO algorithm. In addition, the total delivery time of PSO-ACO fusion algorithm is 213 minutes, which decreased by 10.9% (26.1 minutes). As a result, the distribution cost of the proposed algorithm is 847.2 RMB, in which 17.7% (182.4 RMB) cost is saved. In summary, the proposed PSO-ACO fusion algorithm can effectively optimize the vehicle driving routing, improve the efficiency of logistics distribution and thus the economic benefits of enterprises.

6 Conclusions

(1) In order to manage the vehicle routing more reasonably in the process of VRP, a PSO-ACO fusion algorithm for logistics distribution routing planning is proposed by combing the advantages of fast convergence speed of PSO and high addressing accuracy of ACO. The algorithm first obtains the suboptimal solution through PSO, then transforms it into the increment of the initial pheromone in ACO. Finally, the positive feedback mechanism of ACO algorithm is applied to solve the exact solution of the problem.

(2) The simulation results and industrial case discussion show that, compared with single ACO algorithm, the proposed PSO-ACO fusion algorithm can quickly and effectively determine the best logistics distribution routing, with faster optimization speed and better convergence accuracy. It can not only avoid the ‘premature’ phenomenon in ACO algorithm, but also improve the rationality of vehicle scheduling, thus reduce the logistics distribution cost significantly.