The research on vehicle routing problem (VRP) beganin 1959. Based on the unremitting efforts of experts at home and abroad in this field, a series of intelligent algorithms have been introduced into the field of research, such as thetabu search algorithm, simulated annealing algorithm, ant colony algorithm, genetic algorithm, artificial neural network, and particle swarm optimization algorithm[1-9]. However, there are few articles on intelligent algorithms to explore the optimal decision-making problem of spare parts supply paths with time windows.

Spare parts are the premise and foundation for maintenance support. A timely and effective spare parts supply can provide a reliable guarantee of the smooth development of maintenance activities. The task-oriented spare parts supply and transportation require decision-makers to organize the transportation power reasonably, select the transportation route scientifically, deliver the spare parts of the customers on time and accurately, meet the customer’s spare parts time demands and quantity requirements properly, and achieve the maximum benefit perfectly. Generally speaking, scientific and reasonable transportation can not only reduce the cost of spare parts transportation, but also save capacity and improve the speed of spare parts turnover. There are many literatureson various supply problems. We need to select key points according to spare parts supply features and transportation characteristics. At present, the hot spot of theoretical research is the shortest path problem. It involves large-scale network nodes, while there are a few road network nodes between the transportation starting point and the transportation end. The transportation routes in the small range are even generally determined. Therefore, it is of great theoretical and practical significance to study the task-oriented optimization decision problem of the supply route. This paper uses an operational research method to establish a task-oriented optimization model of the spare parts supply routing problemand designs an intelligent solution algorithm to solve this model.

The supply route problem can be defined as a problem requiring the optimization of a set of transport routes for the flow of goods that can meet a series of constraints, in the background that a known transport vehicle from one or more warehouses to a multi geographically dispersed demand force. The purpose of VRP is to build a reasonable vehicle operation route and make the vehicle meet the minimum cost of transportation. The problem of task-oriented spare parts supply route optimization can be understood as a simple situation: there is only one spare parts warehouse, the transportation task is known, the vehicle starts from the spare parts warehouse, a transportation pathis chosen, and then it returns to the spare parts warehouse after the service of several spare parts. The output of the problem is to determine the number of transport vehicles needed and the transportation route of each vehicle. The requirement of the problem is to make the optimization decision of the spare parts supply route and achieve the maximum economic benefit, that is, to determine the required capacity (number of vehicles) and the transportation route of each car with a certain optimization goal and meet the requirements of the transportation task.

Therefore, the problems studied in this paper can be described in detail as the number of spare parts that are known to be shipped to each demand customer, and the spare parts warehouse can organize several transport vehicles of the same type to complete the transport task. Each vehicle has a capacity limit—the total amount of spare parts contained should not exceed its capacity. At the beginning, all the vehicles are in the warehouse, and our customers are distributed arbitrarily in the space. The number of vehiclesneeded and the route of each car must be determined, so that the spare parts can be transported to the customers in order. Finally, all the vehicles return to the spare parts warehouse.

The assumptions that need to be met are as follows:

· All transport vehicles start from the spare parts warehouse and eventually return to the spare parts warehouse;

· Every demand customer is only visited by a car once, and each vehicle can only serve one route;

· On every transport route, the sum of spare parts delivered to each customer cannot exceed the vehicle load.

Generally speaking, the arrival time of the spare parts is limited by the customer. Therefore, the vehicle routing problem has time constraints. This requires that the transportation process must be considered to meet the need first and then meet the general requirements. For further research, vehicle routing problems with time windows (VRPTW) are introduced here. Based on the traditional VRP, the VRPTW takes the time window constraint in consideration. The time window constraint can be divided into three types: hard time windows, soft time windows, and mixed time windows. The VRPTW problem includes three key problems: path finding, loading capacity restriction, and spare parts customer service order. The VRPTW must consider the demand of each customer for the time, so the determination of the customer service order is the key point that VRPTW should pay attention to[10-18].

In the process of spare parts transportation, the demand for spare parts delivery time is very high for each spare part. If the spare parts cannot be sent to the customer within the specified time, it will directly affect the economic benefit of the customer. Therefore, this paper focuses on the research of VRPTW.

For the choice of optimization target, transportation time and distance are priority factors. The requirements of the hard time window for each customer will be considered during the modeling process. The transportation distance, transportation damage, transportation cost, and other factors are proportional to the transportation distance. Thus, shortening the transportation distance, both from the macroscopic angle and from the micro angle, is beneficial to the improvement of the transport efficiency of spare parts. As a result, the shortest transportation distance is used as the optimization target to meet the military benefit while the economic benefit is also taken into account, which is beneficial to the improvement of the comprehensive transport efficiency of spare parts. Therefore, the optimization objective is determined as follows: the shortest total distance of all vehicles.

