The design of path optimization in express transportation based on an improved ant colony algorithm

The Ant Colony (AC) algorithm considers the impact of changes in traffic capacity on vehicle travel time, aiming to reduce direct and indirect losses caused by special traffic conditions from both the perspectives of timeliness and economy. The IAC can quickly create the optimal path, enhancing path efficiency and effectively reducing node energy consumption, ensuring overall network energy balance [1]. The AC algorithm can be limited to three directions, which can reduce search time and improve efficiency. The improvement of path cost function can prevent the local optimal solution of AC algorithm [2]; AC algorithm is very good in calculating the optimal path, but it has the phenomenon of slow convergence and stagnation. Therefore, the path selection strategy based on heuristic factors of AC algorithm can accelerate the convergence and effectively solve this problem [3]. With the increasing demand for timeliness in today's era, path selection becomes particularly important. The competition of express delivery industry is intensifying, and the competitiveness of enterprises is the key factor of development. Using the characteristics of AC, the optimal path is found and the mobile warehouse milk distribution model is put forward to meet the needs of enterprise development. Path selection in express delivery is the fundamental reason determining the speed of transportation. According to the ant colony distribution model and algorithm, the cost of express delivery has been reduced, and the efficiency of distribution has been improved, significantly enhancing the service level and competitiveness of express delivery companies [4]. The AC algorithm can introduce pheromone update procedures to dynamically increase pheromones on the optimal path, improving the visibility heuristic factor. Experimental improvements to the AC algorithm also exhibit good optimization capabilities and rapid convergence, aiding in accurately finding the optimal path that meets multiple quality constraints in road networks [5]. The core of urban emergency rescue research is the optimal path problem. In actual situations, apart from distance issues, various practical factors must also be considered. These algorithms use the limitation of pheromone range as a reference for ants' pheromone algorithms and introduce local pheromone tracking strategies, effectively controlling premature convergence and accelerating solution speed [6]. Optimal path algorithms limit the search area and direction, using real-time distance as the weight of the optimal path, resulting in paths that allow users to reach their destinations in the shortest time possible with minimal fuel consumption during actual traffic tests. It is considered the best path [7]. Problems generated by optimal path algorithms can fall under the spectral line extraction algorithm of the AC algorithm. Using the grid method to construct corresponding mathematical models increases the attractiveness of target spectral lines to path searches, improving convergence rates and performing better in extracting low signal-to-noise ratio spectral lines [8]. The express delivery industry has become one of the industry’s most closely related to people's lives, helping courier companies find the best distribution routes to optimize services and save costs [9]. Optimal path selection in tourism is also useful, with influencing factors not only including the length of the route but also weather, traffic, and scenic spot views, among others. Multi-weight ants and genetic variations are used to search for the optimal path [10]. It is widely applied in the telecommunications industry, transportation, and project management. MOSP is one of the most critical problems in network optimization, and results on a set of instance problems show that the algorithm innovation is a high- quality non-dominated solution in the solution, saving time [11]. The hybrid Ant Colony Immune Network Algorithm for motion planning uses an IAC based on pseudo-random proportional rules and super-ant colony optimization strategies to search antibody networks [12]. In the optimized network, the number of delivery vehicles and total distance have been effectively reduced. Therefore, designing a logistics delivery vehicle distribution algorithm model based on the AC algorithm is feasible [13]. Due to the widespread existence of path planning problems, many researchers study this issue. Couriers often need to reach their destinations as quickly as possible. In the process of processing, greedy strategy constantly changes the preference of ant colony, so that the ant colony turns to explore higher concentration areas, thus achieving the purpose of speeding up the convergence speed [14]. The AC algorithm can also achieve good benefits in road passenger transport. Aiming for the shortest transportation time, the AC express lines has been optimized. The optimized transportation network by the AC algorithm can save time [15].

2

Overview of the path problem

2.1

Path Problem and Model

Traditional Vehicle Routing Problems (VRPs) can be analyzed as follows: within a user group of an organization, there will be a distribution center. We need to deliver and pick up goods required by this user group, the reasonable arrangement and planning of the current available vehicle transportation routes in distribution centers are very important. The whole process of vehicles from departure to completion of service until return requires reasonable scheduling. The optimization objectives of VRP generally include total transportation costs, the number of vehicles, customer satisfaction, and vehicle travel distances. As shown in Figure 1, the triangle represents the distribution center, the circles represent customer points with demands, and directed line segments represent the connecting routes between two customer points. Each line segment corresponds to a cost (usually distance or vehicle travel time), and each dashed ellipse encloses a delivery route.

