Ant colony algorithm (ACO), a common algorithm for VRP implementation in Python

Based on python language, the classical ant colony algorithm is implemented to solve the vehicle path planning problem (CVRP).

1. Applicable scenarios

• Solve CVRP
• Single vehicle type
• The vehicle capacity shall not be less than the maximum demand of the demand node
• Single vehicle base

2. Problem analysis

The solution of CVRP problem is a set of path sets of multiple vehicles that meet the needs of demand nodes. Assuming that a physical network has 10 customer nodes numbered 1-10 and a vehicle base numbered 0, a feasible solution to this problem can be expressed as: [0-1-2-0,0-3-4-5-0,0-6-7-8-0,0-9-10-0], that is, four vehicles are required to provide services, and the driving routes of vehicles are 0-1-2-0,0-3-4-5-0,0-6-7-8-0,0-9-10-0 respectively. Since the capacity of vehicles is fixed and the base is fixed, the solution of the above problem can be expressed as an ordered sequence of [1-2-3-4-5-6-7-8-9-10], and then the sequence is cut according to the capacity constraint of vehicles to obtain the driving routes of several vehicles. Therefore, the CVRP problem can be transformed into a TSP problem for solution. After obtaining the optimal solution of the TSP problem, consider the vehicle capacity constraints for path cutting to obtain the solution of the CVRP problem. Such treatment may affect the quality of the solution of CVRP problem, but it simplifies the difficulty of solving the problem.

3. Data format

The network data is stored in xlsx file, in which the first line is the title bar and the second line is the vehicle base data. In the program, vehicle base seq_no number is - 1, demand node seq_id is numbered from 0. Refer to relevant documents on github homepage.

4. Step by step implementation

(1) Data structure
To facilitate data processing, Sol() class, Node() class and Model() class are defined. Their properties are shown in the following table:

• Sol() class, representing a feasible solution
attributedescribe
nodes_seqDemand node seq_no ordered permutation set, corresponding to the solution of TSP
objOptimization target value
routesVehicle path set, corresponding to the solution of CVRP
• Node() class, representing a network node
attributedescribe
idPhysical node id, optional
namePhysical node name, optional
seq_noPhysical node mapping id, base node is - 1, and demand node is numbered from 0
x_coordPhysical node x coordinate
y_coordPhysical node y coordinate
demandPhysical node requirements
• Model() class, storing algorithm parameters
attributedescribe
best_solGlobal optimal solution, value type is Sol()
node_listPhysical node collection, with value type of Node()
sol_listFeasible solution set, value type is Sol()
node_seq_no_listSet of physical node mapping IDS
depotDepot, value type is Node()
number_of_nodesNumber of demand nodes
opt_typeOptimization target type, 0: minimum number of vehicles, 1: minimum driving distance
distanceDistance matrix
popsizeAnt colony size
alphaInformation heuristic factor
betaExpected heuristic factor
QTotal pheromone
rhoPheromone volatilization factor
tauNetwork arc pheromone concentration

```def readXlsxFile(filepath,model):
node_seq_no = -1
for i in range(df.shape[0]):
node=Node()
node.id=node_seq_no
node.seq_no=node_seq_no
node.x_coord= df['x_coord'][i]
node.y_coord= df['y_coord'][i]
node.demand=df['demand'][i]
if df['demand'][i] == 0:
model.depot=node
else:
model.node_list.append(node)
model.node_seq_no_list.append(node_seq_no)
try:
node.name=df['name'][i]
except:
pass
try:
node.id=df['id'][i]
except:
pass
node_seq_no=node_seq_no+1
model.number_of_nodes=len(model.node_list)
```

(3) Initialization parameters
Initialize the distance matrix and pheromone matrix, and assign the initial pheromone concentration to 10 (other values can also be used).

```def initParam(model):
for i in range(model.number_of_nodes):
for j in range(i+1,model.number_of_nodes):
d=math.sqrt((model.node_list[i].x_coord-model.node_list[j].x_coord)**2+
(model.node_list[i].y_coord-model.node_list[j].y_coord)**2)
model.distance[i,j]=d
model.distance[j,i]=d
model.tau[i,j]=10
model.tau[j,i]=10
```

(4) Ant search
The ant search process relies on the "searchNextNode" function to calculate the next access node according to the network arc information concentration.

```def movePosition(model):
sol_list=[]
local_sol=Sol()
local_sol.obj=float('inf')
for k in range(model.popsize):
#Random ant position
nodes_seq=[int(random.randint(0,model.number_of_nodes-1))]
all_nodes_seq=copy.deepcopy(model.node_seq_no_list)
all_nodes_seq.remove(nodes_seq[-1])
#Determine the next moving position according to pheromone
while len(all_nodes_seq)>0:
next_node_no=searchNextNode(model,nodes_seq[-1],all_nodes_seq)
nodes_seq.append(next_node_no)
all_nodes_seq.remove(next_node_no)
sol=Sol()
sol.nodes_seq=nodes_seq
sol.obj,sol.routes=calObj(nodes_seq,model)
sol_list.append(sol)
if sol.obj<local_sol.obj:
local_sol=copy.deepcopy(sol)
model.sol_list=copy.deepcopy(sol_list)
if local_sol.obj<model.best_sol.obj:
model.best_sol=copy.deepcopy(local_sol)

def searchNextNode(model,current_node_no,SE_List):
prob=np.zeros(len(SE_List))
for i,node_no in enumerate(SE_List):
eta=1/model.distance[current_node_no,node_no]
tau=model.tau[current_node_no,node_no]
prob[i]=((eta**model.alpha)*(tau**model.beta))
#use Roulette to determine the next node
cumsumprob=(prob/sum(prob)).cumsum()
cumsumprob -= np.random.rand()
next_node_no= SE_List[list(cumsumprob > 0).index(True)]
return next_node_no
```