Assume that for an existing transport task, the number of spare parts delivered to the demand customer $i$ is ${{q}_{i}}$, and the demand customer $i$ has a time window $[0,{{b}_{i}}]$, which means that the vehicle must reach the demand customer $i$ before the time ${{b}_{i}}$. In addition, the spare parts warehouse also has a time window $\left[ {{a}_{0}},{{b}_{0}} \right]$, which indicates that the vehicle cannot leave the spare parts warehouse before ${{a}_{0}}$ and must return to the spare parts warehouse before or before the ${{b}_{0}}$. For each requirement customer $i$ and the vehicle $k$ definition variable ${{t}_{ik}}$, it indicates that at time ${{t}_{ik}}$, vehicle $k$ accesses the demand customer $i$. If the vehicle $k$ does not access the demand customer $i$, then ${{t}_{ik}}$ does not have any meaning. Suppose ${{a}_{0}}=0$, so that for all vehicles $k$,${{t}_{0k}}=0$. Set the number of customers that ${{n}_{k}}$ serves for the vehicle $k$, using the set ${{R}_{k}}$ to express the path passed by the vehicle $k$. The element ${{r}_{ik}}$ indicates that the order of the customer ${{r}_{ik}}$ in the path $k$ is $i$ (excluding the spare parts warehouse).

To facilitate the description of the problem, the commonly used symbols in the model are as follows:

· The number of vehicles needed is $V$, the loading capacity of each vehicle is $Q$, the number of spare parts for customer $i~$is$~{{q}_{i}}$, and ${{q}_{i}}<Q$;

· The demand customer set is $C$;

· The definition of a directed graph is $G$, the directed graph has $n+2$ vertices, the vertex $1,2,\cdots ,n$ represents spare parts demand customers, vertex $0$ indicates the spare parts warehouse when the vehicle leaves, and virtual $n+1$ represents the spare parts warehouse when the vehicle returns;

· The vertex $0,1,2,\cdots ,n+1$ is recorded as a set of $N$, and the collection of arcs among demand customers and between demand customers and spare parts warehouses is recorded as $A$. No arc begins at the vertex $n+1$ and no arc terminates at the vertex $0$;

· The distance between each $arc(i,j)$ corresponds to ${{d}_{ij}}$, its corresponding transport time is ${{t}_{ij}}$, and the corresponding quantity of transportation is${{q}_{ij}}$.

For each $arc~\left( i,j \right)$, $\left( i\ne j,i\ne n+1,j\ne 0 \right)$ and vehicle $k$,define the variable ${{x}_{ijk}}$ as

It is necessary to design a path with the minimum total transportation distance for all vehicles. This path should begin at the vertex $0$ and terminate at the vertex $n+1$. It ensures that the spare parts for each customer’s demand is satisfied. The hard time windows of the customers and the traffic constraints of the vehicles are not violated. By describing the above parameters, the mathematical model of VRPTW can be expressed as

S.t.

Equation (2) indicates that the total distance of transportation targets for all vehicles is the shortest.

Equation (3) represents that the number of customers of every path service is not more than the total number of customers. Among them, ${{n}_{k}}$ is the demand customer number of service on route $k$, and $n$ indicates the total number of customers.

Equation (4) indicates that the total amount of spare parts transported to each customer on each path is no more than the capacity limit of the vehicle.

Equation (5) represents the path composition of the $k$ vehicle.

Equations (6)-(8) indicate that each vehicle starts at the spare parts warehouse and finally returns to the spare parts warehouse after visiting the demand customer.

Equation (9) indicates that the vehicle must meet the time window requirements of the visiting customers during the driving process.

Equations (10)-(11) are value constraints.

The vehicle routing problem with hard time windows has been proven to be a NP difficult problem. At present, there are many algorithms to solve such problems. For large vehicle routing problems, there are genetic algorithms, greedy algorithms, tabu search algorithms, simulated annealing algorithms, and so on. In this paper, a model solving method based on the ant colony algorithm is designed, which makes the model feasible for large vehicle routing problems.

$m$:The number of ants in the ant colony;

$\alpha $: The information elicitation factor indicates the relative importance of pheromones;

$\text{ }\!\!\beta\!\!\text{ }$: The expected elicitation factor indicates the relative importance of visibility;

$\text{ }\!\!\rho\!\!\text{ }$: A coefficient that represents the attenuation of the amount of information within the time interval $(t,t+n)$, besides$0\le \text{ }\!\!\rho\!\!\text{ }\le 1$;

