# The Optimization Model of E-Commerce Logistics Distribution Path Based on GIS Technology

Authors: Jianhong Jiao; Yong Liu; Cuijie Xie
Journal: Advances in Multimedia
 (2022)

---

## Abstract

The optimization of the e-commerce logistics distribution path has always been an important research object in intelligent control. Based on the geographic information system (GIS) platform, this paper proposes an improved ant colony algorithm for the logistics distribution path optimization model based on the GIS platform. Firstly, ArcGIS software is used to solve the problem of complex networks and realize the selection and output of optional routes. Secondly, the basic ant colony algorithm is improved, and a dynamic path planning method combining global planning information and local planning is proposed. It mainly includes the improvement of the heuristic function and the improvement of the update method of pheromone. Finally, through simulation experiments and case validation experiments, it is concluded that the improved algorithm outperforms the traditional ant colony algorithm. In the case validation part, a local area of Beijing is selected to simulate a natural distribution environment, and the path optimization experiments are validated by building an actual road network model. The results show that the model can plan the optimal path for logistics distribution according to the road congestion. The data analysis shows that the route optimization model proposed in this paper can effectively reduce the distribution cost of enterprises, increase vehicle loading, and increase the profit and industry competitiveness of logistics enterprises.


---

## Body

## 1. Introduction

With the development of Internet information technology, cross-border e-commerce is developing rapidly, gradually showing the characteristics of the small order amount and high transaction frequency. This transaction model relies on logistics to an ever-increasing extent, putting forward higher requirements for the domestic logistics industry. In the whole operation process of e-commerce, logistics and distribution are crucial links that determine the delivery efficiency and quality of goods. Whether the logistics and distribution path can be effectively optimized directly affects the efficiency of the logistics and distribution system. Along with the development of e-commerce, the demand for e-commerce logistics also shows a spurt in growth. It is an essential link in delivering physical products from manufacturers or distributors to customers. Logistics and distribution have a profound impact on the healthy and sustainable development of the e-commerce industry. Whether the distribution route is reasonable or not directly impacts the speed of distribution, the cost of distribution, the quality of distribution, and the operational efficiency of enterprises.Logistics path optimization problems essentially belong to combinatorial optimization problems [1], and traditional shortest path algorithms such as interpolation and Dykstra’s algorithm cannot effectively solve the complex situation of increasing vertices due to the excessive storage space requirement. For this type of NP-complete problem, it is not easy to find the exact optimal solution by the global search method, so it is of great theoretical and practical significance to study the corresponding efficient algorithms to find the optimal or near-optimal solutions. At present, the more effective algorithms to solve such problems are the artificial neural network algorithm [2], artificial immune system algorithm [3, 4], particle swarm optimization algorithm [5], and ant colony system algorithm. Various intelligent bionic optimization algorithms have been proposed and developed rapidly. The ones that have been more widely used are genetic algorithms, whale optimization algorithms, and ant colony system algorithm. In the literature [6], genetic algorithms are combined with neighborhood search algorithms to obtain better solutions than individual algorithms considering the drawbacks of genetic algorithms. Thangiah and Nygard and Joe and Blanton [7, 8] were the first to solve VRPTW (vehicle routing problem with time windows) with genetic algorithms and obtained premature solutions. In the literature [9], an adaptive ant colony system algorithm with a unique strategy was proposed, dynamically adjusting the algorithm parameters according to the time-lapse and selecting the starting point based on clustering to achieve the shortest path, improving the convergence speed accuracy of the algorithm. The algorithm parameters are dynamically adjusted according to the time-lapse, and the starting point is selected based on clustering to achieve the shortest path, which improves the convergence speed and accuracy of the algorithm. Got et al. [10] designed an algorithm known as guided population archival whale optimization algorithm (GPAWOA). The algorithm is based on Pareto dominance and uses external archives to store the nondominated solutions found during the optimization process. Experimental results show that the proposed GPAWOA is highly competitive and outperforms the selected state-of-the-art multiobjective optimization algorithm, providing excellent approximate solutions in terms of convergence and diversity. Rajeev and Raman [11] combined the ant colony algorithm with the firefly algorithm, and the results show that it is more effective than the algorithm alone.The ant colony system algorithm was first proposed by an Italian scholar Dorigo et al. in 1996 [12]. The ant colony system algorithm has good robustness, positive feedback, and adaptability as a standard intelligent bionic algorithm. At the same time, it also has good parallel computing ability and integration ability with other heuristic algorithms, which makes it perform well in dealing with more complex path planning problems. However, the ant colony system algorithm also has shortcomings, such as low solution accuracy and slow convergence speed. Based on this framework, researchers put forward many improvement strategies and algorithms from the aspects of algorithm composition, architecture, and parameter optimization. Stützle and Hoos [13] proposed a max-min ant system (MMAS) based on ant colony algorithm. After all the ants in the system iterate once, only the ants’ pheromone that finds the optimal solution is updated. The pheromone of each solution is limited to a range, which is conducive to further searching for the optimal solution. The authors in [14–16] designed the parameter selection of the ant colony algorithm as an optimization problem and solved it using a genetic algorithm and particle swarm optimization algorithm.The route planning is based on the provided traffic road network. Therefore, a prerequisite for research is how to simulate realistic node information and road access and construct a realistic road network model for planning. At present, with the development of computer technology, the application of GIS in route planning has achieved great results [17–20]. GIS can store and analyze the geographic information collected with various attributes and provide visualization and advanced mapping functions. With the powerful spatial data processing capability of GIS, the collected geographic attribute information of the existing road network can be uploaded to the GIS platform and then combined with the database of spatial attributes. An accurate traffic road network model can be established. This paper mainly studies the optimization model of improved ant colony algorithm in e-commerce logistics distribution path based on GIS platform, analyzes the path of e-commerce logistics distribution link, and puts forward optimization strategies.