Graph theory is used to describe the problem of vehicle routing: an undirected graph G = (V, E) is defined, where V= (V₀, V_c represents the set of all nodes in the graph, V₀={0} represents the distribution center, V_c={1,2,3,.,.,n} the set of customer points, and E = {(i, j)|i,j ∈ V, i ≠ j} represents the set of road sections composed of the connection of two nodes.

Symbol Definition:

c_d——The unit distance driving cost of a vehicle;

c_v——The fixed cost of calling a vehicle;

d_ij——The straight-line distance between node i and node j.

q_i——Represents the cargo demand of user i;

K——Denote the set of vehicles as K={1,2,3...,m};

Q_k——The maximum loading capacity of delivery vehicle k.

For each edge (i, j), define the following variables:

$x_{ij}^{k}$ --the driving variable of whether the vehicle k.

$y_{i}^{k}$ -indicates whether the vehicle k is transformed following the demand transformation of the user i.

A VRP (Vehicle Routing Problem) aimed at minimizing the total delivery cost can be expressed as:

(1)

\min Z_{c} = c_{d} \sum_{i = 0}^{n} \sum_{j = 0}^{n} d_{i j} x_{i j} + c_{v} \sum_{k = 1}^{m} \sum_{i = 0}^{n} \sum_{j = 0}^{n} x_{i j}^{k}

(2)

\begin{matrix} \sum_{i = 1}^{n} q_{i} y_{i}^{k} \leq Q_{k}, & k \in K \end{matrix}

(3)

\sum_{i = 0}^{n} x_{ip}^{k} - \sum_{j=0}^{n} x_{pj}^{k} = 0, \forall_{p} \in V, k \in K

(4)

\sum_{i = 1}^{n} y_{i}^{k} = 1, k \in K

(5)

\sum_{k=1}^{m} y_{0}^{k} \leq m

(6)

\sum_{k=1}^{m} x_{0 i}^{k} = \sum_{k=1}^{m} x_{i 0}^{k}, i \in V_{c}

Equation 1 is the objective value, which aims to optimize the delivery cost. Here, the delivery cost consists of vehicle travel expenses and fixed vehicle costs; Equation 2 indicates that the total demand must be less than or equal to the total load capacity of the vehicle; Equation 3 shows that the number of vehicles is the same as that of customer points; Equation 4 represents the restriction on individual customers, meaning they are only visited once and their demand is met by only one vehicle; Equation 5 indicates that the number of working vehicles must be less than the maximum number of vehicles available; Equation 6 represents that all working vehicles start from [16].

2.2

Characteristics of core elements of vehicle routing problems

From the mathematical model of VRP, it can be seen that the construction of VRP model needs to include: road network, vehicles, customers, distribution center (parking lot) and optimization objectives.

1)

Road network

In VRP, the road network is typically represented by a weighted graph of nodes and arcs. Arcs represent the connecting paths between customer points or between customer points and the distribution center. Depending on the needs of the actual problem, each arc is usually assigned a non-negative cost weight, which can be the transportation cost between two points, vehicle operation time, or driving distance, etc. Symmetric vehicle problems are generally represented by undirected graphs, where the double cost between two nodes is equal; asymmetric vehicle problems are represented by directed graphs, where the bidirectional cost weights between two nodes are different.

2)

Vehicle

In the VRP, a set of vehicles owned by the distribution center typically provides pick-up and delivery services to customers. In this problem system, vehicles have several characteristics: 1)

Vehicle Type: In theoretical studies on VRP, it is generally assumed that all vehicles owned by the distribution center are of the same type; however, in actual logistics activities, the vehicles used are mostly composed of various types, meaning that their loading capacities, fixed costs for using the vehicles, and transportation costs per unit distance differ.

2)

Vehicle Loading Capacity: This refers to the maximum weight limit that a vehicle can carry.

3)

Vehicle Cost: This includes the fixed cost of using a vehicle as well as the cost of operating the vehicle.

4)

Vehicle Service Type: The service types provided by vehicles include delivery, pick-up, and simultaneous pick-up and delivery services.

5)

Vehicle Service Time: This is the time spent by the vehicle when providing service at customer locations.

6)

Vehicle Range: In other words, the maximum distance or the longer the car can operate, which translates to the longest continuous driving time in practical terms.

3

AC algorithms

Assuming some ants, related problems are studied, and they are made to work in parallel. Ants will release pheromones on each journey [17]. Based on the distance between two points, ants choose a random local search strategy considering the initial quantity of pheromones (assuming an equal initial quantity of pheromones). This increases the pheromone levels in peripheral areas, making it easier to select subsequent actions. Each ant can only walk legal routes, and once all ants have completed their tours, they will start updating all pheromones autonomously. The new ant colony updates the new information obtained from the search, and the pheromone is replaced by the new pheromone, which improves the method. Then, when the ant colony paths are all the same, indicating that the running steps have stagnated and the solution has not changed, we think that the algorithm is successful, and the solution obtained is the optimal solution. As shown in Figure 2.

