# Multiconstrained Network Intensive Vehicle Routing Adaptive Ant Colony Algorithm in the Context of Neural Network Analysis

Authors: Shaopei Chen; Ji Yang; Yong Li; Jingfeng Yang
Journal: Complexity
 (2017)

---

## Abstract

Neural network models have recently made significant achievements in solving vehicle scheduling problems. Adaptive ant colony algorithm provides a new idea for neural networks to solve complex system problems of multiconstrained network intensive vehicle routing models. The pheromone in the path is changed by adjusting the volatile factors in the operation process adaptively. It effectively overcomes the tendency of the traditional ant colony algorithm to fall easily into the local optimal solution and slow convergence speed to search for the global optimal solution. The multiconstrained network intensive vehicle routing algorithm based on adaptive ant colony algorithm in this paper refers to the interaction between groups. Adaptive transfer and pheromone update strategies are introduced based on the traditional ant colony algorithm to optimize the selection, update, and coordination mechanisms of the algorithm further. Thus, the search task of the objective function for a feasible solution is completed by the search ants. Through the division and collaboration of different kinds of ants, pheromone adaptive strategy is combined with polymorphic ant colony algorithm. It can effectively overcome some disadvantages, such as premature stagnation, and has a theoretical significance to the study of large-scale multiconstrained vehicle routing problems in complex traffic network systems.


---

## Body

## 1. Introduction

Network intensive vehicle service, which is an important part of the complex urban public transport network system, is an innovation representative of the shared economy model in the era of Internet +. The Internet service platform has been attracting increasing attention in the shared economy era by creating a new commercial and management mode to adapt the Internet economy. It is also perceived as a representative of the development direction of the new economy and business model. Moreover, optimizing the network intensive vehicle scheduling model and improving the scheduling efficiency, response speed, and cost savings are important measures to improve the quality of network intensive vehicle services. Thus, studies on supply-and-demand information matching and of the path optimization algorithm for developing network intensive vehicle services are of great significance. However, the vehicle scheduling problem on network intensive car rental is different from that of the classic vehicle scheduling problem. In the classic vehicle scheduling problem, the control center is assumed to know all the information related to optimal scheduling before the optimal scheduling instruction is executed, and the information does not change over time. In the era of Internet +, passenger demand information, such as location, time of demand, quantity demanded, travel time, and service time, is unknown and even dynamic before the path optimization. Furthermore, new information may have arrived or existing information may have changed. Therefore, dynamic vehicle routing problems (DVRPs) are more prominent in the network intensive vehicle scheduling problem. Moreover, the supply-and-demand information of network intensive vehicles is matched in real time seamlessly and dynamically and does not require manual docking and transmission. This overcomes a problem that network booking taxi is forbidden to parade showmanship on the road under the existing management system. Therefore, the significant difference between the network intensive and classic vehicle scheduling problems is the continuous development of and change in the demand type and quantity in the former based on the real-time interaction through the Internet. In addition, real-time dynamic resource scheduling is performed according to the change in demand. However, the first principle of passenger transport in network intensive vehicle scheduling is to minimize the response time and relatively lessen the cost factors. This is also an important feature that distinguishes it from the traditional transportation problem and the vehicle routing problem (VRP). Network intensive vehicle scheduling problem is a multiconstrained path planning problem that integrates the dynamic network flow problem with multiconditioned and multi-start-and-stop points.Studies on vehicle scheduling problem at home and abroad have gradually deepened in recent years. Studies on the target selection of modeling and consideration of constraints are mostly based on the simple extension of the traditional transportation problem and VRP. The single starting point and demand problem is extended to multiple starting points and demand problems. Moreover, the goal is extended from the single focus on cost minimization to the multiple objective optimizations of efficiency and cost [1–3]. Presently, no literature on the multiconstrained path problem of network intensive vehicles has been found, although some scholars have recently started to introduce some particular constraints into vehicle scheduling modeling. For instance, some scholars have established many kinds of dynamic vehicle scheduling models and designed concise and efficient heuristic algorithms for goods distribution or emergency material transportation vehicle scheduling problems [4–7]. Emergency material transportation vehicle scheduling models consider multitransport ways, multimaterials, multisupply points, and multidemand points, as they suppose that the number of vehicles, supply amount of materials and goods, and other parameters are dynamic. However, the goal of emergency material transportation is to minimize the total quantity of the goods that are not satisfied in the transport cycle. Although constraint is comprehensive in emergency material transportation vehicle scheduling models, vehicle scheduling under a dynamic demand still adopts the optimization method in a single cycle and limits the consideration of global optimization in multiple cycles [6, 7]. Other scholars similarly consider the vehicle dynamic scheduling problem under a vehicle shortage hypothesis and introduce minimum transportation time and cost into the goal. Nevertheless, the improvement of the vehicle scheduling efficiency is still limited to the optimal one in a single stage. The global consideration of dynamic vehicle scheduling problem is inadequate [8, 9]. Thus, many unsolved problems are elucidated in the research on network intensive vehicle scheduling problem. Therefore, considering the characteristics of DVRP with multiple constraints (DVRPMC), the construction and exploration of a simple intelligent algorithm with excellent performance are important for the construction of a network intensive vehicle scheduling service system.


## 2. DVRPMC Description and Mathematical Model

### 2.1. Problem Description