## 2. Model Design

### 2.1. Current Situation of the Study Area

The research area is Beijing, and this paper is aimed at the business area of a crosstown logistics company. The company's main business includes a complete set of logistics agency and storage agency services. The most frequent hometown delivery demand in the daily delivery is the delivery of ordinary express mail. The company's supply point warehouse and transport road network in the study area can be viewed on Google Maps, as shown in Figure1.Figure 1
Traffic network map of the study area.


### 2.2. GIS Data Collection Process

This paper uses ArcGIS software that solves complex network problems by allowing users to browse and analyze spatial data on their computers. The software’s basic mapping capabilities and advanced GIS features allow users to create maps, display created maps, present data, and complete the integration process. GIS-based road network creation requires two parts, and one is to input traffic network data (including nodes, road sections, and lanes) without topological relationships in the ArcGIS platform; secondly, based on traffic network data, the traffic network with spatial topological rules is formed by relevant processing (such as endpoint matching, error correction, and automatic clipping). Figure2 shows the flowchart of GIS-based traffic network input.Figure 2
Flowchart of traffic network input based on ArcGIS.


### 2.3. Model Variable Determination

Once the GIS-based traffic road network is generated, we can optimize the e-commerce logistics distribution path using an improved ant colony algorithm. In order to facilitate the research, the constraints of the distribution routing problem are determined as follows:(1)
The resources required at each demand point must be satisfied, and none of them can complete the task.(2)
The distribution process ends when all resources have been distributed or met demand points.(3)
The resources required for each demand point can only be obtained from a particular supply point.(4)
The distance and speed determine the completion time of a distribution task from the point of supply to the end of demand.(5)
Vehicles perform logistics services to demand points, which must be completed within the specified time, and early and late arrivals incur corresponding penalty costs.For the sake of description, the model variables are shown in Table1.Table 1
Basic model symbol definition.
Symbolic variableRepresentative meaningZDenotes the objective value of the aggregate function of the supply pointNThe number of demand points to be served by supply pointsDijDenotes the distance from supply pointi to demand point jTijDenotes the time from supply pointi to demand point jCijDenotes the cost of supply pointi to demand point jPa, PbTime penalty factorKIndicates the number of vehicles required for the supply point to provide service to the demand pointSkjDenotes the start time when vehiclek begins service to demand point jTkjDenotes the service time required for vehiclek at demand point jxijkDenotes vehiclek from demand point I to demand point j. It is a logical value with a value of 0 or 1.


### 2.4. Model Description

#### 2.4.1. Constraints

The following equation can be obtained from the description of constraints in Section2.3.(1)
Each demand point can only be served by one vehicle, and no delivery service is allowed to be performed by two or more vehicles. The vehicle leaves the demand point after the delivery service to it is finished for a demand point. The number of vehicles that perform service to the demand point and the number of vehicles that leave should be the same to ensure the balance of traffic flow.(1)∑k=1K∑i=0Nxijk=1,j∈1,2…N,∑k=1K∑j=0Nxijk=1,i∈1,2…N.(2)
The number of vehicles departing from a supply point to a demand point does not exceedK.(2)∑k=1K∑j=1Nx0jk≤K.(3)
The sum of the demand of each demand point on each path shall not exceed the vehicle's maximum capacity.(3)∑i=0N∑j=0Ndixijk≤q,k∈1,2…K.(4)
Distribution vehicles are not involved in pick-up activities when carrying out distribution tasks and return to the original supply point after completing the tasks.(4)∑j=1Nx0jk=∑i=1Nxi0k≤1,k∈1,2…k,∑i=0Nxipk−∑j=1Nxpjk=0,p∈1,2…N,k∈1,2…K.


#### 2.4.2. Congestion Analysis

In this paper, the consideration of path congestion level is added. When the delivery vehicle selects the next node, it focuses not only on the physical distance between nodes but also on the congestion of the path to the next node. Because the physical distance between nodes can be easily obtained by navigation software, the degree of path congestion affects the selection of the optimal path due to weather conditions, traffic accidents, the number of road junctions, the number of traffic signals, and the density of different functional areas of the city. Therefore, when selecting the next node, it is necessary to integrate the two elements of path length and path impact factor to select the more optimal path for priority passage.In order to incorporate the congestion level into the model solving process, the path processing model under congestion restriction is defined as follows: for a demand point, traverse all available routes from the post-supply point to the target demand point to find an optimal path solution. When congestion arises, it usually makes the transportation distance longer, and the transportation time increases, leading to higher transportation costs. The constructed nodal cost function is shown in the following equation.(5)Cij=αijdij+βijmax0,dijv−tij2,where Cij denotes the cost of connecting node i to node j; αij is the fixed transportation cost from node i to node j (acquisition cost or rental cost of distribution vehicles, depreciation and maintenance cost, and driver’s cost); dij is the distance between the two nodes; βij is the congestion cost factor from node i to node j; tij is the typical time spent by both nodes (averaged over several times); and v is the speed of distribution vehicles; when there is congestion on the road, dij increases, and then dij/v (transport time) increases; when dij/v>tij, congestion cost arises, and with the increase of dij/v, the marginal congestion cost rises, showing the characteristics of diseconomies of scale.


#### 2.4.3. Cost Analysis

