An adaptive simulated annealing and artificial fish swarm algorithm for the optimization of multi-depot express delivery vehicle routing

Abstract

In this paper, the Capacitated Vehicle Routing Problem (CVRP) of multi-depot express delivery is investigated based on the actual express delivery business in Beijing and driving intention-based road network. An Adaptive Simulated Annealing and Artificial Fish Swarm Algorithm (A-SAAFSA) is proposed to solve the CVRP. The basic ideas are use a “certainty” probability to accept the worst solution through the Metropolis criterion in the search process, and a strategy of adjusting the swimming direction to avoid falling into the local optimal solution. Moreover, an adaptive visual strategy, which adjusts the visual range adaptively in real time according to the current solution quality, is used to ensure the efficient searching and accuracy of the algorithm. Experimental results show that the A-SAAFSA algorithm outperforms four well-known algorithms, namely simulated annealing and artificial fish swarm algorithm, artificial fish swarm algorithm, simulated annealing algorithm, and genetic algorithm.

Keywords

Express delivery CVRP road network simplification artificial fish swarm algorithm simulated annealing algorithm adaptive visual strategy

1. Introduction

The concept of express delivery was first born in the United States. It delivers a certain number of goods to customers at the right time in the form of distribution, realizing the seamless connection between production and consumption, and meeting customers’ consumption needs to the greatest extent. In recent years, with the booming of the Internet e-commerce industry, the express delivery business also develops rapidly, and express delivery companies have sprung up. In order to improve customer satisfaction and the competitiveness of enterprises under the premise of reducing the cost of distribution, more and more subject experts and enterprise operators pay attention to the problem of route optimization of express delivery.

The routing problem of express delivery is an important application field of vehicle routing problem (VRP). It means that through the reasonable arrangement of vehicles and routes, the express goods can be delivered to the customer site in an optimal way, so that both the delivery party and the receiving party can achieve the maximum benefits. VRP was first introduced by Dantzig and Ramser in 1959 [1]. It can be described as having one or more distribution centers and a number of scattered customer sites in a distribution network. Given the constraints, a vehicle and its corresponding routes are planned and calculated to minimize the target cost. VRP has attracted the attention of experts and scholars in many fields such as operations research, applied mathematics, logistics science, computer application, and enterprise management [2]. According to the actual constraints and the number of distribution centers, VRP can be divided into several sub-problems, which includes Capacitated Vehicle Routing Problem (CVRP), Vehicle Routing Problem with Time Windows (VRPTW), Vehicle Routing Problem with Pickup and Delivery (VRPPD), Multiple Depot Vehicle Routing Problem (MDVRP), and others [34]. Among them, CVRP mainly focuses on the limitation of vehicle overloading [5, 6, 7, 8], and VRPTW mainly focuses on the constraints of delivery time [9, 10, 11, 12]. These two sub-problems have a wide range of applications in practice, especially in express delivery business.

The combinatorial optimization problem is one in which the optimal solution is selected from a finite number of discrete states by mathematical methods in the form of objective function, constraint conditions and domain of definition. VRP is a typical combinatorial optimization problem. The algorithms used to solve such problems mainly evolving through three stages: accurate algorithms in the 1960s–1970s [13, 14], classic heuristic algorithms in the 1970s–1980s [11, 12], and intelligent heuristic algorithms [8, 9, 10, 15, 16, 17, 18, 19, 20, 21] after the 1980s. The early accurate algorithm can only solve problems with small-scale data; and the efficiency of classical heuristic algorithm cannot be guaranteed. Nowadays, the fast-developing intelligent heuristic algorithm approach has great advantages in solving large-scale complex problems. It can find a satisfactory solution that is close to the optimal solution at a faster speed. However, there is still a lot of room for improvement in the field of express delivery.

In this paper a novel and effective adaptive simulated annealing and artificial fish swarm algorithm (A-SAAFSA) is proposed to solve VRP in express delivery business. The main contributions are summarized as follows. Firstly, a basic A-SAAFSA algorithm is formulated for express delivery business. Secondly, a novel adaptive field of view strategy for the A-SAAFSA algorithm is defined and combined with the Metropolis criterion in SA to improve the accuracy and search efficiency of artificial fish. Thirdly, the model is supplemented and discussed from three different perspectives of company operation, customers, and drivers. The A-SAAFSA algorithm is applied to the distribution of express delivery business in Chaoyang District of Beijing. Results show that the proposed algorithm performs better than current Simulated Annealing and Artificial Fish Swarm Algorithm (SA-AFSA), Artificial Fish Swarm Algorithm (AFSA), Simulated Annealing Algorithm (SA), and Genetic Algorithm (GA).

The rest of this paper is arranged as follows. In Section 2, the related work of intelligent heuristic algorithm is introduced. In Section 3, the CVRP model is formulated according to the actual situation of express delivery business. In Section 4, based on the idea of AFSA and SA, an adaptive solution algorithm A-SAAFSA algorithm is proposed. In Section 5, the A-SAAFSA algorithm is used to optimize the model, and the effectiveness of the algorithm is verified by comparing to other four algorithms. The model is further supplemented from different optimization perspectives. In Section 6, the work of this paper is summarized.

2. The related work

Existing popular intelligent heuristic algorithms mainly include GA [8, 17, 18, 19, 21], SA [10, 20], and ACA [9, 15, 16, 21]. GA is mainly used to solve the knapsack problem and traveling salesman problem (TSP), SA is mainly used to solve the TSP and workshop scheduling problem, and ACA is mainly used for path planning of robots and unmanned aerial vehicles Intelligent heuristic algorithms have a wide range of applications in solving VRP. Scholars often try to integrate multiple algorithms to improve the performance of the algorithm. Davoodi et al. combined artificial bee colony algorithm with GA to effectively improve the performance of solving VRP by detecting bees [22]. Zidi et al. combined SA and tabu search algorithm to solve the ambulance path problem, and verified the superiority of the algorithm through comparative experiments [23]. Chen et al. proposed the IACATS algorithm, which combines the local search ability of tabu search algorithm with the global search ability of ACA to realize cold chain logistics distribution [24].

