Python | 聚焦[MD]HVRP系列求解算法

2022年7月26日 517点热度 0人点赞 0条评论

Python |

聚焦[MD]HVRP系列求解算法

之禁忌搜索算法

摘要

禁忌搜索算法+Split求解异构车辆路径规划问题

致力于打造交通领域优质代码分享平台

今天继续为大家分享 [MD]HVRP系列求解算法源码。欢迎：点赞+收藏+关注。后续将推送更多优质内容，为避免错过一个亿，建议星标。

异构车辆路径问题(heterogeneous fixed fleet vehicle routing problem，HVRP)是VRP的一类重要变体问题，相比于原始的VRP，进一步考虑了车辆的某些特性，比如装载量，行驶里程等。也有些研究是针对顾客的某些特性而言。这里的异构是指车辆的装载量存在差异，由此带来运输费用的差异。为了能够在多约束条件下寻求更好的求解效果，本期文章将复现经典文献中的改进Split算法，实现使其能够处理多（单）车场条件下考虑车辆装载特性的车辆路径规划问题。

注意事项

求解HVRP或MDHVRP

多车辆类型

车辆容量不小于需求节点最大需求

（多）车辆基地

车场车辆总数满足实际需求

实现思路

Christian Prins^[2]给出的HVRP的Split方法过程如下：

以上算法在搜索过程中需求节点的备选标签规模会非常大，占用内存且降低搜索效率，因此采用了帕累托思想来遗传非支配解（19行~21行）。为了进一步控制备选标签数量，本期文章还附加实现了通过剩余容量与剩余需求来判断是否产生新的备选标签，提前避免产生不可行的标签。尽管如此，当考虑的异构车辆类型较多、需求点规模较大时，求解效率依然较低（代码结构、python特性、硬件环境）。所以本期文章进一步加入了最大标签数量参数来控制每个需求节点的备选标签规模，通过调节该参数实现速度与质量的相对均衡。

数据结构

继续以类的形式对算法参数、编码、解码、目标函数等进行封装。具体分为以下四类：

基本数据结构定义如下：

· Sol类：包含解的相关信息

属性	描述
obj	优化目标值
node_id_list	需求节点id有序排列集合
route_list	车辆路径集合
action_id	解所对应的算子id，用于禁用算子

·Demand类：包含需求节点的相关信息

属性	描述
id	物理节点id，需唯一。从0开始编号
x_coord	物理节点x坐标
y_coord	物理节点y坐标
demand	物理节点需求

·Vehicle类：包含车辆的相关信息

属性	描述
depot_id	所属车场id，不可与需求id重复
capacity	车辆装载率
type	车辆类型
fixed_cost	固定成本
variable_cost	单位里程变动成本
numbers	车辆数量

·Model类：包含全局参数

属性	描述
sol_list	种群集合，值类型为Sol()
best_sol	全局最优解，值类型为Sol()
demand_dict	需求节点集合（字典），值类型为Demand()
vehicle_dict	车辆集合，值类型为Vehicle()
vehicle_type_list	车辆类型集合
demand_id_list	需求id集合
distance_matrix	距离矩阵
number_of_demands	需求数量
TL	禁忌长度
tau_list	禁忌表
max_labels	最大备选标签数量

部分源码

参数读取

def readCSVFile(demand_file,depot_file,model):    with open(demand_file,'r') as f:        demand_reader=csv.DictReader(f)        for row in demand_reader:            demand = Demand()            demand.id = int(row['id'])            demand.x_coord = float(row['x_coord'])            demand.y_coord = float(row['y_coord'])            demand.demand = float(row['demand'])            model.demand_dict[demand.id] = demand            model.demand_id_list.append(demand.id)        model.number_of_demands=len(model.demand_id_list)
    with open(depot_file, 'r') as f:        depot_reader = csv.DictReader(f)        for row in depot_reader:            vehicle = Vehicle()            vehicle.depot_id = row['depot_id']            vehicle.x_coord = float(row['x_coord'])            vehicle.y_coord = float(row['y_coord'])            vehicle.type = row['vehicle_type']            vehicle.capacity=float(row['vehicle_capacity'])            vehicle.numbers=float(row['number_of_vehicle'])            vehicle.fixed_cost=float(row['fixed_cost'])            vehicle.variable_cost=float(row['variable_cost'])            model.vehicle_dict[vehicle.type] = vehicle            model.vehicle_type_list.append(vehicle.type)