In constructing the model, customer satisfaction is expressed in terms of whether the time of logistics service is within the specified time window. The vehicle path is optimized to minimize the total delivery cost, and violation of the time window incurs a penalty cost. Therefore, the vehicle must be delivered within the time window as much as possible. Assume that the supply point has a specified time frame for performing service for a customer ofai,bi and the start time of service to the demand point by vehicle k is Sik. When Sik<ai, it means the vehicle arrives early, the penalty factor is Pa, and the penalty cost is Ca=Pa∗ai−Sik. Conversely, when Sik>bi, it means the vehicle has arrived late, the penalty factor is Pb, and the penalty cost is Cb=Pb∗Sik−bi. Generally, the loss of late arrival is greater than the loss of early arrival; then, Cb>Ca. From the above, the penalty cost function can be defined as follows.(6)f=Pa∗max0,ai−sik+Pb∗max0,sik−bi.When performing route optimization, the penalty cost should be appropriate to the distribution cost of the company’s actual vehicles. The distribution cost of the vehicle is calculated from the average distribution cost of all distribution routes within the distribution range. The punishment cost should adapt to the actual vehicle distribution cost of the company and should not be too high or too low. If the delivery vehicle arrives in advance, the impact on customer satisfaction is relatively small; on the contrary, customer satisfaction will be seriously affected. In this paper, the penalty cost PA is set to 25% of the distribution cost. The penalty cost Pb is set to 65% of the distribution cost.Integrating the time penalty cost and distribution cost, the objective function of this paper is constructed as(7)Z=min∑k=1K∑j=1N∑i=0Ncijxijk+Pa∑k=1K∑i=1Nmax0,ai−sik+Pb∑k=1K∑i=1Nmax0,sik−bi.


## 2.1. Current Situation of the Study Area

The research area is Beijing, and this paper is aimed at the business area of a crosstown logistics company. The company's main business includes a complete set of logistics agency and storage agency services. The most frequent hometown delivery demand in the daily delivery is the delivery of ordinary express mail. The company's supply point warehouse and transport road network in the study area can be viewed on Google Maps, as shown in Figure1.Figure 1
Traffic network map of the study area.


## 2.2. GIS Data Collection Process

This paper uses ArcGIS software that solves complex network problems by allowing users to browse and analyze spatial data on their computers. The software’s basic mapping capabilities and advanced GIS features allow users to create maps, display created maps, present data, and complete the integration process. GIS-based road network creation requires two parts, and one is to input traffic network data (including nodes, road sections, and lanes) without topological relationships in the ArcGIS platform; secondly, based on traffic network data, the traffic network with spatial topological rules is formed by relevant processing (such as endpoint matching, error correction, and automatic clipping). Figure2 shows the flowchart of GIS-based traffic network input.Figure 2
Flowchart of traffic network input based on ArcGIS.


## 2.3. Model Variable Determination

Once the GIS-based traffic road network is generated, we can optimize the e-commerce logistics distribution path using an improved ant colony algorithm. In order to facilitate the research, the constraints of the distribution routing problem are determined as follows:(1)
The resources required at each demand point must be satisfied, and none of them can complete the task.(2)
The distribution process ends when all resources have been distributed or met demand points.(3)
The resources required for each demand point can only be obtained from a particular supply point.(4)
The distance and speed determine the completion time of a distribution task from the point of supply to the end of demand.(5)
Vehicles perform logistics services to demand points, which must be completed within the specified time, and early and late arrivals incur corresponding penalty costs.For the sake of description, the model variables are shown in Table1.Table 1
Basic model symbol definition.
Symbolic variableRepresentative meaningZDenotes the objective value of the aggregate function of the supply pointNThe number of demand points to be served by supply pointsDijDenotes the distance from supply pointi to demand point jTijDenotes the time from supply pointi to demand point jCijDenotes the cost of supply pointi to demand point jPa, PbTime penalty factorKIndicates the number of vehicles required for the supply point to provide service to the demand pointSkjDenotes the start time when vehiclek begins service to demand point jTkjDenotes the service time required for vehiclek at demand point jxijkDenotes vehiclek from demand point I to demand point j. It is a logical value with a value of 0 or 1.


## 2.4. Model Description

### 2.4.1. Constraints

The following equation can be obtained from the description of constraints in Section2.3.(1)
Each demand point can only be served by one vehicle, and no delivery service is allowed to be performed by two or more vehicles. The vehicle leaves the demand point after the delivery service to it is finished for a demand point. The number of vehicles that perform service to the demand point and the number of vehicles that leave should be the same to ensure the balance of traffic flow.(1)∑k=1K∑i=0Nxijk=1,j∈1,2…N,∑k=1K∑j=0Nxijk=1,i∈1,2…N.(2)
The number of vehicles departing from a supply point to a demand point does not exceedK.(2)∑k=1K∑j=1Nx0jk≤K.(3)
The sum of the demand of each demand point on each path shall not exceed the vehicle's maximum capacity.(3)∑i=0N∑j=0Ndixijk≤q,k∈1,2…K.(4)
Distribution vehicles are not involved in pick-up activities when carrying out distribution tasks and return to the original supply point after completing the tasks.(4)∑j=1Nx0jk=∑i=1Nxi0k≤1,k∈1,2…k,∑i=0Nxipk−∑j=1Nxpjk=0,p∈1,2…N,k∈1,2…K.


### 2.4.2. Congestion Analysis