A network intensive vehicle scheduling problem is oriented to the personal travel mode. Therefore, it should involve objective and subjective conditions and is a typical vehicle routing problem with multiple constraints, involving time, vehicle, traffic, safety, and so on. As a result, a network intensive vehicle schedule problem, that is, DVRPMC, should consider passenger priority in the order of booking time, demand of vehicle pattern, billing method, traffic conditions, time window, capacitance, safe surveillance, and other conditions. This is to ensure that network intensive scheduling is universal and practical. The detailed problem description is as follows. (1) A car is assigned to the passenger (i.e., customer point) according to the nearby principle. (2) The nearest dispatch point (i.e., parking spot of booking car) is selected from a total ofK callable vehicles based on the time window limit to reach the customer point. If the vehicle arrives in advance, it must wait to serve the customer. (3) Different priorities are assigned according to passenger booking time. The highest grade is 1, and the lowest grade is R. High priority means that the passenger has significant weight. Thus, all aspects of priority should be satisfied. (4) Vehicles only consider passenger demands that are less than or equal to their carrying capacities. (5) Each passenger can select only one type of vehicle and charging method pattern and is only serviced by the selected car. (6) The passenger arrives at the target point and guides the vehicle to the nearest scheduled point. (7) For a transport service, the proper vehicle type, dispatch time, and path can minimize the time cost and obtain the highest response efficiency.Information in DVRPMC changes over time. DVRPMC should consider time factors. Time axis is introduced here. The whole scheduling cycle (such as a working day) in a dynamic scheduling environment is constructed as the time axis. The time each new demand triggers a cycle ist. At t, demand information is divided into four kinds according to the state of the vehicle: (1) vehicles that have completed the task, (2) vehicles in service or on the way to serve, (3) vehicles that have responded to the service demand but do not proceed to the demand spots, and (4) vehicles waiting for new demands. A series of key points can be constructed on the time axis to represent the dynamic problem, and a vehicle scheduling system can arrange a scheduling plan according to the identified key points. The following scheduling strategies are adopted. (1) The vehicle from a certain scheduling point returns to the nearest scheduling point at the end of the delivery. (2) The fairness principle is followed to prevent customer points from obtaining any vehicle service response. Each customer service response shall not be lower than the level of its own demand. (3) The goal of the network intensive vehicle transport service is to minimize the response time, that is, from the initial start of the demand to the time when the vehicle reaches the demand point.Compared with traditional VRP, the essence of DVRPMC is to create a vehicle scheduling plan for each customer point in the case of a known customer point distribution and the real-time development of any customer point. Moreover, many different vehicle models should be considered in DVRPMC. Thus, dynamic model selection and path arrangement are performed according to the passenger capacities of the models, the effect on the path, and the model requirements of passengers.


### 2.2. Mathematical Model

The mathematical model needs to satisfy the dynamic scheduling description. Therefore, the analysis mechanics can be described as follows: Firstly, this model is set to beW(t)=wti,i=1,2,3,4, which refers to the set of all key points at t (Class 4). It is used to represent the dynamic problem by constructing a series of key points on the time axis. wt1 refers to the completed transport task, where the vehicle returned to the nearest scheduling point (parking point). wt2 refers to a passenger being served or a vehicle on the way to the service. wt3 refers to the vehicle that responded to the service demand but is not yet at the customer point. wt4 represents a vehicle in waiting state. Class 2 in the implementation of the task cannot be changed. The other three classes, as schedulable network intensive vehicles, are recorded as K∈W(t) vehicles scheduled from the scheduling point (parking point) to n customers at t. Then, the scheduling task can be represented by a weighted graph Gt(V,E) at t, where V=(0,1,2,…,n) refers to a set of nodes, 0 refers to the scheduling point, n nodes refer to customer points, and E=dij,i,j∈V refers to a set of paths from i to j. Last, considering road conditions and various factors, a coefficient of road condition λij is used to represent the influence of road conditions on the scheduled vehicles. For the standard path, λij=1. If λij is better than the standard path, λij<1; otherwise, λij>1. The coefficient of the road condition is multiplied by the actual length of the path between distribution points. dij is equal to the equivalent path length in consideration of the path influence. L refers to a feasible path. f(L) refers to the cost corresponding to this path, that is, objective function. q refers to the quantity booked by the passenger. Qk refers to the maximum load of vehicle K. The importance of the priority of a customer point is represented by weight σi. The time window of passenger i is ai,bi. The model demand of passenger i is Gi. The billing method of passenger i is Fi. tijk refers to the travel time of vehicle K from the scheduling point to the customer point. The time vehicle K served at the starting point of passenger i is si. sik is a decision variable that represents the moment vehicle K reaches customer point i. Xijk is also a decision variable and can be represented as follows:(1)Xijk=1vechiclekfromitoj0others.DVRPMC aims to determine a set of paths. The travel time of each path should be minimal, and no vehicle should exceed its carrying capacityQk. A feasible solution under a different priority, model demand, different billing method, and road conditions is sought for highly efficient vehicle scheduling at minimum cost.First, considering the cost of vehicle scheduling,C0k refers to the fixed cost of using vehicle K. C1k refers to the operating cost of vehicle K in the unit distance. VkSP refers to the travel speed of vehicle K under standard road conditions. Scheduling cost mainly includes the fixed cost of vehicle K  C0kv and operating cost C1kv. C0kv=C0k∑Xijk(i,j=0,1,2,…,n;n∈k), and C1kv=C1k∑Xijkλijdij(i,j=0,1,2,…,n;n∈k). Second, the cost for waiting for customer Ciks is considered, and Ciks=μsik. μ refers to the wait cost in the unit of time. Finally, extra cost CiP is incurred if vehicle K arrives beyond the time window of the passenger. To set CiP linear increase(2)CiP=ci1max⁡ai-sik,0+ci2max⁡sik-bi,where ci1 refers to the wait cost of vehicle K in customer point i with priority r per unit time and ci2 refers to the penalty per unit time if vehicle K arrives after the time window of the customer with priority r.Therefore, the minimum objective function can be represented as(3)minfL=∑k=1kC0kv+C1kv+Ciks+∑i=1nCiP.Constraint conditions are as follows:(4)∑j=0n∑i=0nXijkqj≤Qkk=1,2,…,k(5)∑i=0n∑k=1kXijk=1j=0,1,2,…,n(6)∑j=1nX0jk=1k=1,2,…,k(7)∑i=1nXi0k-∑j=1nX0jk=0k=1,2,…,k(8)∑i=1nXi0k=1k=1,2,…,k(9)si+sik+tijk=sjk(10)λijdij=VkSPtijk(11)Xijk=1vechicleKfromitoj0others.Equation (3) refers to the objective function, which represents the minimum scheduling cost. Equation (4) refers to the sum of load capacities on a feasible path, which is not more than the maximum load of the vehicle. Equation (5) refers to a vehicle (vehicle model and billing method that satisfies the requirements) that is distributed once in each customer point. Equations (6)–(8) refer to the subpath of each vehicle. A vehicle starts from the scheduling point, arrives at the customer point to provide transport service, brings passengers to the objective point, and finally returns to the scheduling point. Equation (9) indicates that if a vehicle travels directly from node i to j, the arrival time at node j is equal to the sum of the arrival time node i, service time, and travel time from node i to j. Equation (10) indicates that path distance is equal to the product of standard speed and travel time under the influence of road conditions. Equation (11) refers to the decision variable Xijk, which is 0,1.


