使用 NSGA2 算法解决车辆路径问题 (VRP) 模型 - Python 代码示例

使用 NSGA2 算法解决车辆路径问题 (VRP) 模型 - Python 代码示例

本文使用 NSGA2 算法解决一个车辆路径问题 (VRP) 模型，并使用 Python 代码示例。该模型随机生成仓库和客户坐标、客户配送需求以及客户预期配送到达时间，并以最小化总成本和最大化客户满意度为目标函数。本文展示了 Python 代码实现，并使用 geatpy 库进行优化，最终输出使用车辆数目并可视化帕累托前沿和车辆配送路径。

模型定义

该 VRP 模型定义如下：

• 随机生成仓库和一百个客户坐标及客户配送需求： 横纵坐标在 0 到 50 以内，需求在 2-10 之间。
• 有足够的同质车辆： 车辆容量约束为 100，车辆行驶速度为 40。
• 随机生成每个客户的预期配送到达时间： 时间范围在 0 到 8 之间。
• 车辆到达一个客户的实际到达时间： 等于到达上一个客户的实际到达时间加上服务上一个客户的时间加上两个节点的实际行驶时间。
• 服务一个客户的时间： 与配送量成正比。
• 目标函数有两个：
  • 总成本最小： 成本包括所有使用车辆的固定成本和路径行驶成本，每辆车固定成本为 500，路径行驶成本与行驶距离成正比，比例系数是 0.05。
  • 客户满意度总和最大： 客户满意度是客户期望配送到达时间减去实际到达时间，如果大于零则再乘以 0.8，如果小于零则再乘以 1.3。
• 每个车辆必须在时刻为 8 之前返回仓库： 车辆从仓库出发时刻为 0。
• 输出使用车辆数目，并且可视化帕累托前沿和车辆配送路径。

代码实现

以下是一部分 Python 代码实现，使用 geatpy 库进行优化：

# 定义VRP问题的适应度函数
def aimFunc(self, pop):
    for i in range(self.pop_size):
        # 获得个体的染色体信息
        chromosome = pop.Chrom[i, :]
        # 将染色体信息转化为可行解
        customer, vehicle = decode(chromosome)
        # 计算总成本和客户满意度总和
        total_cost, total_satisfaction = vrp_cost(customer, vehicle)
        # 将目标函数值赋值给个体的适应度值
        pop.ObjV[i, :] = [total_cost, -total_satisfaction]

# 定义VRP问题的解码函数
def decode(chromosome):
    # 将染色体信息按照客户数目和车辆数目划分
    customer_num = len(chromosome) - 1
    vehicle_num = np.sum(chromosome == 0) - 1
    # 获得仓库和客户的坐标和需求
    coordinate = np.random.randint(0, 50, size=(customer_num + 1, 2))
    demand = np.random.randint(2, 11, size=customer_num)
    # 获得每个客户的预期配送到达时间
    delivery_time = np.random.randint(0, 9, size=customer_num)
    # 将客户和车辆信息存储为列表
    customer = [{'id': i, 'coordinate': coordinate[i], 'demand': demand[i],
                 'delivery_time': delivery_time[i]} for i in range(1, customer_num+1)]
    vehicle = [{'id': i, 'capacity': 100, 'current_load': 0, 'current_time': 0,
                'route': [0]} for i in range(1, vehicle_num+1)]
    # 将染色体信息转化为可行解
    for i in range(customer_num):
        if chromosome[i] == 0:
            continue
        else:
            vehicle_id = np.sum(chromosome[:i+1] == chromosome[i]) - 1
            vehicle[vehicle_id]['route'].append(customer[i]['id'])
            vehicle[vehicle_id]['current_load'] += customer[i]['demand']
            vehicle[vehicle_id]['current_time'] = max(vehicle[vehicle_id]['current_time'], customer[i]['delivery_time'])
            vehicle[vehicle_id]['current_time'] += distance(customer[i]['coordinate'], customer[i+1]['coordinate']) / 40
    # 将每个车辆的路径和返回仓库的路径连接起来
    for i in range(vehicle_num):
        vehicle[i]['route'].append(0)
    return customer, vehicle

# 定义VRP问题的成本计算函数
def vrp_cost(customer, vehicle):
    fixed_cost = 500 * len(vehicle) # 计算固定成本
    distance_cost = 0 # 计算路径行驶成本
    satisfaction = 0 # 计算客户满意度
    for v in vehicle:
        # 判断该车辆是否能在规定时间内返回仓库
        if v['current_time'] + distance(customer[v['route'][-2]]['coordinate'], customer[0]['coordinate']) / 40 > 8:
            return float('inf'), float('-inf')
        # 计算路径行驶成本
        for i in range(len(v['route']) - 1):
            distance_cost += distance(customer[v['route'][i]]['coordinate'], customer[v['route'][i+1]]['coordinate'])
        distance_cost *= 0.05
        # 计算客户满意度
        for i in range(len(v['route']) - 1):
            satisfaction += (customer[v['route'][i+1]]['delivery_time'] - v['current_time']) * customer[v['route'][i+1]]['demand']
            if customer[v['route'][i+1]]['delivery_time'] >= v['current_time']:
                satisfaction -= (customer[v['route'][i+1]]['delivery_time'] - v['current_time']) * customer[v['route'][i+1]]['demand'] * 0.8
            else:
                satisfaction -= (v['current_time'] - customer[v['route'][i+1]]['delivery_time']) * customer[v['route'][i+1]]['demand'] * 1.3
            v['current_time'] += distance(customer[v['route'][i]]['coordinate'], customer[v['route'][i+1]]['coordinate']) / 40
    return fixed_cost + distance_cost, satisfaction

# 定义求两点距离的函数
def distance(a, b):
    return np.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)

完整代码和可视化结果请见我的 GitHub 仓库。

总结

本文使用 NSGA2 算法解决了一个 VRP 模型，并使用 Python 代码示例进行了实现。该模型随机生成仓库和客户坐标、客户配送需求以及客户预期配送到达时间，并以最小化总成本和最大化客户满意度为目标函数。最终输出使用车辆数目并可视化帕累托前沿和车辆配送路径。