${{\tau }_{ij}}$: The intensity of the pheromone on the edge $e\left( {{v}_{i}},{{v}_{j}} \right)$;

${{\eta }_{ij}}$: The visibility of edge $e\left( {{v}_{i}},{{v}_{j}} \right)$, reflecting the degree of inspiration of the choice edge $e\left( {{v}_{i}},{{v}_{j}} \right)$. Generally there is ${{\eta }_{ij}}=1/Di{{s}_{ij}}$;

$P_{ij}^{k}$: The probability of an ant$k$being transferred to ${{v}_{i}}$ from a node $k$;

$\Delta {{\tau }_{ij}}$: The pheromone increment of the unit length of the ant k on the edge $e\left( {{v}_{i}},{{v}_{j}} \right)$;

$Di{{s}_{ij}}$: The distance from node ${{v}_{i}}$to node ${{v}_{j}}$ onthe side of connection ${{v}_{i}},{{v}_{j}}\in V.$

In the ant colony system, ants have the following characteristics: (1) Choose the transfer route by probability, and the probability is the function of the distance between nodes and the amount of information on the path; (2) After the completion of a cycle, a certain amount of pheromone is left on the path it has passed; (3) The pheromone of ants on the path gradually undergoes volatilization (attenuation). In the initial time, the pheromone amount on each path is equal. Ants in the ant colony system randomly select the transfer path and leave the pheromone of the path information on the path through which it passes. Later, the ants then choose the path according to the distribution of pheromones and the visibility of the feasible paths, making the better path pheromone increase. After a period of adjustment, all the ants tend to move along a path, which finds the optimal or approximate optimal path.

The general flow chart of solving the ant colony algorithm is given in this paper, as shown in Figure 1:

· Initialization:Set the initial value of the parameter: the pheromone given at the initial time ${{\tau }_{ij}}\left( 0 \right)=c$; pheromone increment $\Delta \tau \left( 0 \right)=c$; visibility weight factor ${{\eta }_{ij}}$. It is usually obtained by some heuristic algorithm, take ${{\eta }_{ij}}=1/Di{{s}_{ij}}$.

· Release the ant colony:The initial node is randomly given to record the starting point of ants, which is used as a symbol to decide whether ants search all paths.

· Choose the direction of movement according to probability: In every optimization process, ants choose the next node according to probability. The probability of ant selection node ${{v}_{i}}$ on node ${{v}_{j}}$ is determined by pheromone concentration ${{\tau }_{ij}}$ and visibility factor ${{\eta }_{ij}}$.

The transfer probability is expressed as

Among them, $allowe{{d}_{k}}=\left\{ V-tab{{u}_{k}} \right\}$ is the node that ants $k$ can choose in the next step, that is, the point connected with the current node, $V$ is the set of target nodes that ants can choose, $tab{{u}_{k}}$ represents the set of paths that the ant has passed by $k$, and the relative importance of the pheromone intensity information and the visibility information, respectively, by$\alpha $ and $\beta $ as two parameters, is generally determined by the experiment.

· Update the pheromone:Once a cycle is completed, the pheromone quantity on the obtained path is adjusted according to the following formulas:

Among them,$\Delta \tau _{ij}^{k}\left( t,t+1 \right)$ indicates that at the $\left( t,t+1 \right)$ time, $k$ ants remain on the pheromone on the side$e\left( {{v}_{i}},{{v}_{j}} \right)$,$\rho $is the attenuation coefficient of the pheromone, and$\text{ }\!\!\Delta\!\!\text{ }\tau _{ij}^{~}\left( t,t+1 \right)$ represents the increment of the pheromone on the $e\left( {{v}_{i}},{{v}_{j}} \right)$ sides of this cycle.

4.3.1. Dynamic Adjustment of Feasible Point Set Allowed_k

In the VRPTW problem, every ant needs to traverse all road network nodes. Therefore, in each iteration of the VRPTW problem, the number of movements of each ant is uncertain and can only be returned to the starting point (warehouse) as a sign to be constructed as a path. The tabu list $tab{{u}_{k}}$ of the walking network set contains two identical origin nodes.

In solving the VRPTW problem based on the ant colony algorithm, the path construction process is divided into two stages:

· If the initial location of an ant is not a spare parts warehouse, the first stage is the process of looking for the spare parts warehouse from the initial node, called “process I”. In this process, the feasible point set $allowe{{d}_{k}}$ should include the spare parts warehouse instead of the initial node. After arriving at the spare parts warehouse, the next step is to start from the spare parts warehouse and look for a path to return to the initial node, which is called “process II”. In this process, the spare parts repository cannot be contained in $allowe{{d}_{k}}$ but should contain initial nodes.