## 2.1. Problem Description

A network intensive vehicle scheduling problem is oriented to the personal travel mode. Therefore, it should involve objective and subjective conditions and is a typical vehicle routing problem with multiple constraints, involving time, vehicle, traffic, safety, and so on. As a result, a network intensive vehicle schedule problem, that is, DVRPMC, should consider passenger priority in the order of booking time, demand of vehicle pattern, billing method, traffic conditions, time window, capacitance, safe surveillance, and other conditions. This is to ensure that network intensive scheduling is universal and practical. The detailed problem description is as follows. (1) A car is assigned to the passenger (i.e., customer point) according to the nearby principle. (2) The nearest dispatch point (i.e., parking spot of booking car) is selected from a total ofK callable vehicles based on the time window limit to reach the customer point. If the vehicle arrives in advance, it must wait to serve the customer. (3) Different priorities are assigned according to passenger booking time. The highest grade is 1, and the lowest grade is R. High priority means that the passenger has significant weight. Thus, all aspects of priority should be satisfied. (4) Vehicles only consider passenger demands that are less than or equal to their carrying capacities. (5) Each passenger can select only one type of vehicle and charging method pattern and is only serviced by the selected car. (6) The passenger arrives at the target point and guides the vehicle to the nearest scheduled point. (7) For a transport service, the proper vehicle type, dispatch time, and path can minimize the time cost and obtain the highest response efficiency.Information in DVRPMC changes over time. DVRPMC should consider time factors. Time axis is introduced here. The whole scheduling cycle (such as a working day) in a dynamic scheduling environment is constructed as the time axis. The time each new demand triggers a cycle ist. At t, demand information is divided into four kinds according to the state of the vehicle: (1) vehicles that have completed the task, (2) vehicles in service or on the way to serve, (3) vehicles that have responded to the service demand but do not proceed to the demand spots, and (4) vehicles waiting for new demands. A series of key points can be constructed on the time axis to represent the dynamic problem, and a vehicle scheduling system can arrange a scheduling plan according to the identified key points. The following scheduling strategies are adopted. (1) The vehicle from a certain scheduling point returns to the nearest scheduling point at the end of the delivery. (2) The fairness principle is followed to prevent customer points from obtaining any vehicle service response. Each customer service response shall not be lower than the level of its own demand. (3) The goal of the network intensive vehicle transport service is to minimize the response time, that is, from the initial start of the demand to the time when the vehicle reaches the demand point.Compared with traditional VRP, the essence of DVRPMC is to create a vehicle scheduling plan for each customer point in the case of a known customer point distribution and the real-time development of any customer point. Moreover, many different vehicle models should be considered in DVRPMC. Thus, dynamic model selection and path arrangement are performed according to the passenger capacities of the models, the effect on the path, and the model requirements of passengers.


## 2.2. Mathematical Model

The mathematical model needs to satisfy the dynamic scheduling description. Therefore, the analysis mechanics can be described as follows: Firstly, this model is set to beW(t)=wti,i=1,2,3,4, which refers to the set of all key points at t (Class 4). It is used to represent the dynamic problem by constructing a series of key points on the time axis. wt1 refers to the completed transport task, where the vehicle returned to the nearest scheduling point (parking point). wt2 refers to a passenger being served or a vehicle on the way to the service. wt3 refers to the vehicle that responded to the service demand but is not yet at the customer point. wt4 represents a vehicle in waiting state. Class 2 in the implementation of the task cannot be changed. The other three classes, as schedulable network intensive vehicles, are recorded as K∈W(t) vehicles scheduled from the scheduling point (parking point) to n customers at t. Then, the scheduling task can be represented by a weighted graph Gt(V,E) at t, where V=(0,1,2,…,n) refers to a set of nodes, 0 refers to the scheduling point, n nodes refer to customer points, and E=dij,i,j∈V refers to a set of paths from i to j. Last, considering road conditions and various factors, a coefficient of road condition λij is used to represent the influence of road conditions on the scheduled vehicles. For the standard path, λij=1. If λij is better than the standard path, λij<1; otherwise, λij>1. The coefficient of the road condition is multiplied by the actual length of the path between distribution points. dij is equal to the equivalent path length in consideration of the path influence. L refers to a feasible path. f(L) refers to the cost corresponding to this path, that is, objective function. q refers to the quantity booked by the passenger. Qk refers to the maximum load of vehicle K. The importance of the priority of a customer point is represented by weight σi. The time window of passenger i is ai,bi. The model demand of passenger i is Gi. The billing method of passenger i is Fi. tijk refers to the travel time of vehicle K from the scheduling point to the customer point. The time vehicle K served at the starting point of passenger i is si. sik is a decision variable that represents the moment vehicle K reaches customer point i. Xijk is also a decision variable and can be represented as follows:(1)Xijk=1vechiclekfromitoj0others.DVRPMC aims to determine a set of paths. The travel time of each path should be minimal, and no vehicle should exceed its carrying capacityQk. A feasible solution under a different priority, model demand, different billing method, and road conditions is sought for highly efficient vehicle scheduling at minimum cost.First, considering the cost of vehicle scheduling,C0k refers to the fixed cost of using vehicle K. C1k refers to the operating cost of vehicle K in the unit distance. VkSP refers to the travel speed of vehicle K under standard road conditions. Scheduling cost mainly includes the fixed cost of vehicle K  C0kv and operating cost C1kv. C0kv=C0k∑Xijk(i,j=0,1,2,…,n;n∈k), and C1kv=C1k∑Xijkλijdij(i,j=0,1,2,…,n;n∈k). Second, the cost for waiting for customer Ciks is considered, and Ciks=μsik. μ refers to the wait cost in the unit of time. Finally, extra cost CiP is incurred if vehicle K arrives beyond the time window of the passenger. To set CiP linear increase(2)CiP=ci1max⁡ai-sik,0+ci2max⁡sik-bi,where ci1 refers to the wait cost of vehicle K in customer point i with priority r per unit time and ci2 refers to the penalty per unit time if vehicle K arrives after the time window of the customer with priority r.Therefore, the minimum objective function can be represented as(3)minfL=∑k=1kC0kv+C1kv+Ciks+∑i=1nCiP.Constraint conditions are as follows:(4)∑j=0n∑i=0nXijkqj≤Qkk=1,2,…,k(5)∑i=0n∑k=1kXijk=1j=0,1,2,…,n(6)∑j=1nX0jk=1k=1,2,…,k(7)∑i=1nXi0k-∑j=1nX0jk=0k=1,2,…,k(8)∑i=1nXi0k=1k=1,2,…,k(9)si+sik+tijk=sjk(10)λijdij=VkSPtijk(11)Xijk=1vechicleKfromitoj0others.Equation (3) refers to the objective function, which represents the minimum scheduling cost. Equation (4) refers to the sum of load capacities on a feasible path, which is not more than the maximum load of the vehicle. Equation (5) refers to a vehicle (vehicle model and billing method that satisfies the requirements) that is distributed once in each customer point. Equations (6)–(8) refer to the subpath of each vehicle. A vehicle starts from the scheduling point, arrives at the customer point to provide transport service, brings passengers to the objective point, and finally returns to the scheduling point. Equation (9) indicates that if a vehicle travels directly from node i to j, the arrival time at node j is equal to the sum of the arrival time node i, service time, and travel time from node i to j. Equation (10) indicates that path distance is equal to the product of standard speed and travel time under the influence of road conditions. Equation (11) refers to the decision variable Xijk, which is 0,1.