距离矩阵计算

def calDistanceMatrix(model):    for i in range(len(model.demand_id_list)):        from_node_id = model.demand_id_list[i]        for j in range(i + 1, len(model.demand_id_list)):            to_node_id = model.demand_id_list[j]            dist = math.sqrt((model.demand_dict[from_node_id].x_coord - model.demand_dict[to_node_id].x_coord) ** 2                             + (model.demand_dict[from_node_id].y_coord - model.demand_dict[to_node_id].y_coord) ** 2)            model.distance_matrix[from_node_id, to_node_id] = int(dist)            model.distance_matrix[to_node_id, from_node_id] = int(dist)        for _, vehicle in model.vehicle_dict.items():            dist = math.sqrt((model.demand_dict[from_node_id].x_coord - vehicle.x_coord) ** 2                             + (model.demand_dict[from_node_id].y_coord - vehicle.y_coord) ** 2)            model.distance_matrix[from_node_id, vehicle.type] = int(dist)            model.distance_matrix[vehicle.type, from_node_id] = int(dist)

运输成本计算

def calTravelCost(route_list,model):    obj=0    for route in route_list:        vehicle=model.vehicle_dict[route[0]]        distance=0        fixed_cost=vehicle.fixed_cost        variable_cost=vehicle.variable_cost        for i in range(len(route) - 1):            from_node = route[i]            to_node = route[i + 1]            distance += model.distance_matrix[from_node, to_node]        obj += fixed_cost + distance * variable_cost    return obj

目标函数计算

def calObj(node_id_list,model):    vehicle_routes = splitRoutes(node_id_list, model)    if vehicle_routes:        return calTravelCost(vehicle_routes,model),vehicle_routes    else:        return 10**9,None

初始解

def generateInitialSol(node_id_list):    node_id_list_=copy.deepcopy(node_id_list)    random.seed(0)    random.shuffle(node_id_list_)    return node_id_list_

邻域算子

def createActions(n):    action_list=[]    nswap=n//2    # 第一种算子（Swap）：前半段与后半段对应位置一对一交换    for i in range(nswap):        action_list.append([1,i,i+nswap])    # 第二中算子（DSwap）：前半段与后半段对应位置二对二交换    for i in range(0,nswap,2):        action_list.append([2,i,i+nswap])    # 第三种算子（Reverse）：指定长度的序列反序    for i in range(0,n,4):        action_list.append([3,i,i+3])    return action_list

提取路径

def extractRoutes(V,node_id_list,model):    route_list = []    min_obj=float('inf')    pred_label_id=None    v_type=None    # search the min cost label of last node of the node_id_list    for label in V[model.number_of_demands-1]:        if label[3]<=min_obj:            min_obj=label[3]            pred_label_id=label[1]            v_type=label[2]    # generate routes by pred_label_id    route=[node_id_list[-1]]    indexs=list(range(0,model.number_of_demands))[::-1]    start=1    while pred_label_id!=1:        for i in indexs[start:]:            stop=False            for label in V[i]:                if label[0]==pred_label_id:                    stop=True                    pred_label_id=label[1]                    start=i                    v_type_=label[2]                    break            if not stop:                route.insert(0,node_id_list[i])            else:                route.insert(0,v_type)                route.append(v_type)                route_list.append(route)                route=[node_id_list[i]]                v_type=v_type_    route.insert(0,v_type)    route.append(v_type)    route_list.append(route)    return route_list

代码结构

结果展示

这里采用solomon开源数据对算法进行测试，数据文件结构如下图所示，共100个需求点，3个车场，3类车辆，以.csv文件储存数据。

demand.csv文件内容如下图，其中第一行为标题栏，节点id从0开始递增编号。

depot.csv文件内容如下图，其中第一行为标题栏，依次为：车场id，车场平面x坐标，车场平面y坐标，车辆类型，车辆装载量，车辆数量，固定成本，单位里程运输成本。

求解结果如下：

算法收敛图

优化路线图

源码获取

①分享至朋友圈1小时以上

②凭分享截图后台回复 'TS_HVRP' 获取下载链接（链接有效期为30天）

参考

[1].汪定伟. 智能优化方法[M]. 高等教育出版社, 2007.

[2]Prins C , Lacomme P , Prodhon C . Order-first split-second methods for vehicle routing problems: A review[J]. Transportation Research Part C, 2014, 40(mar.):179-200.

扫码关注我们

欢迎点赞+收藏+关注