In this paper, the consideration of path congestion level is added. When the delivery vehicle selects the next node, it focuses not only on the physical distance between nodes but also on the congestion of the path to the next node. Because the physical distance between nodes can be easily obtained by navigation software, the degree of path congestion affects the selection of the optimal path due to weather conditions, traffic accidents, the number of road junctions, the number of traffic signals, and the density of different functional areas of the city. Therefore, when selecting the next node, it is necessary to integrate the two elements of path length and path impact factor to select the more optimal path for priority passage.In order to incorporate the congestion level into the model solving process, the path processing model under congestion restriction is defined as follows: for a demand point, traverse all available routes from the post-supply point to the target demand point to find an optimal path solution. When congestion arises, it usually makes the transportation distance longer, and the transportation time increases, leading to higher transportation costs. The constructed nodal cost function is shown in the following equation.(5)Cij=αijdij+βijmax0,dijv−tij2,where Cij denotes the cost of connecting node i to node j; αij is the fixed transportation cost from node i to node j (acquisition cost or rental cost of distribution vehicles, depreciation and maintenance cost, and driver’s cost); dij is the distance between the two nodes; βij is the congestion cost factor from node i to node j; tij is the typical time spent by both nodes (averaged over several times); and v is the speed of distribution vehicles; when there is congestion on the road, dij increases, and then dij/v (transport time) increases; when dij/v>tij, congestion cost arises, and with the increase of dij/v, the marginal congestion cost rises, showing the characteristics of diseconomies of scale.


### 2.4.3. Cost Analysis

In constructing the model, customer satisfaction is expressed in terms of whether the time of logistics service is within the specified time window. The vehicle path is optimized to minimize the total delivery cost, and violation of the time window incurs a penalty cost. Therefore, the vehicle must be delivered within the time window as much as possible. Assume that the supply point has a specified time frame for performing service for a customer ofai,bi and the start time of service to the demand point by vehicle k is Sik. When Sik<ai, it means the vehicle arrives early, the penalty factor is Pa, and the penalty cost is Ca=Pa∗ai−Sik. Conversely, when Sik>bi, it means the vehicle has arrived late, the penalty factor is Pb, and the penalty cost is Cb=Pb∗Sik−bi. Generally, the loss of late arrival is greater than the loss of early arrival; then, Cb>Ca. From the above, the penalty cost function can be defined as follows.(6)f=Pa∗max0,ai−sik+Pb∗max0,sik−bi.When performing route optimization, the penalty cost should be appropriate to the distribution cost of the company’s actual vehicles. The distribution cost of the vehicle is calculated from the average distribution cost of all distribution routes within the distribution range. The punishment cost should adapt to the actual vehicle distribution cost of the company and should not be too high or too low. If the delivery vehicle arrives in advance, the impact on customer satisfaction is relatively small; on the contrary, customer satisfaction will be seriously affected. In this paper, the penalty cost PA is set to 25% of the distribution cost. The penalty cost Pb is set to 65% of the distribution cost.Integrating the time penalty cost and distribution cost, the objective function of this paper is constructed as(7)Z=min∑k=1K∑j=1N∑i=0Ncijxijk+Pa∑k=1K∑i=1Nmax0,ai−sik+Pb∑k=1K∑i=1Nmax0,sik−bi.


## 2.4.1. Constraints

The following equation can be obtained from the description of constraints in Section2.3.(1)
Each demand point can only be served by one vehicle, and no delivery service is allowed to be performed by two or more vehicles. The vehicle leaves the demand point after the delivery service to it is finished for a demand point. The number of vehicles that perform service to the demand point and the number of vehicles that leave should be the same to ensure the balance of traffic flow.(1)∑k=1K∑i=0Nxijk=1,j∈1,2…N,∑k=1K∑j=0Nxijk=1,i∈1,2…N.(2)
The number of vehicles departing from a supply point to a demand point does not exceedK.(2)∑k=1K∑j=1Nx0jk≤K.(3)
The sum of the demand of each demand point on each path shall not exceed the vehicle's maximum capacity.(3)∑i=0N∑j=0Ndixijk≤q,k∈1,2…K.(4)
Distribution vehicles are not involved in pick-up activities when carrying out distribution tasks and return to the original supply point after completing the tasks.(4)∑j=1Nx0jk=∑i=1Nxi0k≤1,k∈1,2…k,∑i=0Nxipk−∑j=1Nxpjk=0,p∈1,2…N,k∈1,2…K.


## 2.4.2. Congestion Analysis

In this paper, the consideration of path congestion level is added. When the delivery vehicle selects the next node, it focuses not only on the physical distance between nodes but also on the congestion of the path to the next node. Because the physical distance between nodes can be easily obtained by navigation software, the degree of path congestion affects the selection of the optimal path due to weather conditions, traffic accidents, the number of road junctions, the number of traffic signals, and the density of different functional areas of the city. Therefore, when selecting the next node, it is necessary to integrate the two elements of path length and path impact factor to select the more optimal path for priority passage.In order to incorporate the congestion level into the model solving process, the path processing model under congestion restriction is defined as follows: for a demand point, traverse all available routes from the post-supply point to the target demand point to find an optimal path solution. When congestion arises, it usually makes the transportation distance longer, and the transportation time increases, leading to higher transportation costs. The constructed nodal cost function is shown in the following equation.(5)Cij=αijdij+βijmax0,dijv−tij2,where Cij denotes the cost of connecting node i to node j; αij is the fixed transportation cost from node i to node j (acquisition cost or rental cost of distribution vehicles, depreciation and maintenance cost, and driver’s cost); dij is the distance between the two nodes; βij is the congestion cost factor from node i to node j; tij is the typical time spent by both nodes (averaged over several times); and v is the speed of distribution vehicles; when there is congestion on the road, dij increases, and then dij/v (transport time) increases; when dij/v>tij, congestion cost arises, and with the increase of dij/v, the marginal congestion cost rises, showing the characteristics of diseconomies of scale.


## 2.4.3. Cost Analysis