## 3. Design of Optimization Algorithm of DVRPMC Based on Adaptive Ant Colony Algorithm

Intelligent algorithms have made great achievements in solving vehicle scheduling problems, especially for adaptive ant colony algorithm. Adaptive ant colony algorithm provides not only a new idea for solving the complex combination of optimization problems, but also a scientific perspective to deal with VRPs with multiple constraints. The pheromone in the path is changed by adaptively adjusting the volatile factors in the operation process. It effectively overcomes the tendency of the traditional ant colony algorithm to fall easily into the local optimal solution and slow convergence speed to search for the global optimal solution [10, 11]. Considering DVRPMC, this paper proposes an adaptive ant colony algorithm to introduce adaptive transfer and pheromone update strategies based on a traditional ant colony algorithm to optimize the selection, update, and coordination mechanisms of the algorithm further. Thus, considering the diversity of the ant colony, a task with many constraint conditions is provided to reconnaissance ants. Therefore, the search task for the feasible solution for the objective function is completed by the search ants. Through the division and collaboration of different kinds of ants, pheromone adaptive strategy is combined with polymorphic ant colony algorithm to effectively overcome some disadvantages, including long computing time and susceptibility to premature stagnation.


### 3.1. Principle and Implementation of Basic Ant Colony Algorithm

Ant colony algorithm is proposed based on the research on the real ant colony behavior in the natural world. It is a kind of simulated evolutionary algorithm based on population and belongs to the random search algorithm. Dorigo et al. [12, 13] first proposed this method and made full use of the similarities between the food search process of an ant colony and the famous traveling salesman problem (TSP) to determine the shortest path from the ant nest to the food source through information exchange and cooperation among individuals to solve the TSP [14–18]. The principle and the method of the basic algorithm are as follows.M ants are placed on N nodes selected at random. An ant selects the next node or cycle it has not yet visited based on a criterion, τij(t), which is the concentration of residual information on the path from node i to node j at t. This is the information provided by the algorithm itself, and ηij is the initial information from node i transferred to node j. This initial information is provided with the problem to be solved. ηij=1/dij refers to an a priori value of node i to j. Thus, the probability that ant K at node i selects node j as the objective node at t is(12)Pijk=τijαtηijβt∑n∈allowedkτinαtηinβt,j∈allowedk0others,supposing that j∈Nik.α is the relative importance of the residual information and β is the relative importance of the expected value.N
i
k refers to all possible objective nodes. Nodes mean no access. Each ant maintains a list tabuk, which records all cities it has visited up to the present, to avoid multiple visits to the same node. Pijk refers to the probability that ant K transfers from node i to node j.After each ant has accessed alln nodes (i.e., a cycle), residual information must be updated and old information must be weakened to prevent residual information from inundating inspired information caused by excessive residual information. New information on the ant access path must be added to τij.(13)τijt+n=ρτijt+∑k=1τijk.ρ refers to the reserve part of residual information. 1-ρ refers to the weakened part of the residual information. ρ must be less than 1 to prevent the unlimited accumulation of information. Δτijk refers to the residual information content ant K left in the path from i to j in the access period t to (t+n).GambardeIIa and Dorigo et al. provided the Ant-Q (Quantity) algorithm model based on the basic ant colony algorithm [12]. Ant-Q algorithm is a reinforcement learning algorithm based on the Cellular Computing paradigm. Ant-Q’s results on the vehicle routing problem, which is conceptually similar to fuel reload, are better than other ant colony optimization algorithms, such as Ant-C (Cycle) and Ant-D (Density) or the genetic algorithm (GA).(14)Δτij=QLk,the  pheromone  antKleft  in  the  period  fromttot+10otherwise.Otherwise, if antK selects the path (i,j) in the period from t to (t+n), Q is a constant, and Lk refers to the total path length ant K selected in this cycle. If it does not select this path, (15)Δτij=0.According to the Ant-Q algorithm concept, each step (i.e., fromt to (t+1)) requires the update of the concentration of residual information, but not the update of the residual information concentration after waiting for all ants to complete the access to all n cities. Therefore, in the Ant-Q algorithm model, Δτij=Q/dij, where dij refers to the distance from node i to node j and Q/dij is the concentration of residual information; that is, the concentration of residual information increases with the decrease of the distance to a city.Therefore, the basic ant colony algorithm is mainly based on the combination of the principle of positive information feedback and a certain heuristic algorithm. This algorithm employs the random selection strategy in the process of constructing the solution. This selection strategy slows down the evolution. The positive feedback principle is designed to enhance the performance of the solution but is prone to stagnation. This is the root of the deficiency of the ant colony algorithm. Therefore, improving the selection strategy is necessary; that is, the selection strategy should be adapted based on the combination of deterministic and random selections. The evolution to a certain algebra dynamically adjusts the probability of deterministic selection in the search process. Thus, the evolution direction is basically determined. Dynamic adjustment at a particular time is based on the amount of information on the path [5]. Therefore, adaptive ant colony algorithm has increasingly attracted attention. This algorithm shrinks the gap in the quantity of information between the best and worst paths and appropriately enlarges the probability of random selection to conduct a complete search of the solution space with less than l to overcome the shortcomings of the basic ant colony algorithm effectively.