In 2002, Li Xiaolei et al. put forward a new bionic optimization algorithm-AFSA by observing the swimming and foraging behavior of fish swarm on the basis of studying the intelligent behavior of animal swarm [25]. The algorithm constructs artificial fish swarm according to the characteristics of fish swarm in real water area, and imitates the behavior of fish swarm to find the swimming strategy of the place with the highest food concentration through following, preying and swarming behavior. The algorithm changes the swimming trend of artificial fish in real time according to the quality of the current solution, and has better search and adjustment capabilities. In recent years, AFSA performs well and has been widely applied, such as, crowd evacuation in public places [26], vibration control of floating wind turbine [27], power distribution of communication system [28], and haze weather forecast [29]. However, when this algorithm is used to solve VRP [30, 31, 32, 33], it may lead to no considering of the solution strategy after falling into the local optimal solution. It also does not have an effective method for adjusting the visual field.

The A-SAAFSA algorithm proposed in this paper combines AFSA and SA to solve VRP in express delivery. The algorithm effectively adjusts the global search ability of artificial fish through adaptive vision strategy, and further jumps out of the local optimal solution through SA. The performance and convergence speed of the algorithm are further verified by comparative experiments.

3. Model of VRP in express delivery business

3.1 Problem description

According to the actual situation of express delivery in Beijing, this paper mainly studies CVRP with only one distribution center and with capacity constraints of vehicles. Figure 1 gives an example of this type of the problem, where the blue square 0 represents the distribution center, and the red circles 1–10 represent the customer sites. Through the planning and calculation of vehicles and routes, three vehicles can be selected to deliver the goods to achieve the minimum target cost. The specific delivery route of each vehicle is shown in Table 1.

Table 1
Arrangement of vehicles and routes

Vehicle ID	Delivery route
Vehicle 1	0->9->6->8->7->0
Vehicle 2	0->3->2->0
Vehicle 3	0->1->5->4->10->0

Figure 1.

An example of CVRP.

In the light of the actual delivery situation of a given express business in Chaoyang District of Beijing, this paper optimizes the delivery vehicles and routes satisfying the specific needs of customers under the given constraints to minimize the total cost. As shown in Fig. 2, the blue square 0 represents the distribution center, and the red circles 1–27 represent the express customer sites. Different from the previous example, this example shows that in the actual express delivery, the delivery route cannot be idealized as a simple straight path, which will lead to the wrong estimation of the distance and the wrong planning of vehicles and routes. Therefore, in the actual calculation of this paper, the actual geographic route of Google Maps is used as the basic route of VRP, model and optimize the express delivery problem according to the actual scene.

Figure 2.

Distribution of express business.

3.2 Establishment of model

Based on the description in the previous section, the goal of VRP is to provide the company’s operation manager with a more optimized vehicle allocation plan, thereby maximizing profits. In order to restore the specific delivery characteristics of urban express delivery business, a CVRP model with the total operating cost as the optimization objective is established.

Variables are divided into three categories and defined as follows:

1)
Variables related to vehicles:

$Q$ : Maximum cargo capacity of the vehicle;

$K$ : Set of delivery vehicles;

$k$ : Vehicle serial number, $k\in K$ ;

$\eta$ : Fixed cost of each vehicle (including management expense, driver salary, depreciation expense, etc.);
2)
Variables related to distribution centers and customer sites:

$N$ : Set of customer site addresses;

$q_{i}$ : Demand for customer site $i$ , $i\in N$ ;

$O$ : Address of distribution center;

$V$ : Set of distribution center and customer sites, $V=N\cup O$ ;

$C_{ij}$ : Fuel consumption cost from customer site $i$ to customer site $j$ ;
3)
Variables related to vehicles, distribution center and customer sites:

$\displaystyle x_{\textit{ijk}}=\left\{{{\begin{array}[]{ll}1&{\text{Vehicle }k% \text{ travels from customer site }i\text{ to }j}\\ 0&{\text{Otherwise}}\\ \end{array}}}\right.;$ $\displaystyle y_{ki}=\left\{{{\begin{array}[]{ll}1&{\text{Vehicle }k\text{ % delivers to customer site }i}\\ 0&{\text{Otherwise}}\\ \end{array}}}\right..$

From the perspective of company operation, the optimization goal $\phi$ of the express delivery route problem can be defined as in Eq. (1):

$\displaystyle\phi={\min}\,\eta\cdot K+\sum\limits_{i\in V}\sum\limits_{j\in V}% \sum\limits_{k\in K}C_{ij}x_{\textit{ijk}}$ (1) $\displaystyle\text{S.T.}\quad\sum\limits_{k\in K}\sum\limits_{i\in N}x_{% \textit{oik}}-\sum\limits_{k\in K}\sum\limits_{j\in N}x_{\textit{jok}}=0$ (2) $\displaystyle\sum\limits_{i\in N,i\neq j}x_{\textit{ijk}}=\sum\limits_{j\in N,% i\neq j}x_{\textit{ijk}}=y_{ki}\quad\forall k\in K$ (3) $\displaystyle\sum\limits_{i\in N}q_{i}y_{ki}\leqslant Q$ (4)

where Eq. (2) ensures that each distribution task takes the distribution center as the starting and ending site; Eq. (3) ensures that each customer site will be visited one and only one time; Eq. (4) ensures that the total demand of all customer sites distributed by each vehicle does not exceed its maximum cargo capacity.
3.3 Road network selection based on driving intention

Urban roads are intricate and road networks are scattered. We abandon the method of expressing the route directly using simple direct connections between customer sites. Instead, the actual geographic route of Google Maps is used as the basic route for VRP. As a result, the choice of the actual route is particularly important. However, it is too complicated to use all the possible routes between customer sites in the planning. In the actual logistics and distribution, every driver wants to choose a route with lower fuel consumption and shorter traveling time. They often make conditional choices of actual driving routes based on their own driving experience. Since the vehicles for logistics distribution are mainly heavy vehicles, the requirements for road conditions are relatively strict, and it is of no practical significance for the roads that do not meet the driving conditions even if the distance is shorter. According to the restrictions on heavy vehicles in Chaoyang District and Tongzhou District of Beijing (traffic time limit is 6:00–23:00) [34, 35], we only design the road for the non-restricted time to simplify the road network with the following principles:

•
Do not consider roads, road bridges, and road tunnels with a road height limit of less than 4 meters;
•
Do not consider small lanes with lower road grades;
•
For roads that pass through special area zones with traffic controls such as hospitals and schools, if there are other alternatives, these special zones will not be considered.

Based on the above analysis, the structure between the entire road network is optimized according to the driver’s driving intention and actual experience. Roads that are not suitable for heavy vehicles are also be discarded. By simplifying the road network, the search time for effective paths can be reduced, and the searching efficiency can be improved.
4. A-SAAFSA algorithm

4.1 Description of AFSA

Given an area of water, a fish often finds the region with the most food by swimming in the way of following and swarming. The idea of AFSA is to simulate the preying, following and swarming behavior of fish swarm by constructing artificial fish according to the characteristics of fish survival methods, and to realize the global search for the optimal solution [25].

The state of a single artificial fish can be recorded as a vector $S=(s_{1},s_{2},\ldots,s_{n})$ , where $s_{i}(i=1,2,\ldots,n)$ is the optimized target variable. The food concentration at the current position of the artificial fish is recorded as $\rho$ , the bulletin board is used to record the highest food concentration $\rho_{\textit{best}}$ and the corresponding artificial fish state $S_{\textit{best}}$ during the iteration.

In order to meet the scenario where the greater the food concentration, the more the fish swarm gathers, this paper transforms the minimization problem into a maximization problem, so the food concentration $\rho$ is defined as follows:

$\displaystyle\rho=\frac{1}{\phi}$ (5)

where $\phi$ is the optimized objective function shown in Eq. (1), and the total cost $\phi\neq 0$ in actual express delivery.

As shown in Fig. 3, the current state of the artificial fish is recorded as $S_{i}$ , and the target state is recorded as $S_{j}$ . Then the distance between the two states is expressed as $d_{ij}=\|{S_{i}-S_{j}}\|$ (where $\|\cdot\|$ is the Euclidean norm), and the next state is recorded as $S_{\textit{i\_next}}$ . The field of view of artificial fish Visual is a circular area centered on the current state, which represents the farthest range that the artificial fish can see, Step represents the moving step, $\delta$ represents the crowding factor, and trynumber represents the maximum number of trials.

Figure 3.

Moving strategy of artificial fish.

AFSA mainly summarizes the four basic types of behavior of fish swarm, namely, the following behavior, preying behavior, swarming behavior, and random behavior.

4.1.1 Following behavior

Assuming that the total number of artificial fishes in the field of view Visual of the artificial fish $S_{i}$ is $n$ , and the state of the artificial fish with the maximum food concentration $\rho_{\max}$ is $S_{\max}$ . When $\rho_{i}<\rho_{\max}$ and ${\rho_{\max}}\mathord{\left/{\vphantom{{\rho_{\max}}n}}\right.\kern-1.2pt}n>% \delta\rho_{i}$ , it means that the food concentration at the location is higher and the fish swarm is not crowded. Then the artificial fish will move forward in the direction of $S_{\max}$ according to the Eq. (5), otherwise the artificial fish will perform preying behavior.

$\displaystyle S_{\textit{i\_next}}=S_{i}+\textit{Step}\cdot\textit{rand}\cdot% \frac{S_{\max}-S_{i}}{\|{S_{\max}-S_{i}}\|}$ (6)

where rand is a random number between 0 and 1.

4.1.2 Preying behavior

Assuming that the food concentration of the artificial fish in the current state $S_{i}$ is $\rho_{i}$ , randomly search for state $S_{j}$ in the field of view Visual, and compare the food concentration of the two states. When $\rho_{j}>\rho_{i}$ , the artificial fish will move forward in the direction of $S_{j}$ according to Eq. (6). If the satisfactory state $S_{j}$ is still not found after trying trynumber times, the artificial fish will perform swarming behavior.

$\displaystyle S_{\textit{i\_next}}=S_{i}+\textit{Step}\cdot\textit{rand}\cdot% \frac{S_{j}-S_{i}}{\|{S_{j}-S_{i}}\|}$ (7)

4.1.3 Swarming behavior

Assuming that the total number of artificial fish in the current field of view Visual is $n$ , and the center position is $S_{c}$ . When ${\rho_{c}}\mathord{\left/{\vphantom{{\rho_{c}}n}}\right.\kern-1.2pt}n>\delta% \rho_{i}$ , it means that the food concentration in the center is higher and the fish swarm is not crowded. Then the artificial fish will move forward in the direction of $S_{c}$ according to Eq. (8); otherwise, the artificial fish will perform random behavior.

$\displaystyle S_{\textit{i\_next}}=S_{i}+\textit{Step}\cdot\textit{rand}\cdot% \frac{S_{c}-S_{i}}{\|{S_{c}-S_{i}}\|}$ (8)

4.1.4 Random behavior

The random behavior of the artificial fish is to randomly select a state within the field of view Visual and move one step in the direction according to Eq. (9).

$\displaystyle S_{\textit{i\_next}}=S_{i}+\textit{Step}\cdot\textit{rand}$ (9)

During the execution of the algorithm, the artificial fish will select one of the above four types of behavior according to its own state and current environment. The selection process is shown in Algorithm 1.

Algorithm 1: Fish movement strategy
1. Input: $S_{i}$
2. Initialization: FishNum, trynumber, Visual, step, $\delta$ , $\rho_{\max}$
3. if $\rho_{i}<\rho_{\max}$ && ${\rho_{\max}}\mathord{\left/{\vphantom{{\rho_{\max}}n}}\right.\kern-1.2pt}n>% \delta\rho_{i}$ :
4. Update current status $S_{i}$ according to Eq. (6);
5. return $S_{\textit{i\_next}}$
6. else:
7. for count in range trynumber:
8. if $\rho_{j}>\rho_{i}$ :
9. Update current status $S_{i}$ according to Eq. (7);
10. return $S_{\textit{i\_next}}$
11. if ${\rho_{c}}\mathord{\left/{\vphantom{{\rho_{c}}n}}\right.\kern-1.2pt}n>\delta% \rho_{i}$ :
12. Update current status $S_{i}$ according to Eq. (8);
13. return $S_{\textit{i\_next}}$
14. else
15. Update current status $S_{i}$ according to Eq. (9);
16. return $S_{\textit{i\_next}}$

The artificial fish searches for the maximum value of food concentration $\rho_{\textit{best}}$ and the corresponding state $S_{\max}$ through continuous selection and iteration of the moving strategy. It then updates the bulletin board to find the optimal solution for the optimization goal. This is shown in Algorithm 2.

Algorithm 2: AFSA
1. Input: Road network matrix Dist
2. Import Algorithm 1:Fish movement strategy
3. Initialization: FishNum, Max_gen, trynumber, Visual, step, $\delta$ , $\rho_{\textit{best}}$
4. while $i<=\textit{Max{\_}gen}$ :
5. Update the status of artificial fish $S_{i}$ according to Algorithm 1;
6. Calculate the concentration of food $\rho_{i}$ ;
7. if $\rho_{i}>\rho_{\textit{best}}$ :
8. $S_{\textit{best}}=S_{i}$ ;
9. $i=i+1$ ;
10. Output: $S_{\textit{best}}$ , $\rho_{\textit{best}}$

4.2 Description of SA

SA is a stochastic search optimization algorithm based on probability, which follows the solid annealing process. In the annealing process, the Metropolis criterion is used to accept the solution which is worse than the current solution with an acceptance probability. The acceptance probability is formulated in Eq. (10).

$\displaystyle P_{i}=\left\{{{\begin{array}[]{ll}1,&\phi_{i\_next}\leqslant\phi% _{i}\\ e^{-\frac{\Delta\phi}{T_{i}}},&\phi_{\textit{i\_next}}>\phi_{i}\\ \end{array}}}\right.$ (10)

where $P_{i}$ is the acceptance probability, $\phi_{i}$ is the objective function value at the current moment, $\phi_{\textit{i\_next}}$ is the objective function value at the next moment, $\Delta\phi=\phi_{\textit{i\_next}}-\phi_{i}$ , and $T_{i}$ is the annealing temperature at the current moment. When the minimum annealing temperature condition is not satisfied, the temperature will be cooled according to the temperature function shown in Eq. (11).

$\displaystyle T_{\textit{i\_next}}=\alpha T_{i}\quad 0<\alpha<1$ (11)

where $T_{\textit{i\_next}}$ is the annealing temperature at the next moment and $\alpha$ is the cooling coefficient. This is shown in Algorithm 3.

Algorithm 3: SA
1. Input: Road network matrix Dist
2. Initialization: Max_gen, $\phi_{\textit{best}}$ , $T_{0}$ , $\alpha$
3. while $i<=\textit{Max{\_}gen}$ :
4. Generate current solution $\phi_{i}$ ;
5. if $\phi_{\textit{best}}>\phi_{i}$ :
6. $\phi_{\textit{best}}=\phi_{i}$ ;
7. else
8. Calculate $P_{i}$ according to Eq. (10);
9. Generate random number rand;
10. if rand $\leqslant P_{i}$ :
11. $\phi_{\textit{best}}=\phi_{i}$ ;
12. Update $T_{i}$ according to Eq. (11);
13. Output: $\phi_{\textit{best}}$

4.3 Description of adaptive visual

In AFSA, the field of view Visual of the artificial fish is a fixed value, which is easy to fall into a local optimal solution. In order to improve the optimization accuracy and diversity of the algorithm, this paper defines the following adaptive view function:

$\displaystyle\textit{Visual}_{i}=\left\{{\begin{array}[]{l}\textit{Visual}_{% \min},\rho_{i}>\rho_{a}\\ \textit{Visual}_{\min}+({\textit{Visual}_{\max}-\textit{Visual}_{\min}})\frac{% \rho_{a}-\rho_{i}}{\rho_{\max}-\rho_{a}},\rho_{i}\leqslant\rho_{a}\\ \end{array}}\right.$ (12)

where $\textit{Visual}_{i}$ is the current field of view of the artificial fish, $\textit{Visual}_{\min}$ is the minimum field of view of the artificial fish, $\textit{Visual}_{\max}$ is the maximum field of view of the artificial fish, $\rho_{i}$ is the food concentration value found by the $i$ -th artificial fish in the current iteration, $\rho_{a}$ is the average value of the food concentration found by each artificial fish in the current iteration, $\rho_{\max}$ is the maximum food concentration value found by the artificial fish in the current iteration. In the current iteration, if the food concentration found by the artificial fish is lower than the average value, it can adaptively expand the field of view according to the average and maximum values, which is conducive to the faster approach to the optimal artificial fish. If the food concentration found by the artificial fish is greater than the average value, it indicates that the current artificial fish is in good condition, and the field of view needs to be reduced to further enhance the local search ability to find the maximum food concentration value.

4.4 Proposed A-SAAFSA

Based on the above description of SA and AFSA, we propose our A-SAAFSA algorithm, which combines AFSA and SA. The purpose is to ensure that the artificial fish can find the maximum of food concentration through the four basic behavior types: following, preying, swarming and random. In each iteration of the optimization process, the artificial fish accepts the state with lower food concentration with an acceptance probability as shown in Eq. (10), and then jumps out of the local optimal solution. In order to increase the optimization accuracy of the algorithm, an adaptive field of view function is proposed as shown in Eq. (12). According to the average and maximum value of food concentration in the current iteration, the field of view is adjusted in real time, which improves the global search ability of the algorithm. This is shown in Algorithm 4.

Algorithm 4: A-SAAFSA
1. Input: Road network matrix Dist
2. Import Algorithm 1:Fish movement strategy
3. Initialization: FishNum, Max_gen, trynumber, $\textit{Visual}_{\min}$ , $\textit{Visual}_{\max}$ , $\delta$ , $\rho_{\textit{best}}$ , $T_{0}$ , $\alpha$
4. while $i<=\textit{Max{\_}gen}$ :
5. Generate adaptive $\textit{Visual}_{i}$ according to Eq. (12);
6. Update current status $S_{i}$ according to Algorithm 1;
7. Calculate the concentration of food $\rho_{i}$ ;
8. if $\rho_{i}>\rho_{\textit{best}}$ :
9. $S_{\textit{best}}=S_{i}$ ;
10. else
11. Calculate $P_{i}$ according to Eq. (10);
12. Generate random number rand;
13. if rand $\leqslant P_{i}$ :
14. $S_{\textit{best}}=S_{i}$ ;
15. Update $T_{i}$ according to Eq. (11);
16. $i=i+1$ ;
17. Output: $S_{\textit{best}}$ , $\rho_{\textit{best}}$

The procedure of the algorithm is shown in Fig. 4.

5. Experimental analysis and discussion

The actual location data in this paper comes from Google Maps in Chaoyang District of Beijing. The experimental test environment is: Intel(R) Core(TM) i5 3.70 GHz processor, Windows10 operating system, and the programming environment used is MATLAB R2015b version.

5.1 Experimental result

With reference to the actual market delivery price, the fuel consumption price and the vehicle load information of the express delivery business, the specific parameters of CVRP model of express delivery business are set as in Table 2, and the parameters of the A-SAAFSA algorithm proposed in this paper are set as Table 3. According to the actual location information and road network information of a given express business in Chaoyang District of Beijing, the model is calculated 10 times with the A-SAAFSA algorithm. Through the comparison of the computed results, the vehicle distribution scheme with the best result is selected. The total cost of the delivery plan is 2,447.55 CNY for the setting in Tables 2 and 3. The specific arrangement of vehicles and routes is shown in Table 4, and the specific delivery routes are shown in Fig. 5.

Table 2
Parameters of express delivery business model

Parameter (unit)	Definition	Value
$Q$ (t)	Maximum cargo capacity of the vehicle	10
$K$ (per)	Maximum number of vehicles used	15
$\eta$ (CNY)	The fixed cost of each vehicle (including management expense, driver salary,	300
	depreciation expense, etc.)
$C$ (CNY)	Fuel consumption cost per kilometer	1.5

Table 3

Parameters of A-SAAFSA

Parameter	FishNum	Max_gen	trynumber	$\textit{Visual}_{\min}$
Value	10	300	500	10
Parameter	$\textit{Visual}_{\max}$	$\delta$	$T0$	$\alpha$
Value	20	0.8	100	0.95

Table 4

Result of A-SAAFSA

Vehicle ID	Delivery route
Vehicle 1	0->17->14->24->10->0
Vehicle 2	0->2->12->26->23->7->0
Vehicle 3	0->27->19->22->4->0
Vehicle 4	0->16->13->21->15->18->0
Vehicle 5	0->5->9->11->1->3->0
Vehicle 6	0->8->6->25->20->0

Figure 4.

Procedure of A-SAAFSA.

Figure 5.

Delivery route of the vehicle.

In order to better understand the solution performance of the algorithm, the iterative convergence curve of A-SAAFSA is shown in Fig. 6 according to the above-mentioned distribution scheme to further measure its effectiveness. The iterative convergence curve shows that in the first 30 iterations, the optimization curve of artificial fish swarm has a steep downward trend and a faster convergence speed. When the number of iterations increases, the optimization curve tends to be leveled off. It enters a stable state after the 208th iteration, and converges to the optimal solution of 2447.55.

Figure 6.

Iterative convergence curve of A-SAAFSA.

5.2 Comparative experiment with other algorithms

In order to test the effectiveness of A-SAAFSA algorithm, four algorithms of SA-AFSA, AFSA, GA, and SA are used for comparative experiments, and the performance of the proposed algorithm is studied through different tests.

Firstly, the effectiveness of the proposed adaptive visual function is verified. Under the same experimental environment and parameters, the visual range of the SA-AFSA algorithm is set to a fixed value of 16, and perform 10 operations on the established model. Through the comparison of the calculation results, the vehicle distribution scheme with the best result is selected. The total cost of the delivery plan is 2,45.45 CNY. The specific arrangements of vehicles and routes are shown in Table 5.

Table 5
Result of SA-AFSA

Vehicle ID	Delivery route
Vehicle 1	0->24->3->13->16->6->0
Vehicle 2	0->22->21->18->12->27->0
Vehicle 3	0->8->1->9->11->7->0
Vehicle 4	0->2->26->23->19->15->0
Vehicle 5	0->20->10->25->5->0
Vehicle 6	0->17->14->4->0

By comparing the result of the A-SAAFSA algorithm in Table 4 with that of the SA-AFSA algorithm, it can be seen that the former one gives a better result. Both algorithms use 6 vehicles for the delivery, however the A-SAAFSA algorithm is better than the SA-AFSA algorithm in fuel consumption. When the artificial fish is close to the global optimal solution, if the field of view is fixed, the searching accuracy cannot be effectively controlled, and the optimal solution will be missed. The proposed adaptive field of view function can adaptively change the field of view of the artificial fish according to the quality of the current solution. This improves the searching performance of the algorithm.

The iterative convergence curves of the A-SAAFSA algorithm and the SA-AFSA algorithm are shown in Fig. 7. The iterative convergence curves of the two algorithms are similar, but the SA-AFSA algorithm has reached the convergence state after the 82nd generation, while the A-SAAFSA algorithm only finds the local optimal solution in the 82nd generation. Obviously, due to the application of the adaptive field of view function, the artificial fish constantly tries to explore the local optimal solution. It finally converges near the 200th generation and finds a better solution than the SA-AFSA algorithm does.

Figure 7.

Iterative convergence curve of A-SAAFSA and SA-AFSA.

To further understand the performance of the A-SAAFSA algorithm, we continue to compare it with AFSA, GA and SA in the same experimental setting. The total cost of the distribution schemes of the three algorithms are shown in Table 6, and the specific arrangements of vehicles and routes are shown in Table 7.

Table 6

Comparison of the total cost

Algorithm	A-SAAFSA	AFSA	GA	SA
Total cost (CNY)	2447.55	2749.5	2874	2748.45

Table 7

Result of AFSA

Vehicle ID	Delivery route
Vehicle 1	0->8->10->24->20->16->0
Vehicle 2	0->22->14->4->0
Vehicle 3	0->21->18->15->19->12->2->0
Vehicle 4	0->7->13->6->25->0
Vehicle 5	0->17->0
Vehicle 6	0->26->23->27->0
Vehicle 7	0->1->9->11->3->5->0

Table 8

Result of GA

Vehicle ID	Delivery route
Vehicle 1	0->4->21->27->0
Vehicle 2	0->8->9->6->16->0
Vehicle 3	0->14->20->22->12->19->0
Vehicle 4	0->7->23->17->0
Vehicle 5	0->25->10->24->11->0
Vehicle 6	0->26->18->15->2->0
Vehicle 7	0->5->13->1->3->0

Table 9

Result of SA

Vehicle ID	Delivery route
Vehicle 1	0->14->13->22->7->0
Vehicle 2	0->8->10->24->4->0
Vehicle 3	0->27->23->26->0
Vehicle 4	0->2->12->19->18->21->15->0
Vehicle 5	0->17->0
Vehicle 6	0->20->25->6->5->0
Vehicle 7	0->3->11->9->1->16->0

Figure 8 shows the results of the four algorithms, A-SAAFSA, AFSA, GA, and SA. It shows that the total cost of SA is slightly lower than the other two algorithms and is higher than that of the A-SAAFSA algorithm. From the specific arrangement of vehicles and routes used in the paper, it can be seen that the three algorithms all use seven vehicles for the distribution, among which AFSA and SA both use a single car to distribute customer site 17, which virtually increases the total cost and cannot get the optimal solution. The comparison between the iterative convergence curve of the A-SAAFSA algorithm and the other three algorithms is shown in Fig. 8. The convergence speed of A-SAAFSA algorithm is faster than that of AFSA and GA, but the quality of the solution is obviously better than those of the two algorithms. Although the solution of SA is slightly better than that of AFSA and GA, the convergence speed is 2–3 times slower, and the optimal solution is still not found in the end.

Figure 8.

Iterative convergence curve of A-SAAFSA/AFSA/GA/SA.

In view of the above analysis, the proposed A-SAAFSA algorithm has good convergence, and the effects of global optimization and local optimization are better.

5.3 Supplement of model optimization

The express delivery model established in Section 2.2 is only from the perspective of the company’s operation to pursue the lowest total cost. However, in the actual distribution process, drivers and customers are the key links of the distribution chain. For customers, some special products have extremely high requirements for the delivery time, such as fresh products or urgent items, so they hope that the total delivery time is the shortest. For drivers, with a fixed delivery salary, they hope that the total fuel consumption of delivery is the least. Therefore, the model is further supplemented according to different requirements of the target audiences.

5.3.1 From the perspective of customers

The optimization objective $\phi_{c}$ is defined as follows:

$\displaystyle\phi_{c}={\min}\sum\limits_{i\in V}\sum\limits_{j\in V}\sum% \limits_{k\in K}t_{ij}x_{\textit{ijk}}$ (13) $\displaystyle\text{S.T.}\quad\sum\limits_{k\in K}\sum\limits_{i\in N}x_{% \textit{oik}}-\sum\limits_{k\in K}\sum\limits_{j\in N}x_{\textit{jok}}=0$ $\displaystyle\sum\limits_{i\in N,i\neq j}x_{\textit{ijk}}=\sum\limits_{j\in N,% i\neq j}x_{\textit{ijk}}=y_{ki}\quad\forall k\in K$ $\displaystyle\sum\limits_{i\in N}q_{i}y_{ki}\leqslant Q$

where $t_{ij}$ is the time from customer site $i$ to customer site $j$ .

With reference to the “2019 China Urban Traffic Report” [36], the speed value of the delivery vehicle is set as 20 km/h. Using the A-SAAFSA algorithm, the final distribution scheme is shown in Table 10. The scheme uses a total of 6 vehicles for delivery and takes an average of 2.45 hours.

Table 10

The result from the perspective of customers

Vehicle ID	Delivery route	Cost time ( $h$ )
Vehicle 1	0->7->2->23->27->0	1.705
Vehicle 2	0->8->11->3->1->17->0	3.935
Vehicle 3	0->15->9->10->25->0	2.715
Vehicle 4	0->13->14->4->0	2.310
Vehicle 5	0->26->12->19->18->21->22->0	2.240
Vehicle 6	0->5->16->6->24->20->0	1.820

5.3.2 From the perspective of drivers

The optimization objective $\phi_{d}$ is defined as follows:

$\displaystyle\phi_{d}={\min}\sum\limits_{i\in V}\sum\limits_{j\in V}\sum% \limits_{k\in K}\textit{fuel}_{ij}x_{\textit{ijk}}$ (14) $\displaystyle\text{S.T.}\quad\sum\limits_{k\in K}\sum\limits_{i\in N}x_{% \textit{oik}}-\sum\limits_{k\in K}\sum\limits_{j\in N}x_{\textit{jok}}=0$ $\displaystyle\sum\limits_{i\in N,i\neq j}x_{\textit{ijk}}=\sum\limits_{j\in N,% i\neq j}x_{\textit{ijk}}=y_{ki}\quad\forall k\in K$ $\displaystyle\sum\limits_{i\in N}q_{i}y_{ki}\leqslant Q$

where $\textit{fuel}_{ij}$ is the time from customer site $i$ to customer site $j$ .

With reference to the fuel consumption of heavy vehicles in Beijing, we calculate the fuel consumption by 0.3 $L$ per kilometer, and the final distribution scheme is shown in Table 11. The scheme uses a total of 6 vehicles for delivery, and the total fuel consumption is 129.54 $L$ .

Table 11

Result from the perspective of drivers

Vehicle ID	Delivery route	Fuel consumption ( $L$ )
Vehicle 1	0->21->11->9->14->0	25.89
Vehicle 2	0->26->23->2->19->15->0	17.55
Vehicle 3	0->16->10->8->4->0	23.04
Vehicle 4	0->3->1->13->25->0	21.96
Vehicle 5	0->5->24->20->6->22->0	20.52
Vehicle 6	0->17->18->12->27->7->0	20.58

Therefore, with the above-mentioned supplement to the express delivery model, different optimization models can be selected according to the requirement from different target audiences. For some special products, the model established from the perspective of customers is more time efficient. For fuel consumption, the model established from the perspective of drivers is more economical.

6. Conclusion

Based on the actual location and route information of Google Maps, combined with the actual delivery situation of a certain express service in Chaoyang District of Beijing, the A-SAAFSA algorithm is designed to solve the CVRP distribution model, which is established from the perspective of company operation. The experimental results show that the distribution plan obtained by A-SAAFSA algorithm realizes the distribution of 27 customer sites through 6 vehicles, and the total cost is 2,447.55 CNY. Compared with the other four intelligent algorithms, it is proved that the improved algorithm can accomplish the distribution task with less cost, and the algorithm convergence speed is faster and the solution accuracy is higher. However, there is still room for improvement in solving large-scale vehicle distribution problems. With the improvement of express delivery business, when the goods are delivered to the distribution site, the couriers need to sort and arrange the secondary delivery. The scope of secondary delivery is small, and mainly for residential and commercial districts with dense personnel, so it has important research value in the future development of express delivery.

Footnotes

Acknowledgments

We would gratefully acknowledge the support by the National Natural Science Foundation of China (NSFC) as the research program [grant numbers 61703270, 61803255, 62073071].

References

Dantzig

G.B.

and Ramser

J.H.

, The truck dispatching problem, Management Science 6 (1959), 80–91.

Bodin

L.D.

Golden

B.L.

Assad

A.A.

and Ball

M.O.

, Routing and scheduling of vehicles and crews: The state of the art, Computers and Operations Research 10 (1983), 67.

Pillac

Gendreau

Guéet

and Medaglia

A.L.

, A review of dynamic vehicle routing problems, European Journal of Operational Research 225 (2013), 1–11.

Braekers

Ramaekers

and Nieuwenhuyse

I.V.

, The vehicle routing problem: State of the art classification and review, Computers & Industrial Engineering 99 (2016), 300–313.

Ghosal

and Wiesemann

, The distributionally robust chance constrained vehicle routing problem, Operations Research 68 (2020), 716–732.

Helal

Pichon

Porumbel

Mercier

and Lefèvre

, The capacitated vehicle routing problem with evidential demands, International Journal of Approximate Reasoning 95 (2018), 124–151.

Teymourian

Kayvanfar

Komaki

G.M.

and Zandieh

, Enhanced intelligent water drops and cuckoo search algorithms for solving the capacitated vehicle routing problem, Information Sciences (2016), 334–335, 354–378.

Wang

K.Z.

Lan

S.L.

and Zhao

Y.X.

, A genetic-algorithm-based approach to the two-echelon capacitated vehicle routing problem with stochastic demands in logistics service, Journal of the Operational Research Society 68 (2017), 1409–1421.

Zhang

H.Z.

Zhang

Q.W.

Zhang

Z.Y.

and Liu

, A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows, Information Sciences 490 (2019), 166–190.

10.

Khodabandeh

Bai

L.H.

Heragu

S.S.

Evans

G.W.

Elrod

and Shirkness

, Modelling and solution of a large-scale vehicle routing problem at GE appliances & lighting, International Journal of Production Research 55 (2017), 1100–1116.

11.

Moccia

Cordeau

J.-F.

and Laporte

, An incremental tabu search heuristic for the generalized vehicle routing problem with time windows, Journal of the Operational Research Society 63 (2012), 232–244.

12.

Remy

Said

and Tom

V.W.

, The time window assignment vehicle routing problem with time-dependent travel times, Transportation Science 52 (2018), 261–276.

13.

Fisher

M.L.

, Optimal solution of vehicle routing problems using minimum K-trees, Operations Research 42 (1994), 626–642.

14.

Laporte

Nobert

and Desroschers

, Optimal routing under capacity and distance restrictions, Operations Research 33 (1985), 1050–1073.

15.

Yang

Z.Z.

and Xie

J.X.

, A parallel improved ant colony optimization for multi-depot vehicle routing problem, Journal of the Operational Research Society 62 (2011), 183–188.

16.

Zhang

S.A.

Gajpal

and Appadoo

S.S.

, A meta-heuristic for capacitated green vehicle routing problem, Annals of Operations Research 269 (2018), 753–771.

17.

Long

J.Y.

Sun

Z.Z.

Pardalos

P.M.

Hong

Zhang

S.H.

and Li

, A hybrid multi-objective genetic local search algorithm for the prize-collecting vehicle routing problem, Information Sciences 478 (2019), 40–61.

18.

Zou

X.X.

Liu

K.P.

and Li

W.L.

, A coordinated algorithm for integrated production scheduling and vehicle routing problem International Journal of Production Research 56 (2018), 5005–5024.

19.

H.J.

and Zhou

X.B.

, A GPS location data clustering approach based on a niche genetic algorithm and hybrid K-means, Intelligent Data Analysis 23 (2019), S175–S198.

20.

Manwar

Zafar

Podoleanu

and Avanaki

, An application of simulated annealing in compensation of nonlinearity of scanners, Applied Sciences 9 (2019), 1655.

21.

Ahmad

S.R.

Bakar

A.A.

and Yaaku

M.R.

, Ant colony optimization for text feature selection in sentiment analysis, Intelligent Data Analysis 23 (2019), 133–158.

22.

Davoodi

Golsefidi

M.M.

and Mesgari

M.S.

, A hybrid optimization method for vehicle routing problem using artificial bee colony and genetic algorithm, International Archives of the Photogrammetry, Remote Sensing & Spatial Information Sciences XLII-5 (2019), 293–297.

23.

Zidi

Al-Omani

and Aldhafeeri

, A new approach based on the hybridization of simulated annealing algorithm and tabu search to solve the static ambulance routing problem, Procedia Computer Science 159 (2019), 1216–1228.

24.

Chen

Gui

Ding

and Zhou

, Optimization of transportation routing problem for fresh food by improved ant colony algorithm based on tabu search, Sustainability 11 (2019), 1–22.

25.

X.L.

, A new intelligent optimization method-artificial fish school algorithm, Zhejiang University, 2003.

26.

Zong

X.L.

Wang

C.Z.

J.Y.

and Jiang

Y.L.

, Tree hierarchical directed evacuation network model based on artificial fish swarm algorithm, International Journal of Modern Physics C: Computational Physics & Physical Computation 30 (2019), 1–23.

27.

Jin

Xie

S.Y.

Lin

Y.F.

Wang

Y.M.

and Wang

, Optimization of tuned mass damper parameters for floating wind turbines by using the artificial fish swarm algorithm, Ocean Engineering 167 (2018), 130–141.

28.

Zhou

G.L.

Y.M.

Y.C.

Wang

X.L.

and Yu

M.C.

, Artificial fish swarm based power allocation algorithm for MIMO-OFDM relay underwater acoustic communication, IET Communications 12 (2018), 1079–1085.

29.

Z.W.

Cheng

M.Y.

Jin

F.F.

J.M.

Zhu

X.H.

and Weckman

, Selective ensemble based on extreme learning machine and improved discrete artificial fish swarm algorithm for haze forecast, Applied Intelligence 48 (2018), 1757–1775.

30.

Fei

O.Y.

, Research on port logistics distribution route planning based on artificial fish swarm algorithm, Journal of Coastal Research SI (2020), 78–80.

31.

Song

M.X.

J.Q.

Han

Y.Q.

Han

Y.Y.

Liu

L.L.

and Sun

, Metaheuristics for solving the vehicle routing problem with the time windows and energy consumption in cold chain logistics, Applied Soft Computing 95 (2020), 106561.

32.

Che

J.N.

Zhou

Zhang

X.Y.

Tong

Hou

L.Y.

Jia

S.Y.

and Zhen

Y.T.

, Application of hybrid artificial fish swarm algorithm based on similar fragments in VRP, Proceedings of the SPIE 10611 (2018), 106111L.

33.

Jia

S.Y.

Zhou

Yang

H.Q.

Zhen

Y.T.

Zhang

and Zhang

H.P.

, Application of artificial fish swarm algorithm in vehicle routing problem, Bio-inspired Computing: Theories and Applications 952 (2018), 1–12.

34.

ChaoYang District People’s Government of Beijing Municipality, http://www.bjchy.gov.cn/.

35.

Tongzhou District People’s Government of Beijing Municipality, http://www.bjtzh.gov.cn/.

36.

Baidu

Map.

,Transportation big data research center, Institute of data science, Tsinghua University, School of communications, Southeast University, Institute of Financial Strategy, Chinese Academy of Social Sciences, Saiwen Transportation Network, KuWeather, Baidu Apollo Platform, Baidu Sonar, Baidu Index, Baidu Encyclopedia, 2019 China Urban Traffic Report. http://jiaotong.baidu.com/landings/landing?id=50.

An adaptive simulated annealing and artificial fish swarm algorithm for the optimization of multi-depot express delivery vehicle routing

Abstract

Keywords

1. Introduction

2. The related work

3. Model of VRP in express delivery business

3.1 Problem description

Table 1 Arrangement of vehicles and routes

4.1 Description of AFSA

5. Experimental analysis and discussion

5.1 Experimental result

Table 2 Parameters of express delivery business model

Table 5 Result of SA-AFSA

5.3.1 From the perspective of customers

Footnotes

Acknowledgments

References

Table 1
Arrangement of vehicles and routes

Table 2
Parameters of express delivery business model

Table 5
Result of SA-AFSA