· If the initial location of the ant is a spare parts warehouse, “process I” is the first move of the ant, that is, the process of moving the spare parts warehouse to any other node. Process II is the process of ants returning to the spare parts warehouse. Therefore, in process I, $allowe{{d}_{k}}$ cannot contain the spare parts warehouse, and in process II, the spare parts repository must be included.

To sum up, in order to meet the needs of path search, the feasible point set $allowe{{d}_{k}}$ needs to be dynamically adjusted.

4.3.2. Selection Probability Optimization

When ants choose the next spare part and demand customers, they should consider the premise of satisfying vehicle capacity and time window constraint. To the next spare part, we need the path length and the amount of information on the path. The choice and optimality of the time window factor is influenced by the time window of the next spare part demand $j$ and the time of the current node to the demand customer $j$, and then the priority principle of the timing window factor optimality is the shorter waiting time priority and the smaller time window. Therefore, in the current node$i$, this paper improves the calculation formula of the state transition probability of the next spare part demand customer $j$ on the path $k$ to

Among them, $a$ and $b$ are weight coefficients,$a+b=1$, and $allowe{{d}_{k}}=\left\{ V-tab{{u}_{k}} \right\}$.

4.3.3. Parameters Optimization

In order to reduce search stagnation, we limit the pheromone to interval $\left[ {{\tau }_{\min }},{{\tau }_{\max }} \right]$. In this way, the pheromone concentration on a path will not be much larger than other paths, and the algorithm will no longer diffuse.

In the initial stage of ant colony optimization, a larger $\rho$ value can help ants choose paths. From the research results of document [19], it is known that when the pheromone volatilization factor $\rho$ is $0.5$, the overall performance of the algorithm is better. Therefore, in the path optimization process, when the optimal solution obtained by the ant colony algorithm has no obvious improvement in the cycle process, it should be adjusted according to the following formula:

Based on the improved ant colony algorithm, the algorithm flow of vehicle routing problem with hard time windows is designed in this paper. We can use the process of artificial ants accessing points to simulate the process of spare parts transportation vehicle service needs of customers. When the next spare part needs the customer to make the total amount exceed the number of existing spare parts, it returns to the spare parts warehouse, indicating that the car has completed the transportation. The car then starts to serve other spare parts and demand customers until all customers receive service. At this time, the artificial ants representing the vehicle have completed a cruise. When all the ants have completed a cruise, they write a cycle. Then, the number of vehicles needed is the number of ants who go all the way to the spare parts warehouse in the cycle. After a cycle, according to the advantages and disadvantages of each ant’s cruise, we calculate the increment of pheromones and update pheromones. After many cycles, most ants will choose the same path or find an approximate optimal path solution, and then solve it.

The concrete solution steps are as follows:

Step1 initialize system parameters, initial time $t=0$, iteration number $NC\_max=0$, read road network information, place m ants on the nodes representing the spare parts warehouse, set up an ant colony taboo table $tab{{u}_{k}}$ and feasible point set $allowe{{d}_{k}}$.

Step2 for each ant $i$, find the nodes that have not gone through the list of nodes, calculate the transfer probability according to the probability transfer Equation (16), and then use the roulette method[10] to select the customer $j$ for the next service of the ant.

Step3 after considering the spare parts supply of the customer $j$ of the path $(i,j)$, the total supply is $q$.If $q~<~Q$, jump to Step4, otherwise the node $j$ is added to the feasible point set $allowe{{d}_{k}}$ and jumps to Step5.

Step4 calculate the time to reach the demand customer $j$. If the time window is not satisfied, the node $j$is added to the tabu table $tab{{u}_{k}}$ to jump to Step2; otherwise, the node $j$ is rejoined in the feasible point set $allowe{{d}_{k}}$ and jumps to Step5.

Step5 ants return to the spare parts warehouse, and the number of vehicles increases by 1 (initial 0). Then, judge the feasible point set $allowe{{d}_{k}}$;if $allowe{{d}_{k}}$ is empty, jump to Step6; otherwise, get the unsearched nodes from $allowe{{d}_{k}}$, select the shortest node as the starting point, jump to Step2, and search the next node.

Step6 ants will update pheromone updates according to pheromone update Equations (14) and (15) after completing a cruise each time. Record the path and total length of each cruise.

Step7 when an ant completes the search, it searches for the shortest path length of the vehicle and the number of vehicles required in this iteration (the number of ant round-trip warehouses for the shortest path iteration of the shortest path). The optimal solution of this iteration is compared with the global optimal solution. If the optimal solution is superior to the global optimal solution, then the global optimal solution is replaced, and the pheromone is updated according to the pheromone updating Equations (14) and (15).