### 3.2. Principle and Design of Adaptive Ant Colony Algorithm

Drawing lessons from the polymorphic ant colony method of Yang et al. [1], this paper divides ants in the ant colony algorithm into two types, namely, reconnaissance and search ants, because of the multiconstrained and dynamic characteristics of network intensive vehicle routing problems. Reconnaissance ants complete local reconnaissance and search ants complete global search.Reconnaissance ants are endowed with multiconstrained tasks by the polymorphic ant colony method. Each customer point is regarded as the center to make local reconnaissance. Furthermore, a reconnaissance element is used to mark the reconnaissance result, in order to provide supplementary information for a search ant, and select the next customer point after arriving at this point. The local search method of the reconnaissance ant colony placesn reconnaissance ants in n passenger demand points, and each reconnaissance ant regards its location as the center from which to scout the feasibility of n-1 points. The greater the feasibility, the higher the reconnaissance element on the path. Moreover, the reconnaissance element consists of three parts: (1) capacity-constrained reconnaissance element with a weight coefficient of ω1, (2) time window matching reconnaissance element with a weight coefficient of ω2, and (3) reconnaissance element in several points nearest to reconnaissance center (i.e., 20 points are taken from 100 demand points) with a weight coefficient of ω3, and ω1+ω2+ω3=1, where 0<ω1,ω2,ω3<1. If the capacity constraint is satisfactory, the contribution to the reconnaissance element is recorded as ω1C1. If it is unsatisfactory, the contribution to the reconnaissance element is 0. The matching factor of the time window in the routing starting point determines the reconnaissance element contributed by the time window matching degree ω2εjiC2. Matching factor εji=L([aji,bji],[ai,bi])/(bi-ai) refers to the matching degree of the time window, and aji=aj+sj+tji. L([aji,bji],[ai,bi]) refers to the length of the overlapping parts of the two time windows. Under a fixed value of [aji,bji], εji is high if the overlapping part is large. That is, point j, which is the precursor of i, is reasonable from the angle of the time window. Passenger priority factors are considered in the search ant pheromone; that is, the factors are considered in the objective function but are not considered in the reconnaissance element. Moreover, to reduce the scout scope of reconnaissance ants, the statistic result of Quan and Wen [14] shows that the next node of a point is selected in several points nearest to this point in the path optimization solution without calculating all the remaining viable nodes. Thus, the optimization process can be accelerated and the solution is quite reliable, which can converge to the optimal solution with the probability of approaching 1. The reconnaissance result in ascending order is combined with the existing prior knowledge (integrated with max(PC) [14]) to generate another reconnaissance element, which is recorded as ω3δij, on the path from point i to j. δij(i,j=0,1,2,…,n-1;i≠j) is represented as follows:(16)δij=min⁡dixdijvechilekfromitoj0otherwise,where min⁡dix refers to the nearest distance from city i as the center to other cities n-1. To synthesize the total reconnaissance element of the above reconnaissance ants,(17)Sij=ξ1C1+ξ2εijC2+ξ3min⁡dixdijεji≠0jandiinmaxPC0others.Considering the need for a certain pheromone on the path at the initial moment, the amount of information of each path at the initial moment is set as(18)τij0=CSijSij≠0Cmin⁡dix,max⁡dixSij=0,where min⁡dix and max⁡dix refer to the minimum and maximum distances from point i, as the center, to other points n-1. C refers to the concentration of pheromone on each path at the initial moment and is a constant. Through the reconnaissance element trail marked by the reconnaissance ants, research ants can make a directional search with the assistance of the pheromone. This can improve efficiency and determine the optimal solution.The global search of the search ant colony draws lessons from the concept of the Ant-Q algorithm of Dorigo et al. [13] where the selection strategy is combined with the deterministic and random selection [1, 4]: (1) K is the number of search ants, ηij refers to the visibility of side (i,j), and ηij=1/f(dij), which reflects the heuristic degree transfer from node i to j and is different from ηij=1/dij in the basic ant colony algorithm model. The objective function is placed in the global scope given the best visibility. It reflects the big-picture thinking of ants and does not necessarily have to select the closest point in a large probability as the next point. However, each step of the ant must consider the objective function of overall optimization. (2) τij refers to the pheromone trail intensity of side (i,j), Pijk refers to state mobility probability of ant K from node i to node j, and j refers to the node that is not yet visited. When each ant selects the next node, two points should be considered while selecting the next service point under the premise of adhering to the vehicle capacity and time window constraints. One is visibility and the amount of information access to the next service point. Second is priority conditions priority-of-small time window and priority-of-shortest waiting time.The search ant colony is tasked to conduct a global search. At each customer point, reconnaissance element and the pheromone at each side select the next service point until they find and mark the best route. The formula for the probabilityPijk of the search ant colony k(k=1,2,…,n) that transfers from i to j at t during the movement is as follows:(19)Pijk=Q1τijαηijβ∑x∈akτijαηijβ+Q2θj/sjk-ajk+sjk-bjk∑x∈akθx/sxk-axk+sxk-bxkj∈ak0others,where ak refers to the set of the service points and destinations that ant K is allowed to select for the next step; α and β parameters reflect the relative importance the pheromone ants accumulated during the movement and heuristic information provided that the ants select the path, respectively; Q1 and Q2 are weight coefficients that satisfy 0≤Q1≤1, 0≤Q2≤1, Q1+Q2=1, and 0≤θj≤1, which refers to the taboo list (tabuk) each ant creates, where k=1,2,…,K (K refers to the sum of search ant colony) for recording the nodes that ant K has visited at t and the ants are forbidden to visit again in this cycle. The tabu list is cleared at the end of the cycle.


### 3.3. Adaptive Information Update Strategy

