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
| attribute | describe |
|---|---|
| nodes_seq | Demand node seq_no ordered permutation set, corresponding to the solution of TSP |
| obj | Optimization target value |
| routes | Vehicle path set, corresponding to the solution of CVRP |
- Node() class, representing a network node
| attribute | describe |
|---|---|
| id | Physical node id, optional |
| name | Physical node name, optional |
| seq_no | Physical node mapping id, base node is - 1, and demand node is numbered from 0 |
| x_coord | Physical node x coordinate |
| y_coord | Physical node y coordinate |
| demand | Physical node requirements |
- Model() class, storing algorithm parameters
| attribute | describe |
|---|---|
| best_sol | Global optimal solution, value type is Sol() |
| node_list | Physical node collection, with value type of Node() |
| sol_list | Feasible solution set, value type is Sol() |
| node_seq_no_list | Set of physical node mapping IDS |
| depot | Depot, value type is Node() |
| number_of_nodes | Number of demand nodes |
| opt_type | Optimization target type, 0: minimum number of vehicles, 1: minimum driving distance |
| distance | Distance matrix |
| popsize | Ant colony size |
| alpha | Information heuristic factor |
| beta | Expected heuristic factor |
| Q | Total pheromone |
| rho | Pheromone volatilization factor |
| tau | Network arc pheromone concentration |
(2) File reading
def readXlsxFile(filepath,model):
node_seq_no = -1
df = pd.read_excel(filepath)
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=work.add_worksheet()
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 = []
readXlsxFile(filepath,model)
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
- Wang Dingwei Intelligent optimization method [M] Higher education press, 2007
- https://blog.csdn.net/zuochao_2013/article/details/71872950