(5) Update pheromone
The pheromone, Q/obj, left by ants on the path is calculated by ant week model. In the specific calculation, two methods are written here. One is based on the nodes of the feasible solution_ The SEQ attribute value, that is, the solution of the TSP problem, updates the pheromone of the path. The other is to update the pheromone of the path according to the routes attribute value of the feasible solution, that is, the solution of the CVRP problem.

```def upateTau(model):
rho=model.rho
for k in model.tau.keys():
model.tau[k]=(1-rho)*model.tau[k]
#update tau according to sol.nodes_seq(solution of TSP)
# for sol in model.sol_list:
#     nodes_seq=sol.nodes_seq
#     for i in range(len(nodes_seq)-1):
#         from_node_no=nodes_seq[i]
#         to_node_no=nodes_seq[i+1]
#         model.tau[from_node_no,to_node_no]+=model.Q/sol.obj

#update tau according to sol.routes(solution of CVRP)
for sol in model.sol_list:
routes=sol.routes
for route in routes:
for i in range(len(route)-1):
from_node_no=route[i]
to_node_no=route[i+1]
model.tau[from_node_no,to_node_no]+=model.Q/sol.obj
```

(6) Calculate the objective function
The target value calculation depends on the "splitRoutes" function to segment the TSP feasible solution to obtain the vehicle driving route and the required number of vehicles, and the "calDistance" function calculates the driving distance.

```def splitRoutes(nodes_seq,model):
num_vehicle = 0
vehicle_routes = []
route = []
remained_cap = model.vehicle_cap
for node_no in nodes_seq:
if remained_cap - model.node_list[node_no].demand >= 0:
route.append(node_no)
remained_cap = remained_cap - model.node_list[node_no].demand
else:
vehicle_routes.append(route)
route = [node_no]
num_vehicle = num_vehicle + 1
remained_cap =model.vehicle_cap - model.node_list[node_no].demand
vehicle_routes.append(route)
return num_vehicle,vehicle_routes
def calDistance(route,model):
distance=0
depot=model.depot
for i in range(len(route)-1):
from_node=model.node_list[route[i]]
to_node=model.node_list[route[i+1]]
distance+=math.sqrt((from_node.x_coord-to_node.x_coord)**2+(from_node.y_coord-to_node.y_coord)**2)
first_node=model.node_list[route[0]]
last_node=model.node_list[route[-1]]
distance+=math.sqrt((depot.x_coord-first_node.x_coord)**2+(depot.y_coord-first_node.y_coord)**2)
distance+=math.sqrt((depot.x_coord-last_node.x_coord)**2+(depot.y_coord - last_node.y_coord)**2)
return distance
def calObj(nodes_seq,model):
num_vehicle, vehicle_routes = splitRoutes(nodes_seq, model)
if model.opt_type==0:
return num_vehicle,vehicle_routes
else:
distance=0
for route in vehicle_routes:
distance+=calDistance(route,model)
return distance,vehicle_routes
```

(7) Draw convergence curve

```def plotObj(obj_list):
plt.rcParams['font.sans-serif'] = ['SimHei']  #show chinese
plt.rcParams['axes.unicode_minus'] = False   # Show minus sign
plt.plot(np.arange(1,len(obj_list)+1),obj_list)
plt.xlabel('Iterations')
plt.ylabel('Obj Value')
plt.grid()
plt.xlim(1,len(obj_list)+1)
plt.show()
```

(8) Output results

```def outPut(model):
work=xlsxwriter.Workbook('result.xlsx')
worksheet.write(0,0,'opt_type')
worksheet.write(1,0,'obj')
if model.opt_type==0:
worksheet.write(0,1,'number of vehicles')
else:
worksheet.write(0, 1, 'drive distance of vehicles')
worksheet.write(1,1,model.best_sol.obj)
for row,route in enumerate(model.best_sol.routes):
worksheet.write(row+2,0,'v'+str(row+1))
r=[str(i)for i in route]
worksheet.write(row+2,1, '-'.join(r))
work.close()
```

(9) Main function

```def run(filepath,Q,alpha,beta,rho,epochs,v_cap,opt_type,popsize):
"""
:param filepath:Xlsx file path
:param Q:Total pheromone
:param alpha:Information heuristic factor
:param beta:Expected heuristic factor
:param rho:Information volatilization factor
:param epochs:Iterations
:param v_cap:Vehicle capacity
:param opt_type:Optimization type:0:Minimize the number of vehicles,1:Minimize travel distance
:param popsize:Population size
:return:
"""
model=Model()
model.vehicle_cap=v_cap
model.opt_type=opt_type
model.alpha=alpha
model.beta=beta
model.Q=Q
model.rho=rho
model.popsize=popsize
sol=Sol()
sol.obj=float('inf')
model.best_sol=sol
history_best_obj = []
initParam(model)
for ep in range(epochs):
movePosition(model)
upateTau(model)
history_best_obj.append(model.best_sol.obj)
print("%s/%s， best obj: %s" % (ep,epochs, model.best_sol.obj))
plotObj(history_best_obj)
outPut(model)
```

5. Complete code

The code and data files are available from the github home page:

https://github.com/PariseC/Algorithms_for_solving_VRP

reference resources

1. Wang Dingwei Intelligent optimization method [M] Higher education press, 2007
2. https://blog.csdn.net/zuochao_2013/article/details/71872950

Tags: Python Algorithm

Posted by digitus78 on Tue, 19 Apr 2022 02:34:54 +0930