Traveling ants often cause blockage and stagnation. Ant colony algorithm easily leads to premature and local convergences. To solve this problem and improve the global convergence of ant colony algorithm and search speed, many studies proposed different strategies to update existing information [19–25]; for example, in the standard ant colony algorithm, when information is updated and as long as the ant is traversed, selecting the path can update the information on the path. This enhances the information on the path for optimal fitness and weakens the information on other paths; the other algorithms based on level change enable the ant to set several paths with relatively good fitness, and the degree of excellence of its solution determines the magnitude of information. These algorithms presented above are different. They mainly update the amount of information using the increasing or decreasing proportion of the fixed amount of information and ignore the distribution features of the solution. They improve the characteristics of the ant colony algorithm to a certain extent and are used to treat small-scale problems. This paper proposes a new adaptive information update strategy for solving the large-scale problems, which starts from the distribution state of the solution.In large-scale problems, the existence of a volatile coefficient reduces the amount of information on the path that has never been searched to be close to 0, which lowers the search ability of the algorithm on these paths. If the amount of information on a path is large, the amount of information on these paths is increased, and the chance that the path that has been searched is selected again is high. Moreover, the global search ability of the algorithm is influenced. A fixed changing volatile coefficient can improve the global search ability but reduces the convergence speed of the algorithm. Therefore, an adaptive method for changingτ is proposed to update the pheromone. The formula is as follows [11]:(20)τijt+1=1-ρτij+Δτij;while τ<τmin,(21)τijt+1=1-ρ1+ϕmτijt+Δτij;while τ>τmax,(22)τijt+1=1-ρ1-ϕmτijt+Δτij,where ϕ(m) is a function proportional to the number of convergences m. If the number of convergences m is higher, ϕ(m) is larger, as denoted by the equation below:(23)ϕm=Continuous  convergence  timesmc,where c is a constant. The distribution of the solution adaptively updates the amount of information to dynamically adjust the intensity of information on each path, causing the moderate concentration or scattering of ants to avoid premature convergence and local convergence and improving global search ability. The adaptive information update strategy adaptively updates the amount of information based on the distribution of the solution. Thus, it dynamically adjusts the intensity of information on each path, increases the diversity of the solution space, improves the global search ability, and prevents premature convergence and local convergence.


## 3.1. Principle and Implementation of Basic Ant Colony Algorithm

Ant colony algorithm is proposed based on the research on the real ant colony behavior in the natural world. It is a kind of simulated evolutionary algorithm based on population and belongs to the random search algorithm. Dorigo et al. [12, 13] first proposed this method and made full use of the similarities between the food search process of an ant colony and the famous traveling salesman problem (TSP) to determine the shortest path from the ant nest to the food source through information exchange and cooperation among individuals to solve the TSP [14–18]. The principle and the method of the basic algorithm are as follows.M ants are placed on N nodes selected at random. An ant selects the next node or cycle it has not yet visited based on a criterion, τij(t), which is the concentration of residual information on the path from node i to node j at t. This is the information provided by the algorithm itself, and ηij is the initial information from node i transferred to node j. This initial information is provided with the problem to be solved. ηij=1/dij refers to an a priori value of node i to j. Thus, the probability that ant K at node i selects node j as the objective node at t is(12)Pijk=τijαtηijβt∑n∈allowedkτinαtηinβt,j∈allowedk0others,supposing that j∈Nik.α is the relative importance of the residual information and β is the relative importance of the expected value.N
i
k refers to all possible objective nodes. Nodes mean no access. Each ant maintains a list tabuk, which records all cities it has visited up to the present, to avoid multiple visits to the same node. Pijk refers to the probability that ant K transfers from node i to node j.After each ant has accessed alln nodes (i.e., a cycle), residual information must be updated and old information must be weakened to prevent residual information from inundating inspired information caused by excessive residual information. New information on the ant access path must be added to τij.(13)τijt+n=ρτijt+∑k=1τijk.ρ refers to the reserve part of residual information. 1-ρ refers to the weakened part of the residual information. ρ must be less than 1 to prevent the unlimited accumulation of information. Δτijk refers to the residual information content ant K left in the path from i to j in the access period t to (t+n).GambardeIIa and Dorigo et al. provided the Ant-Q (Quantity) algorithm model based on the basic ant colony algorithm [12]. Ant-Q algorithm is a reinforcement learning algorithm based on the Cellular Computing paradigm. Ant-Q’s results on the vehicle routing problem, which is conceptually similar to fuel reload, are better than other ant colony optimization algorithms, such as Ant-C (Cycle) and Ant-D (Density) or the genetic algorithm (GA).(14)Δτij=QLk,the  pheromone  antKleft  in  the  period  fromttot+10otherwise.Otherwise, if antK selects the path (i,j) in the period from t to (t+n), Q is a constant, and Lk refers to the total path length ant K selected in this cycle. If it does not select this path, (15)Δτij=0.According to the Ant-Q algorithm concept, each step (i.e., fromt to (t+1)) requires the update of the concentration of residual information, but not the update of the residual information concentration after waiting for all ants to complete the access to all n cities. Therefore, in the Ant-Q algorithm model, Δτij=Q/dij, where dij refers to the distance from node i to node j and Q/dij is the concentration of residual information; that is, the concentration of residual information increases with the decrease of the distance to a city.Therefore, the basic ant colony algorithm is mainly based on the combination of the principle of positive information feedback and a certain heuristic algorithm. This algorithm employs the random selection strategy in the process of constructing the solution. This selection strategy slows down the evolution. The positive feedback principle is designed to enhance the performance of the solution but is prone to stagnation. This is the root of the deficiency of the ant colony algorithm. Therefore, improving the selection strategy is necessary; that is, the selection strategy should be adapted based on the combination of deterministic and random selections. The evolution to a certain algebra dynamically adjusts the probability of deterministic selection in the search process. Thus, the evolution direction is basically determined. Dynamic adjustment at a particular time is based on the amount of information on the path [5]. Therefore, adaptive ant colony algorithm has increasingly attracted attention. This algorithm shrinks the gap in the quantity of information between the best and worst paths and appropriately enlarges the probability of random selection to conduct a complete search of the solution space with less than l to overcome the shortcomings of the basic ant colony algorithm effectively.


## 3.2. Principle and Design of Adaptive Ant Colony Algorithm