Step8 if the number of iterations reaches the maximum number of iterations or the global optimal solution is found, the optimal path solution and the number of vehicles will be output at the end of the program. Otherwise, clear tabu table, jump to Step2,and repeat the above steps.

It is necessary to explain that if the next service node is searched only according to the concentration of pheromone, the intelligent algorithm can easily converge to a path earlier. It cannot search for a shorter path in the space, that is, the phenomenon of stagnation occurs. In order to avoid premature convergence, Step2 used roulette to select the next node.

The warehouse command center collects the customer’s geographic location, customer order data, and the customer’s time window requirements.Based on the above data,the center draws a list of X spare parts supply tasks in the A area of April 23, 2018, as shown in Table 1.The warehouse A coordinates are (1.7km, 178km, 6.4m), which is responsible for the supply of X spare parts of 39 customers in the supply task list. Its transport vehicles are all type M vehicles. The load of a single transport vehicle is 170 X spare parts. As the area is close to the high speed, the road conditions and the rest time of the transporter are integrated, the average transportation time is 67km/h, and each car is equipped with two professional drivers. At 20:00 on April 22, 2018, the spare parts warehouseA finished loading 161 X spare parts according to the supply task list.According to the characteristics of the warehouse business and customer needs, the carrier with X spare parts must start from warehouse A at 8:00 on April 23, 2018 and then deliver the X spare parts in the hard time window specified by the customer. According to the company’s regulations, vehicles will return to warehouse A before 17:30 on April 23, 2018.

We can use this improved algorithm to help the warehouse plan the shortest transportation path under the time window constraint. According to the 3D coordinates and related terrain information drawing in the order list, the topographic map of the distributed area is drawn by MATLAB to determine the undulation and passing of the road,as shown in Figure 2. The actual distance between nodes can be calculated more accurately through this way.

Through the distribution of regional topographic maps, we find that the area of the 39 customers is a flat terrain, the road has a very small range of fluctuation, and good performance is achieved. Therefore, we can approximate the distribution distance between the distribution nodes in order by the three-dimensional space distance between point $i$ and point $j$.

Using the algorithmabove, the paper takes themaximum iterative algebra $NC\_\max =200$, the number of ants m=18, the information heuristic factor $\alpha $=1, the expected heuristic factor $\beta $=5, the information attenuation coefficient $\rho $=0.5, the probability weight $a$=0.6, and the probability weight $b$=0.4.

Through MATLAB operation, the output of this VRPTW problem is as follows:

· Number of vehicles used =1;

· The total length of the shortest path=324.4637km;

· The shortest route to visit the customers in order is

$\begin{matrix} & spare\text{ }part\text{ }warehouseA(start)\to XJ\to XC\to RN\to FP\to FQ\to XD\to TY\to XF\to AT\to TX\to ZW\to BA\to FG \\ & \to FM\to RJ\to RS\to AR\to BM\to AX\to AN\to TG\to XB\to ZB\to XN\to AZ\to ZM\to BG\to BT\to TF\to AX \\ & \to ZT\to JX\to JR\to XX\to AD\to JD\to XK\to AJ\to RY\to spare\text{ }part\text{ }warehouseA(destination) \\ \end{matrix}$

In other words, the result of fast solving the distribution problem by using the improved ant colony algorithm in this paper is: one car loading 161 spare parts should start from the spare parts warehouse A,pass XJ, XN, RN, FP, FQ, XD, TY, XF,and AT in order and finally returnto the spare parts warehouse A. This can satisfy all customers’ time window requirements and the company’s inherent working time limit. The shortest path for calculation is 324.4637 kilometers, as shown in Figure 3.

This paper focuses on the task oriented spare parts supply routing optimization decision-making problem, and its research results can be directly used for vehicle routing optimization decisions in wartime spare parts. Considering the time window requirements of the company’s working time limit and each customer’s spare parts demand, a mathematical optimization model is established for the shortest distance of all vehicles with the total distance of distribution. From the scale of the problem, it belongs to the small problem category, which can obtain the exact solution of the model solution, but it can further expand the model of this chapter. Based on the characteristics of the model, the traditional ant colony algorithm is improved to solve the model. The optimization result is the output vehicle number, the transportation route, and the total distance of each vehicle. At the same time, a VRPTW case considering terrain is used to prove the effectiveness of the improved genetic algorithm in solving the VRPTW problem.

The authors are appreciative of the useful programming guidance given by Mr.Yu, who majored in precision guidance and simulation technology precision guidance and simulation technology at the Army of Engineering University of PLA University.