Using the distance between different regions in urban transportation, represent the probability of transporting from region i to region j at time t using $p_{ij}^{k} (t)$ .

(7)

p_{ij}^{k} (t) = \{\begin{cases} τ_{ij}^{a} (t) η_{ij}^{β} (t) & j \in {allowed}_{k} \\ \underset{0}{Σ_{r \in {allowed}_{k}}} τ_{ir}^{a} (t) η_{ir}^{β} (t) & other \end{cases}

In which, allowd_k = {0,1...n-1} means entering the next region from one area.

(8)

τ_{ij} (t + 1) = (1 - ρ) \cdot τ_{ij} (t) + {Δτ}_{ij}

Due to the decreasing availability of information, it is represented by the parameter p and τ_ij (t) represents the degree of decay over time. The information increment △τ_ij can be expressed as: (9) ${Δτ}_{ij} = \sum_{k = 1}^{m} {Δτ}_{ij}^{k}$

${Δτ}_{ij}^{k}$ represents the amount of information left by ant k when it traverses cities i and j, and its calculation formula changes with the change of model. For example, in the most commonly used ant circle system model, (10) ${Δτ}_{ij}^{k} = {\begin{matrix} {Q/L}^{k} \\ 0 \end{matrix}$

Where:

Q/L^k—Indicates that there is an ant k passing city i to city j;

0--table otherwise;

Q--denotes a constant;

L^k is the length of the route traveled.

After many traversals, the expressions of $τ_{ij}^{k} (t), {Δτ}_{ij}^{k} (t) and p_{ij}^{k} (t)$ can change with different algorithms[18], depending on the specific problem. M.Dorigo has given 3 different models, the difference lies in the different formulas. In the ant-quantity system: (11) $Δ τ_{ij}^{k} = {\begin{matrix} Q / d_{ij} \\ 0 \end{matrix}$

Where:

Q/d_ij-means that there are and only ants k passing city i to city j;

0--table otherwise.

In ant-density system Middle: (12) $Δ τ_{ij}^{k} = {\begin{matrix} Q \\ 0 \end{matrix}$

Where:

Q--indicates that an ant k passes between city i and city j;

0--table otherwise.

4

IAC

The strategy of constructing its path and pheromone update rules according to ant transfer rules is based on AC algorithm. It is a neighborhood solution that combines local search algorithm with ant AC algorithm to find the optimal solution. To reduce redundant calculations, this paper sets the condition for initiating local search as follows: the results of the algorithm are the same for two consecutive iterations, and the pheromone evaporation coefficient p ∈ [a, b]. After the local search ends, if a better neighborhood solution is obtained, it triggers the utilization coefficient of the information elements and the value of the information pixels on all paths to increase the randomness during the search algorithm. The processing sequence of the algorithm is shown in Figure 4 [19].

Operation steps:

Step 1: Initialize the parameters of the AC algorithm, set the iteration count iter=1, load the specific data of the distribution center, customers, and delivery vehicles, and set the departure node of all ants to the distribution center node.

Step 2: Select the next visit node for the k-th ant.

Step 3: Determine whether the ant has traversed all nodes; if completed, proceed to step 4, otherwise return to step 2.

Step 4: Determine whether all ants have completed path searching; if completed, proceed to step 5, otherwise return to step 2.

Step 5 Determine if the iteration count iter=1; if iter=1, proceed to step 10, otherwise go to step 6.

Step 6 Determine whether the optimal results of two consecutive iterations of the algorithm are the same; if the same, proceed to step 7, otherwise go to step 10.

Step 7 If a≤ρ≤b, proceed to step 8, otherwise adjust ρ and go to step 10.

Step 8: Locally search the obtained optimal solution and then obtain the neighborhood solution.

Step 9 Determine whether the obtained neighborhood solution is better than the initial solution; if it is better, initialize the pheromone evaporation coefficient ρ and the pheromone table, then proceed to step 10, otherwise return to step 7.

Step 10 Update the global pheromones based on the pheromone update rule.

Step 11 Determine whether the number of iterations has reached the maximum iteration count iter_max; if the number of iterations reaches iter_max, output the current solution and terminate the run, otherwise, set iter=iter+1, and return to step 2.

4.1

Experimental settings and environmental settings

Experiments are performed on the proposed algorithm to solve the end-of-scope delivery problem. One of the coordinates is the crank transport and the other coordinates are the crankcase for each area. Set the value of each variable of the ant algorithm, where the number of ants is 50 and the maximum number of iterations is 100. The validity factor A is set to 1, and if this value is 1, the search performance is best. The value of the activation function is too small, resulting in partial optimization, with a bast value of 5 providing the best search performance. The pulse coefficient σ = 0.1 of the information elements, the probability of cross traffic is 0.8, and the probability of change is 0.1. The created model is shown in Figure 5:

The black solid dot in the picture is the express delivery point, and the other dots are 30 transshipment centers. Compared with the traditional AC algorithm, the search efficiency needs to be traversed before the delivery point can be executed.

4.2

Experimental analysis

Comparing the optimal path analysis between the IAC shown in Figure 6 and the traditional AC algorithm, the IAC is faster and breaks through the local optimal solution, and the efficiency is increased by 64%. In addition, in terms of average path, the fluctuation value stationary rate of the IAC is also higher than that of the traditional algorithm.

Compared with the traditional AC algorithm, Path data is selected to calculate the traditional AC algorithm and the IAC. In the traditional AC algorithm, ρ = 0.2, and in IAC, θ = 2. Other parameters are set as follows: m = number of nodes X = 1.5, Q = 1 000, NC _ max = 200. Simulation was performed using MATLAB R2018a software. The iteration curves of three different scales are shown in Figure 8 and Figure 9.

In different iteration graphs, the traditional AC algorithm is better than the IAC, and the initial value and final value are lower than those of the traditional AC algorithm, and the convergence effect from small and medium-scale problems is almost the same. Although the convergence effect is related to the scale of the problem, it has little influence. The IAC is better than the traditional AC algorithm.

It can be seen from Fig. 10 that the total distance decreases with the increase of the number of iterations, and the improved or traditional ant colony algorithm will converge in the iterations, but compared with the speed of the two, the improved algorithm is significantly higher than the traditional algorithm. In case of significant issues, these two algorithms show differences at the beginning of the iteration, with the improved algorithm demonstrating a clear advantage over the traditional one, continuously benefiting from local optimization and searching for better solutions. Although both algorithms converge simultaneously, the improvement speed of the improved algorithm is slightly faster than that of the underlying AC algorithm.

Through the data results in Table 2, it is learned that the traditional AC algorithm has a relatively slow search in the early stage. However, the IAC has made improvements on this. Compared with the traditional algorithm, this algorithm has better search efficiency and fewer iterations. To find the optimal path, the values of the optimal solution and the average path are more in line with the optimal solution of the optimal path result.

Table 2.

Comparison of Iteration Data Between the Two Algorithms

Algorithm	Worst value	Best value	Best value	Stable point	Final convergence value
AC	246.9km	229.94km	50	50	260
IAC	234.6km	224.88km	18	15	230
Improvement Rate	5	2.2	64	70	11.5

5

Conclusion

By analyzing the optimal path of express delivery, a heuristic formula is introduced into AC algorithm to initialize the initialization matrix of information elements, which solves the problem of slow search speed. In order to reduce the number of iterations, cross-search and dynamic update of information items are introduced, which greatly improves the speed of optimal path search. A series of experiments show that the IAC is superior to the traditional algorithm in terms of search ability, processing efficiency, convergence and control speed, and has a broad application prospect. Although the IAC is superior to the traditional AC algorithm, it still falls short relative to other algorithms. The following points can be considered for further modification of this algorithm: Strict control over the setting of parameters α and β, as improper settings can lead to slow solution speeds and poor quality. The AC algorithm involves large computational volumes and long solution times. In real-world scenarios, it is difficult for all ants to select the same route, making it hard to achieve such a situation under given iteration counts.

Sprache:: Englisch

Zeitrahmen der Veröffentlichung:: 1 Hefte pro Jahr
Fachgebiete der Zeitschrift:: Biologie, Biologie, andere, Mathematik, Angewandte Mathematik, Mathematik, Allgemeines, Physik, Physik, andere

Zeitschrift RSS Feed

The design of path optimization in express transportation based on an improved ant colony algorithm

Lingling Zhang

Online veröffentlicht: 27. Feb. 2025

Eingereicht: 14. Sept. 2024

Akzeptiert: 08. Jan. 2025

DOI: https://doi.org/10.2478/amns-2025-0128

SchlüsselwörterImproved Ant Colony Algorithm, Optimal Path, Maximum-Minimum Ant System

© 2025 Lingling Zhang, published by Sciendo

This work is licensed under the Creative Commons Attribution 4.0 International License.

Schlüsselwörter
Improved Ant Colony Algorithm, Optimal Path, Maximum-Minimum Ant System