Drawing lessons from the polymorphic ant colony method of Yang et al. [1], this paper divides ants in the ant colony algorithm into two types, namely, reconnaissance and search ants, because of the multiconstrained and dynamic characteristics of network intensive vehicle routing problems. Reconnaissance ants complete local reconnaissance and search ants complete global search.Reconnaissance ants are endowed with multiconstrained tasks by the polymorphic ant colony method. Each customer point is regarded as the center to make local reconnaissance. Furthermore, a reconnaissance element is used to mark the reconnaissance result, in order to provide supplementary information for a search ant, and select the next customer point after arriving at this point. The local search method of the reconnaissance ant colony placesn reconnaissance ants in n passenger demand points, and each reconnaissance ant regards its location as the center from which to scout the feasibility of n-1 points. The greater the feasibility, the higher the reconnaissance element on the path. Moreover, the reconnaissance element consists of three parts: (1) capacity-constrained reconnaissance element with a weight coefficient of ω1, (2) time window matching reconnaissance element with a weight coefficient of ω2, and (3) reconnaissance element in several points nearest to reconnaissance center (i.e., 20 points are taken from 100 demand points) with a weight coefficient of ω3, and ω1+ω2+ω3=1, where 0<ω1,ω2,ω3<1. If the capacity constraint is satisfactory, the contribution to the reconnaissance element is recorded as ω1C1. If it is unsatisfactory, the contribution to the reconnaissance element is 0. The matching factor of the time window in the routing starting point determines the reconnaissance element contributed by the time window matching degree ω2εjiC2. Matching factor εji=L([aji,bji],[ai,bi])/(bi-ai) refers to the matching degree of the time window, and aji=aj+sj+tji. L([aji,bji],[ai,bi]) refers to the length of the overlapping parts of the two time windows. Under a fixed value of [aji,bji], εji is high if the overlapping part is large. That is, point j, which is the precursor of i, is reasonable from the angle of the time window. Passenger priority factors are considered in the search ant pheromone; that is, the factors are considered in the objective function but are not considered in the reconnaissance element. Moreover, to reduce the scout scope of reconnaissance ants, the statistic result of Quan and Wen [14] shows that the next node of a point is selected in several points nearest to this point in the path optimization solution without calculating all the remaining viable nodes. Thus, the optimization process can be accelerated and the solution is quite reliable, which can converge to the optimal solution with the probability of approaching 1. The reconnaissance result in ascending order is combined with the existing prior knowledge (integrated with max(PC) [14]) to generate another reconnaissance element, which is recorded as ω3δij, on the path from point i to j. δij(i,j=0,1,2,…,n-1;i≠j) is represented as follows:(16)δij=min⁡dixdijvechilekfromitoj0otherwise,where min⁡dix refers to the nearest distance from city i as the center to other cities n-1. To synthesize the total reconnaissance element of the above reconnaissance ants,(17)Sij=ξ1C1+ξ2εijC2+ξ3min⁡dixdijεji≠0jandiinmaxPC0others.Considering the need for a certain pheromone on the path at the initial moment, the amount of information of each path at the initial moment is set as(18)τij0=CSijSij≠0Cmin⁡dix,max⁡dixSij=0,where min⁡dix and max⁡dix refer to the minimum and maximum distances from point i, as the center, to other points n-1. C refers to the concentration of pheromone on each path at the initial moment and is a constant. Through the reconnaissance element trail marked by the reconnaissance ants, research ants can make a directional search with the assistance of the pheromone. This can improve efficiency and determine the optimal solution.The global search of the search ant colony draws lessons from the concept of the Ant-Q algorithm of Dorigo et al. [13] where the selection strategy is combined with the deterministic and random selection [1, 4]: (1) K is the number of search ants, ηij refers to the visibility of side (i,j), and ηij=1/f(dij), which reflects the heuristic degree transfer from node i to j and is different from ηij=1/dij in the basic ant colony algorithm model. The objective function is placed in the global scope given the best visibility. It reflects the big-picture thinking of ants and does not necessarily have to select the closest point in a large probability as the next point. However, each step of the ant must consider the objective function of overall optimization. (2) τij refers to the pheromone trail intensity of side (i,j), Pijk refers to state mobility probability of ant K from node i to node j, and j refers to the node that is not yet visited. When each ant selects the next node, two points should be considered while selecting the next service point under the premise of adhering to the vehicle capacity and time window constraints. One is visibility and the amount of information access to the next service point. Second is priority conditions priority-of-small time window and priority-of-shortest waiting time.The search ant colony is tasked to conduct a global search. At each customer point, reconnaissance element and the pheromone at each side select the next service point until they find and mark the best route. The formula for the probabilityPijk of the search ant colony k(k=1,2,…,n) that transfers from i to j at t during the movement is as follows:(19)Pijk=Q1τijαηijβ∑x∈akτijαηijβ+Q2θj/sjk-ajk+sjk-bjk∑x∈akθx/sxk-axk+sxk-bxkj∈ak0others,where ak refers to the set of the service points and destinations that ant K is allowed to select for the next step; α and β parameters reflect the relative importance the pheromone ants accumulated during the movement and heuristic information provided that the ants select the path, respectively; Q1 and Q2 are weight coefficients that satisfy 0≤Q1≤1, 0≤Q2≤1, Q1+Q2=1, and 0≤θj≤1, which refers to the taboo list (tabuk) each ant creates, where k=1,2,…,K (K refers to the sum of search ant colony) for recording the nodes that ant K has visited at t and the ants are forbidden to visit again in this cycle. The tabu list is cleared at the end of the cycle.


## 3.3. Adaptive Information Update Strategy

Traveling ants often cause blockage and stagnation. Ant colony algorithm easily leads to premature and local convergences. To solve this problem and improve the global convergence of ant colony algorithm and search speed, many studies proposed different strategies to update existing information [19–25]; for example, in the standard ant colony algorithm, when information is updated and as long as the ant is traversed, selecting the path can update the information on the path. This enhances the information on the path for optimal fitness and weakens the information on other paths; the other algorithms based on level change enable the ant to set several paths with relatively good fitness, and the degree of excellence of its solution determines the magnitude of information. These algorithms presented above are different. They mainly update the amount of information using the increasing or decreasing proportion of the fixed amount of information and ignore the distribution features of the solution. They improve the characteristics of the ant colony algorithm to a certain extent and are used to treat small-scale problems. This paper proposes a new adaptive information update strategy for solving the large-scale problems, which starts from the distribution state of the solution.In large-scale problems, the existence of a volatile coefficient reduces the amount of information on the path that has never been searched to be close to 0, which lowers the search ability of the algorithm on these paths. If the amount of information on a path is large, the amount of information on these paths is increased, and the chance that the path that has been searched is selected again is high. Moreover, the global search ability of the algorithm is influenced. A fixed changing volatile coefficient can improve the global search ability but reduces the convergence speed of the algorithm. Therefore, an adaptive method for changingτ is proposed to update the pheromone. The formula is as follows [11]:(20)τijt+1=1-ρτij+Δτij;while τ<τmin,(21)τijt+1=1-ρ1+ϕmτijt+Δτij;while τ>τmax,(22)τijt+1=1-ρ1-ϕmτijt+Δτij,where ϕ(m) is a function proportional to the number of convergences m. If the number of convergences m is higher, ϕ(m) is larger, as denoted by the equation below:(23)ϕm=Continuous  convergence  timesmc,where c is a constant. The distribution of the solution adaptively updates the amount of information to dynamically adjust the intensity of information on each path, causing the moderate concentration or scattering of ants to avoid premature convergence and local convergence and improving global search ability. The adaptive information update strategy adaptively updates the amount of information based on the distribution of the solution. Thus, it dynamically adjusts the intensity of information on each path, increases the diversity of the solution space, improves the global search ability, and prevents premature convergence and local convergence.