In constructing the model, customer satisfaction is expressed in terms of whether the time of logistics service is within the specified time window. The vehicle path is optimized to minimize the total delivery cost, and violation of the time window incurs a penalty cost. Therefore, the vehicle must be delivered within the time window as much as possible. Assume that the supply point has a specified time frame for performing service for a customer ofai,bi and the start time of service to the demand point by vehicle k is Sik. When Sik<ai, it means the vehicle arrives early, the penalty factor is Pa, and the penalty cost is Ca=Pa∗ai−Sik. Conversely, when Sik>bi, it means the vehicle has arrived late, the penalty factor is Pb, and the penalty cost is Cb=Pb∗Sik−bi. Generally, the loss of late arrival is greater than the loss of early arrival; then, Cb>Ca. From the above, the penalty cost function can be defined as follows.(6)f=Pa∗max0,ai−sik+Pb∗max0,sik−bi.When performing route optimization, the penalty cost should be appropriate to the distribution cost of the company’s actual vehicles. The distribution cost of the vehicle is calculated from the average distribution cost of all distribution routes within the distribution range. The punishment cost should adapt to the actual vehicle distribution cost of the company and should not be too high or too low. If the delivery vehicle arrives in advance, the impact on customer satisfaction is relatively small; on the contrary, customer satisfaction will be seriously affected. In this paper, the penalty cost PA is set to 25% of the distribution cost. The penalty cost Pb is set to 65% of the distribution cost.Integrating the time penalty cost and distribution cost, the objective function of this paper is constructed as(7)Z=min∑k=1K∑j=1N∑i=0Ncijxijk+Pa∑k=1K∑i=1Nmax0,ai−sik+Pb∑k=1K∑i=1Nmax0,sik−bi.


## 3. Improved Ant Colony Algorithm

Road node selection in traditional ant colony algorithms is mainly carried out by algorithmic state transfer rules, which can be characterized as follows:(8)Qxyle=δxyαeγxyβe∑g∈Klδxyαeγxyβe,y∈Kl0,other,where Qxyle represents the probability of transfer between ant l and road node x,y at time e; γxyβe represents the heuristic function; δxyαe represents the pheromone concentration of the corresponding path between ant l and road node x,y; Kl represents the set of road nodes to be visited by the ant; and α, β represent the relative importance of the heuristic function factors and the pheromone amount within the transfer rule.The ant colony system needs to perform pheromone local update and global update operations to construct candidate solutions. The local update helps reduce the number of subsequent ants choosing the same path and increases the diversity of the population. The global update aims to increase the pheromone concentration on the optimal path, which increases the probability of the optimal path being selected by subsequent ants and improves the convergence speed of the algorithm. However, it increases the risk of the local optimality of the algorithm.


### 3.1. Pheromone Update Improvement

#### 3.1.1. Local Pheromone Update

Local pheromone updates in ant colony systems can reduce the probability of visited paths being selected again, increase the exploration of unvisited regions, and avoid getting trapped in local optima. When an ant selects a new node, a local pheromone update is required according to(9)τij=1−ξ∗τij+ξ∗τ0,where ξ is the local pheromone volatility coefficient and τ0 is the initial pheromone value.


#### 3.1.2. Global Pheromone Updates

When ants search for the optimal solution, state shifting is performed according to the pheromone concentration. If more pheromones are accumulated on specific paths at the beginning, ants will choose that path with high probability so that the diversity of solutions will be lost from the beginning. In order to obtain the solution of diversity, the pheromone updating strategy of the ant colony is improved. A dynamic weight pheromone update strategy with a penalty mechanism is proposed. Its update method is shown in the following equation.(10)τjt+1=1−ρ⋅τjt+ρ∗Δτjgbt+Δτjibt+Δτjworstt,of which(11)Δτjgbt=QLgb,if nodej∈Tgb0,otherwise,(12)Δτjibt=Lsb˙Lib∗QLib,if nodej∈Tib0,otherwise,(13)Δτjworstt=−QLworst,if nodej∈Tworst0,otherwise,where ρ0<ρ<1 denotes the pheromone volatility coefficient and Q is the pheromone intensity, which controls the amount of pheromone released on the path at each iteration and is usually set to a positive constant. τjgbt denotes the pheromone value added to node j belonging to the globally optimal path, which is calculated as shown in (11). Lgb is the length of the globally optimal path, and Tgb denotes the set of nodes of the globally optimal path. τjibt denotes the pheromone value added to the node j belonging to the iterative optimal path, calculated as shown in (12). Lib is the length of the iterative optimal path, and Tib denotes the set of nodes of the iterative optimal path. Δτjworstt denotes the increase in pheromone value at the global worst path node j, which is calculated as shown in (13). Lworst is the length of the worst path, and Tworst denotes the set of nodes of the worst path.From formula (10), the pheromone updating rules we designed first enhance the pheromones on both the globally optimal and iterative optimal paths. Secondly, the pheromone intensity released on the iterative optimal path is related not only to the length of the iterative optimal path but also to the ratio of the length of the iterative optimal path to the globally optimal path. The smaller the iterative optimal path length is, the larger the pheromone will be released. Otherwise, less pheromones will be released. This update rule weakens the pheromone on the worst solution to reduce the misleading effect of the worst path on the subsequent ants.


### 3.2. Heuristic Function Improvement

In the traditional ant colony algorithm, the heuristic function ignores the directional guidance of ant traversal, and the value is considered the inverse of the distance between two nodes. If the heuristic function ignores the direction, it is easy to cause that the ant traversal tends too much to single-step minimization optimization, deviating seriously from the overall optimization direction. which is seriously offset from the overall optimization direction. With this limitation, the local optimal shortest path selection cannot optimize. In this way, the local optimal shortest path selection is limited, and the overall optimization cannot be achieved. In this paper, we improve the heuristic function based on the distance relationship between the ant's current position and its historical position and the traversal position, as shown in the following equation:(14)γxy=1Lx+Lxy+Lye,where Lx represents that the path length has passed when the ant reaches node x; Lxy represents the distance between two nodes x and y； and Lye represents the distance from the next node y to the target node e.According to the equation, traversal’s direct guidance and accuracy are strengthened by optimizing the heuristic function. In this way, the ants are guided to continue moving towards the globally optimal path node to realize the globally optimal path selection and meet the overall optimization concept based on multiple constraints to the greatest extent.


