Python实现VRP常见求解算法——⾃适应⼤邻域搜索算法（ALNS）基于python语⾔，实现经典⾃适应⼤邻域搜索算法（ALNS）对车辆路径规划问题（CVRP）进⾏求解。
⽬录
1. 适⽤场景
求解CVRP
车辆类型单⼀
车辆容量不⼩于需求节点最⼤需求
单⼀车辆基地
2. 问题分析
CVRP问题的解为⼀组满⾜需求节点需求的多个车辆的路径集合。假设某物理⽹络中共有10个顾客节点，编号为1~10，⼀个车辆基地，编号为0，在满⾜车辆容量约束与顾客节点需求约束的条件下，此问题的⼀个可⾏解可表⽰为：[0-1-2-0,0-3-4-5-0,0-6-7-8-0,0-9-10-0]，即需要4个车辆来提供服务，车辆的
⾏驶路线分别为0-1-2-0,0-3-4-5-0,0-6-7-8-0,0-9-10-0。由于车辆的容量固定，基地固定，因此可以将上述问题的解先表⽰为[1-2-3-4-5-6-7-8-9-10]的有序序列，然后根据车辆的容量约束，对序列进⾏切割得到若⼲车辆的⾏驶路线。因此可以将CVRP问题转换为TSP问题进⾏求解，得到TSP问题的优化解后再考虑车辆容量约束进⾏路径切割，得到CVRP问题的解。这样的处理⽅式可能会影响CVRP问题解的质量，但简化了问题的求解难度。
3. 数据格式
以xlsx⽂件储存⽹络数据，其中第⼀⾏为标题栏，第⼆⾏存放车辆基地数据。在程序中车辆基地seq_no编号为-1，需求节点seq_id从0开始编号。可参考github主页相关⽂件。
4. 分步实现
（1）数据结构
为便于数据处理，定义Sol()类，Node()类，Model()类，其属性如下表：
Sol()类，表⽰⼀个可⾏解
属性描述
nodes_seq需求节点seq_no有序排列集合，对应TSP的解
obj优化⽬标值
routes车辆路径集合，对应CVRP的解
Node()类，表⽰⼀个⽹络节点
属性描述
id物理节点id，可选
name物理节点名称，可选
seq_no物理节点映射id，基地节点为-1，需求节点从0编号
x_coord物理节点x坐标
y_coord物理节点y坐标
demand物理节点需求
demand物理节点需求
属性描述
Model()类，存储算法参数
属性描述
best_sol全局最优解，值类型为Sol()
node_list物理节点集合，值类型为Node() node_seq_no_list物理节点映射id集合
depot车辆基地，值类型为Node() number_of_nodes需求节点数量
opt_type优化⽬标类型，0：最⼩车辆数，1：最⼩⾏驶距离
vehicle_cap车辆容量
distance⽹络弧距离
rand_d_max随机破坏程度上限
rand_d_min随机破坏程度下限
worst_d_max最坏破坏程度上限
worst_d_min最坏破坏程度下限
regret_n次优位置个数
r1算⼦奖励1
r2算⼦奖励2
r3算⼦奖励3
rho算⼦权重衰减系数
d_weight破坏算⼦权重
d_select破坏算⼦被选中次数/每轮
d_score破坏算⼦被奖励得分/每轮d_history_select破坏算⼦历史共计被选中次数
d_history_score破坏算⼦历史共计被奖励得分r_weight修复算⼦权重
r_select修复算⼦被选中次数/每轮
r_score修复算⼦被奖励得分/每轮r_history_select修复算⼦历史共计被选中次数
r_history_score修复算⼦历史共计被奖励得分
（2）⽂件读取
def readXlsxFile(filepath,model):
# It is recommended that the vehicle depot data be placed in the first line of xlsx file
node_seq_no =-1#the depot node seq_no is -1,and demand node seq_no is 0,1,2,...
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]
random pythonif df['demand'][i]==0:
model.depot=node
else:
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=de_list)
（3）初始化参数
在初始化参数时计算⽹络弧距离，以便后续算⼦使⽤。
def initParam(model):
for i in range(model.number_of_nodes):
for j in range(i+1,model.number_of_nodes):
d=math.sqrt((de_list[i].de_list[j].x_coord)**2+
(de_list[i].de_list[j].y_coord)**2)
model.distance[i,j]=d
model.distance[j,i]=d
（4）初始解
def genInitialSol(node_seq):
node_seq=copy.deepcopy(node_seq)
random.seed(0)
random.shuffle(node_seq)
return node_seq
（5）⽬标值计算
⽬标值计算依赖 " splitRoutes " 函数对TSP可⾏解分割得到车辆⾏驶路线和所需车辆数， " calDistance " 函数计算⾏驶距离。
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 - de_list[node_no].demand >=0:
route.append(node_no)
remained_cap = remained_cap - de_list[node_no].demand
else:
vehicle_routes.append(route)
route =[node_no]
num_vehicle = num_vehicle +1
remained_cap =model.vehicle_cap - de_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):
distance+=model.distance[route[i],route[i+1]]
first_de_list[route[0]]
last_de_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
（6）定义destroy算⼦（破坏算⼦）
这⾥实现两种destory：
random destroy : 随机从当前解中移除⼀定⽐例的需求节点
worst destroy：从当前解中移除⼀定⽐例引起⽬标函数增幅较⼤的需求节点
# define random destory action
def createRandomDestory(model):
d=random.uniform(model.rand_d_min,model.rand_d_max)
reomve_list=random.sample(range(model.number_of_nodes),int(d*model.number_of_nodes)) return reomve_list
# define worse destory action
def createWorseDestory(model,sol):
deta_f=[]
for node_no des_seq:
nodes_seq_=copy.des_seq)
nodes_seq_.remove(node_no)
obj,vehicle_routes=calObj(nodes_seq_,model)
deta_f.append(sol.obj-obj)
sorted_id =sorted(range(len(deta_f)), key=lambda k: deta_f[k], reverse=True)
d=random.randint(model.worst_d_min,model.worst_d_max)
remove_list=sorted_id[:d]
return remove_list
（7）定义repair算⼦（修复算⼦）
这⾥实现三种repair：
random repair ：将被移除的需求节点随机插⼊已分配节点序列中；
greedy repair ：根据被移除的需求节点插⼊已分配节点序列中每个可能位置的⽬标函数增量⼤⼩，依次选择⽬标函数增量最⼩的需求节点与插⼊位置组合，直到所有被移除的需求节点都重新插⼊为⽌（可简单理解为，依次选择使⽬标函数增量最⼩的需求节点与其最优的插⼊位置）；
其中，为未分配的需求节点集合，为可能插⼊的位置集合，为将需求节点插⼊中第个位置时的⽬标函数值。
regret repair：计算被移除节点插回到已分配节点序列中n个次优位置时其⽬标函数值与最优位置的⽬
标函数值的差之和，然后选择差之和最⼤的需求节点及其最优位置。（可简单理解为，优先选择n个次优位置与最优位置距离较远的需求节点及其最优位置。）；
其中，为未分配的需求节点集合，为将需求节点插⼊中最优位置和第次优位置时⽬标函数差值。
def createRandomRepair (remove_list ,model ,sol ): unassigned_nodes_seq =[] assigned_nodes_seq = []
# remove node from current solution for i in range (model .number_of_nodes ): if i in remove_list :
unassigned_nodes_seq .append (sol .nodes_seq [i ]) else :
assigned_nodes_seq .append (sol .nodes_seq [i ]) # insert
for node_no in unassigned_nodes_seq :
index =random .randint (0,len (assigned_nodes_seq )-1) assigned_nodes_seq .insert (index ,node_no ) new_sol =Sol ()
new_sol .nodes_seq =copy .deepcopy (assigned_nodes_seq ) new_sol .obj ,new_sol .routes =calObj (assigned_nodes_seq ,model ) return new_sol
def createGreedyRepair (remove_list ,model ,sol ): unassigned_nodes_seq = [] assigned_nodes_seq = []
# remove node from current solution for i in range (model .number_of_nodes ): if i in remove_list :
unassigned_nodes_seq .append (sol .nodes_seq [i ]) else :
assigned_nodes_seq .append (sol .nodes_seq [i ]) #insert
while len (unassigned_nodes_seq )>0:
insert_node_no ,insert_index =findGreedyInsert (unassigned_nodes_seq ,assigned_nodes_seq ,model ) assigned_nodes_seq .insert (insert_index ,insert_node_no ) unassigned_nodes_seq .remove (insert_node_no ) new_sol =Sol ()
new_sol .nodes_seq =copy .deepcopy (assigned_nodes_seq ) new_sol .obj ,new_sol .routes =calObj (assigned_nodes_seq ,model ) return new_sol
def findGreedyInsert (unassigned_nodes_seq ,assigned_nodes_seq ,model ): best_insert_node_no =None best_insert_index = None best_insert_cost = float ('inf')
assigned_nodes_seq_obj ,_=calObj (assigned_nodes_seq ,model ) for node_no in unassigned_nodes_seq : for i in range (len (assigned_nodes_seq )):
assigned_nodes_seq_ = copy .deepcopy (assigned_nodes_seq )
argmin f (s )
p ∈P ,i ∈IP p ,i P IP f (s )p ,i p s i argmax (f (s (p ))
−f (s (p )))p ∈P {∑i =2n
i 1}
P f (s (p ))−i f (s (p ))1p s i
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论