## 4. Case Analysis

The DVRPMC optimal model and algorithm based on ant colony algorithm have many constrained conditions and parameters. To verify the performance of the algorithm, the customer point priority, service time of customer point, coefficient of road condition, vehicle wait cost, and other constrained conditions have not yet been considered in this case analysis. The objective function in the model is also simplified as the path distance. In this case analysis, 15 customer points were distributed in a square region in the edge length of 8 km. Table1 illustrates the customer points’ coordinates and related demand for passenger capacity, respectively. The region has two scheduling points (parking points). The coordinates are (-2,-2) and (3,3), which own five and eight vehicles, respectively. The maximum passenger capacity of each vehicle is four.Table 1
Coordinates of customer points and demand for passenger capacity (DPC).
Number
Coordinates
DPC
(1)
0, −1.3
2
(2)
0, 1.5
1
(3)
−2.1, −2.1
3
(4)
3.9, 3.1
4
(5)
−2.8, −1.1
2
(6)
−2.3, 0.2
1
(7)
2.1, 0
1
(8)
1.9, −1
3
(9)
0.96, −3.2
3
(10)
−2.5, −1.7
2
(11)
−2.98, 1.4
1
(12)
1.97, 0.9
4
(13)
2.0, 1.9
2
(14)
−2.9, −1.7
2
(15)
−3.8, 2.4
2The VRP standard case library of Solomon and Desrosiers [26] is used for detection. The Solomon and Desrosiers case library is divided into three categories: Class C, Class R, and Class RC. The customer points in Class C are distributed in cluster types. The customer points in Class R are distributed at random. The customer points in Class RC are the mixed-half cluster type. This case analysis is conducted in the hardware environment of Intel Pentium IV 3.0 with 1 G memory. VC language is used for the programming of the algorithm and to calculate R and C. The result is compared with the optimal solution from several existing algorithms. The parameters of the algorithm are α = 1, β = 2, and ρ = 0.8. The iteration number is 50. The results of 10 times the calculation are shown in Table 2.Table 2
Experimental results.
Number
RC
R
Optimal solution
Iteration number
Optimal solution
Iteration number
(1)
1526
18
1488
20
(2)
1577
25
1501
19
(3)
1456
21
1401
32
(4)
1411
19
1389
29
(5)
1511
24
1435
33
(6)
1523
30
1367
35
(7)
1489
33
1478
28
(8)
1456
31
1501
21
(9)
1501
29
1459
34
(10)
1531
20
1347
27Table2 shows that the optimal solutions of RC and R are mostly in the twenties. The calculation time is not more than 16 s in the hardware environment of Intel Pentium IV 3.0 with 1 G memory. Thus, the optimal solution convergence is faster than that of the standard ant colony algorithm. To compare the calculation results, standard genetic, adaptive genetic, and ant colony optimal adaptive algorithms are used to stimulate the case study. The obtained parameters in the case of 10 search times for the Class RC are shown in Table 3.Table 3
Comparison of the calculation results of various algorithms.
Parameters
RC
SGA
ASGA
DVRPMC
Number of vehicles
4.98
4.25
3.32
Iteration number
43.2
45.6
27.8
Traveling distance
1582.47
1475.60
1409.70To compare the calculation results, the average number of vehicles in Table3 up to two digits after the decimal point is taken. The calculation result shows that, in Class RC, the DVRPMC calculation results of the average number of vehicles and traveling distances are the best. Thus, the calculation result of the adaptive multiconstrained ant colony algorithm is stable with short traveling distance and high calculation efficiency.


## 5. Conclusion

In the context of neural network analysis, this paper analyzes the existing ant colony algorithm and proposes a multiconstrained network intensive vehicle routing optimal model and algorithm based on the adaptive ant colony algorithm. Drawing lessons from the adaptive polymorphic ant colony algorithm, the adaptive multiconstrained network intensive vehicle ant colony algorithm in this paper is used to collaboratively solve the problems through different types of ants. It overcomes the shortcomings of the traditional ant colony algorithm of having one ant colony with low algorithm efficiency. The ant colony can exchange planning information during the problem-solving process and maintain diversity in the search process because of the interaction among populations. Therefore, through the further use of the adaptive information update strategy, the algorithm of introducing the interaction among populations performs better than the traditional algorithm. Finally, this paper conducts a simulation experiment using specific examples. The experimental result shows that the adaptive multiconstrained ant colony algorithm has better solving efficiency and results than the standard ant colony algorithm. Therefore, for large-scale DVRPMC in network intensive vehicle scheduling, the adaptive multiconstrained and colony algorithm has significant superiority. Through the division and collaboration of different kinds of ants, pheromone adaptive strategy is combined with polymorphic ant colony algorithm; the algorithm given in this paper can effectively overcome some disadvantages, such as premature stagnation, and has a theoretical significance to the study of large-scale multiconstrained vehicle routing problems in complex traffic network systems. The established general mathematical model can be used in future studies, involving verifying further its result and efficiency in the case study of simulation under different passenger priorities, different road conditions, spatiotemporal traffic networks, and other cases’ study of the optimal routing search method of real-time network intensive vehicle scheduling in a dynamic environment intensively. Furthermore, the algorithm provided in this paper should be significant for the further study on routing problem in the dynamic environment of a spatial and temporal complexity traffic network.



---

*Source: 8594792-2017-09-18.xml*