### 3.3. Algorithm Steps

The flow based on the above-improved algorithm is shown in Figure3, and its execution process is as follows.Figure 3
Algorithm flowchart.Step 1.
Initialize the road network environment. Establish the road network model, define the supply points and demand points, and initialize the road information between nodes.Step 2.
Initialize algorithm parameters such as the number of ants, the maximum number of iterations, the current number of iterations, and some control parameters such as information heuristic factor and information volatilization factor.Step 3.
Construct the initial feasible path. The ants in the ant colony system are placed at the starting point of path planning to build candidate paths until the ants reach the end or fall into a deadlock state. When the candidate path is constructed, the pheromone is updated locally according to equation (10).Step 4.
When the candidate paths are constructed, the lengths of all candidate paths are calculated, and the globally optimal path, iterative optimal path, and worst path are obtained. The global pheromone update is performed according to equation (11). At the same time, pheromone diffusion is performed based on the pheromone diffusion model.Step 5.
Perform the local optimization operation on the obtained global optimal path. The new path obtained by local optimization is used as the second path of the optimal ant search, which is equivalent to getting two paths in each iteration. The pheromone update is also performed on the optimized paths to enhance the global search capability of the ant colony algorithm, thus speeding up the algorithm to find the globally optimal path. In addition, the pheromone increments caused by the new paths are also diffused according to the pheromone diffusion model to play the leading role of the paths obtained by local optimization.Step 6.
Repeat Steps3–5, and stop when the algorithm reaches the maximum number of iterations.Step 7.
Output the globally optimal path.


## 3.1. Pheromone Update Improvement

### 3.1.1. Local Pheromone Update

Local pheromone updates in ant colony systems can reduce the probability of visited paths being selected again, increase the exploration of unvisited regions, and avoid getting trapped in local optima. When an ant selects a new node, a local pheromone update is required according to(9)τij=1−ξ∗τij+ξ∗τ0,where ξ is the local pheromone volatility coefficient and τ0 is the initial pheromone value.


### 3.1.2. Global Pheromone Updates

When ants search for the optimal solution, state shifting is performed according to the pheromone concentration. If more pheromones are accumulated on specific paths at the beginning, ants will choose that path with high probability so that the diversity of solutions will be lost from the beginning. In order to obtain the solution of diversity, the pheromone updating strategy of the ant colony is improved. A dynamic weight pheromone update strategy with a penalty mechanism is proposed. Its update method is shown in the following equation.(10)τjt+1=1−ρ⋅τjt+ρ∗Δτjgbt+Δτjibt+Δτjworstt,of which(11)Δτjgbt=QLgb,if nodej∈Tgb0,otherwise,(12)Δτjibt=Lsb˙Lib∗QLib,if nodej∈Tib0,otherwise,(13)Δτjworstt=−QLworst,if nodej∈Tworst0,otherwise,where ρ0<ρ<1 denotes the pheromone volatility coefficient and Q is the pheromone intensity, which controls the amount of pheromone released on the path at each iteration and is usually set to a positive constant. τjgbt denotes the pheromone value added to node j belonging to the globally optimal path, which is calculated as shown in (11). Lgb is the length of the globally optimal path, and Tgb denotes the set of nodes of the globally optimal path. τjibt denotes the pheromone value added to the node j belonging to the iterative optimal path, calculated as shown in (12). Lib is the length of the iterative optimal path, and Tib denotes the set of nodes of the iterative optimal path. Δτjworstt denotes the increase in pheromone value at the global worst path node j, which is calculated as shown in (13). Lworst is the length of the worst path, and Tworst denotes the set of nodes of the worst path.From formula (10), the pheromone updating rules we designed first enhance the pheromones on both the globally optimal and iterative optimal paths. Secondly, the pheromone intensity released on the iterative optimal path is related not only to the length of the iterative optimal path but also to the ratio of the length of the iterative optimal path to the globally optimal path. The smaller the iterative optimal path length is, the larger the pheromone will be released. Otherwise, less pheromones will be released. This update rule weakens the pheromone on the worst solution to reduce the misleading effect of the worst path on the subsequent ants.


## 3.1.1. Local Pheromone Update

Local pheromone updates in ant colony systems can reduce the probability of visited paths being selected again, increase the exploration of unvisited regions, and avoid getting trapped in local optima. When an ant selects a new node, a local pheromone update is required according to(9)τij=1−ξ∗τij+ξ∗τ0,where ξ is the local pheromone volatility coefficient and τ0 is the initial pheromone value.


## 3.1.2. Global Pheromone Updates

When ants search for the optimal solution, state shifting is performed according to the pheromone concentration. If more pheromones are accumulated on specific paths at the beginning, ants will choose that path with high probability so that the diversity of solutions will be lost from the beginning. In order to obtain the solution of diversity, the pheromone updating strategy of the ant colony is improved. A dynamic weight pheromone update strategy with a penalty mechanism is proposed. Its update method is shown in the following equation.(10)τjt+1=1−ρ⋅τjt+ρ∗Δτjgbt+Δτjibt+Δτjworstt,of which(11)Δτjgbt=QLgb,if nodej∈Tgb0,otherwise,(12)Δτjibt=Lsb˙Lib∗QLib,if nodej∈Tib0,otherwise,(13)Δτjworstt=−QLworst,if nodej∈Tworst0,otherwise,where ρ0<ρ<1 denotes the pheromone volatility coefficient and Q is the pheromone intensity, which controls the amount of pheromone released on the path at each iteration and is usually set to a positive constant. τjgbt denotes the pheromone value added to node j belonging to the globally optimal path, which is calculated as shown in (11). Lgb is the length of the globally optimal path, and Tgb denotes the set of nodes of the globally optimal path. τjibt denotes the pheromone value added to the node j belonging to the iterative optimal path, calculated as shown in (12). Lib is the length of the iterative optimal path, and Tib denotes the set of nodes of the iterative optimal path. Δτjworstt denotes the increase in pheromone value at the global worst path node j, which is calculated as shown in (13). Lworst is the length of the worst path, and Tworst denotes the set of nodes of the worst path.From formula (10), the pheromone updating rules we designed first enhance the pheromones on both the globally optimal and iterative optimal paths. Secondly, the pheromone intensity released on the iterative optimal path is related not only to the length of the iterative optimal path but also to the ratio of the length of the iterative optimal path to the globally optimal path. The smaller the iterative optimal path length is, the larger the pheromone will be released. Otherwise, less pheromones will be released. This update rule weakens the pheromone on the worst solution to reduce the misleading effect of the worst path on the subsequent ants.


## 3.2. Heuristic Function Improvement

In the traditional ant colony algorithm, the heuristic function ignores the directional guidance of ant traversal, and the value is considered the inverse of the distance between two nodes. If the heuristic function ignores the direction, it is easy to cause that the ant traversal tends too much to single-step minimization optimization, deviating seriously from the overall optimization direction. which is seriously offset from the overall optimization direction. With this limitation, the local optimal shortest path selection cannot optimize. In this way, the local optimal shortest path selection is limited, and the overall optimization cannot be achieved. In this paper, we improve the heuristic function based on the distance relationship between the ant's current position and its historical position and the traversal position, as shown in the following equation:(14)γxy=1Lx+Lxy+Lye,where Lx represents that the path length has passed when the ant reaches node x; Lxy represents the distance between two nodes x and y； and Lye represents the distance from the next node y to the target node e.According to the equation, traversal’s direct guidance and accuracy are strengthened by optimizing the heuristic function. In this way, the ants are guided to continue moving towards the globally optimal path node to realize the globally optimal path selection and meet the overall optimization concept based on multiple constraints to the greatest extent.


## 3.3. Algorithm Steps

The flow based on the above-improved algorithm is shown in Figure3, and its execution process is as follows.Figure 3
Algorithm flowchart.Step 1.
Initialize the road network environment. Establish the road network model, define the supply points and demand points, and initialize the road information between nodes.Step 2.
Initialize algorithm parameters such as the number of ants, the maximum number of iterations, the current number of iterations, and some control parameters such as information heuristic factor and information volatilization factor.Step 3.
Construct the initial feasible path. The ants in the ant colony system are placed at the starting point of path planning to build candidate paths until the ants reach the end or fall into a deadlock state. When the candidate path is constructed, the pheromone is updated locally according to equation (10).Step 4.
When the candidate paths are constructed, the lengths of all candidate paths are calculated, and the globally optimal path, iterative optimal path, and worst path are obtained. The global pheromone update is performed according to equation (11). At the same time, pheromone diffusion is performed based on the pheromone diffusion model.Step 5.
Perform the local optimization operation on the obtained global optimal path. The new path obtained by local optimization is used as the second path of the optimal ant search, which is equivalent to getting two paths in each iteration. The pheromone update is also performed on the optimized paths to enhance the global search capability of the ant colony algorithm, thus speeding up the algorithm to find the globally optimal path. In addition, the pheromone increments caused by the new paths are also diffused according to the pheromone diffusion model to play the leading role of the paths obtained by local optimization.Step 6.
Repeat Steps3–5, and stop when the algorithm reaches the maximum number of iterations.Step 7.
Output the globally optimal path.


## 4. Experimental Results and Analysis

### 4.1. Simulation Tests

This paper focuses on improving the ant colony algorithm in terms of both the pheromone update strategy and the heuristic function. In order to verify the performance of the proposed algorithm, the improved ant colony algorithm is implemented in MATLAB, and the optimal path is solved. Finally, the results are compared with the original ant colony algorithm.The simulation experiment is described as follows: there is one supply point, and 20 demand points are served with the help of 3 vehicles. Let the distribution methods for these 20 demand points be the same, and the vehicles have a rated capacity of 10 tonnes. It is now necessary to select a distribution route for the group of demand points (considering only straight-line distances) that minimizes the total distance of the distribution path while minimizing the total distribution cost. The relevant parameters for the demand points are shown in Table2.Table 2
Customer parameters.
No.Distance (km)Demand (T)Service time (m)No.Distance (km)Demand (T)Service time (m)116.7230114.723025.6230123.6120310.2120136.2230417.7460149.5230513.21201511.7340621.43401613.423078.92301718.212085.3120187.923094.43401915.6230106.91202013.8340Figure4 compares the optimization results between the two algorithms, using the traditional ant colony algorithm (TACA) and the algorithm proposed in this paper (IACA).Figure 4
Comparison of the optimization results of two algorithms for distribution paths. (a) The optimization result of traditional ant colony algorithm. (b) The optimization result of this algorithm.
(a)(b)Assume that the goods correspond to a distribution cost per unit of time of 12$/hour and that the fixed driving cost per vehicle per day is 90$/day. The average vehicle speed is 50 km/h. The comparison results based on the optimization results of the two algorithms are shown in Table3.Table 3
Comparison of test results.
AlgorithmsTotal number of tripsTotal delivery time (H)Target function value (USD)TACA114.532174.4IACA73.821833.6From the test results, compared to the traditional ant colony algorithm, the improved ant colony algorithm proposed in this paper reduces the total number of trips by 4, the total delivery time consumed by 0.71 hours, and the objective function value (cost) by $340.8.Considering that this algorithm adds the update strategy of local pheromone and the consideration of directionality to the heuristic function, the algorithm's computation and time will increase. We use traditional ant colony algorithm (TACA) and adaptive polymorphic ant colony algorithm (APACA) [21] to compare with the algorithm in this paper (IACA). Three indexes, including iteration times, optimal distance length, and operation time, are selected for verification. The results are shown in Table 4.Table 4
Comparison of test results.
AlgorithmsIteration timesOptimal distance length (km)Running time (ms)TACOA56116.521074APACA3481.56859IACA1958.26972As shown in Table4, compared with the other two algorithms, the algorithm proposed in this paper performs well in terms of the number of iterations and finding the optimal shortest path, but the running time is slightly longer.


### 4.2. Example Validation

In order to test the solution performance of the algorithm introducing congestion factor analysis for logistics distribution route optimization, we take a part of Figure1 as an example to verify. The path planning after intercepting some areas and optimizing with the improved ant colony algorithm is shown in Figure 5, in which the green dot is the supply point and the red water drop sign is the demand point.Figure 5
Optimal logistics distribution path planning.Now suppose that a section of road becomes unconnected due to traffic congestion. At this point, the new road information will be updated in real time through ArcGIS, and the logistics distribution path will be replanned. The result of the re-planning is shown in Figure6.Figure 6
Optimal logistics and distribution path planning after taking congestion into account.The red line segment in Figure6 indicates that it is congested. It can be seen that with the introduction of congestion analysis, the original congested section was avoided after dispatching vehicles and providing new route planning.


## 4.1. Simulation Tests

This paper focuses on improving the ant colony algorithm in terms of both the pheromone update strategy and the heuristic function. In order to verify the performance of the proposed algorithm, the improved ant colony algorithm is implemented in MATLAB, and the optimal path is solved. Finally, the results are compared with the original ant colony algorithm.The simulation experiment is described as follows: there is one supply point, and 20 demand points are served with the help of 3 vehicles. Let the distribution methods for these 20 demand points be the same, and the vehicles have a rated capacity of 10 tonnes. It is now necessary to select a distribution route for the group of demand points (considering only straight-line distances) that minimizes the total distance of the distribution path while minimizing the total distribution cost. The relevant parameters for the demand points are shown in Table2.Table 2
Customer parameters.
No.Distance (km)Demand (T)Service time (m)No.Distance (km)Demand (T)Service time (m)116.7230114.723025.6230123.6120310.2120136.2230417.7460149.5230513.21201511.7340621.43401613.423078.92301718.212085.3120187.923094.43401915.6230106.91202013.8340Figure4 compares the optimization results between the two algorithms, using the traditional ant colony algorithm (TACA) and the algorithm proposed in this paper (IACA).Figure 4
Comparison of the optimization results of two algorithms for distribution paths. (a) The optimization result of traditional ant colony algorithm. (b) The optimization result of this algorithm.
(a)(b)Assume that the goods correspond to a distribution cost per unit of time of 12$/hour and that the fixed driving cost per vehicle per day is 90$/day. The average vehicle speed is 50 km/h. The comparison results based on the optimization results of the two algorithms are shown in Table3.Table 3
Comparison of test results.
AlgorithmsTotal number of tripsTotal delivery time (H)Target function value (USD)TACA114.532174.4IACA73.821833.6From the test results, compared to the traditional ant colony algorithm, the improved ant colony algorithm proposed in this paper reduces the total number of trips by 4, the total delivery time consumed by 0.71 hours, and the objective function value (cost) by $340.8.Considering that this algorithm adds the update strategy of local pheromone and the consideration of directionality to the heuristic function, the algorithm's computation and time will increase. We use traditional ant colony algorithm (TACA) and adaptive polymorphic ant colony algorithm (APACA) [21] to compare with the algorithm in this paper (IACA). Three indexes, including iteration times, optimal distance length, and operation time, are selected for verification. The results are shown in Table 4.Table 4
Comparison of test results.
AlgorithmsIteration timesOptimal distance length (km)Running time (ms)TACOA56116.521074APACA3481.56859IACA1958.26972As shown in Table4, compared with the other two algorithms, the algorithm proposed in this paper performs well in terms of the number of iterations and finding the optimal shortest path, but the running time is slightly longer.


## 4.2. Example Validation

In order to test the solution performance of the algorithm introducing congestion factor analysis for logistics distribution route optimization, we take a part of Figure1 as an example to verify. The path planning after intercepting some areas and optimizing with the improved ant colony algorithm is shown in Figure 5, in which the green dot is the supply point and the red water drop sign is the demand point.Figure 5
Optimal logistics distribution path planning.Now suppose that a section of road becomes unconnected due to traffic congestion. At this point, the new road information will be updated in real time through ArcGIS, and the logistics distribution path will be replanned. The result of the re-planning is shown in Figure6.Figure 6
Optimal logistics and distribution path planning after taking congestion into account.The red line segment in Figure6 indicates that it is congested. It can be seen that with the introduction of congestion analysis, the original congested section was avoided after dispatching vehicles and providing new route planning.


## 5. Conclusion

This paper proposes an optimized logistics distribution path model based on an improved ant colony system algorithm. Based on the GIS platform, the experimental verification of material distribution path planning is carried out using accurate road network information. The main work includes the following. Firstly, the heuristic function and pheromone update strategy in the traditional ant colony system algorithm are improved. Secondly, the improved algorithm is coded and integrated into the urban actual road network model database established in the ArcGIS platform to complete the experimental verification. The experimental results show that the optimized logistics distribution path model designed in this paper can quickly calculate the optimal distribution path considering road congestion factors, achieve the effect of real-time information updates, and provide decision support for logistics enterprises.



---

*Source: 4303863-2022-05-16.xml*