发布时间：2023-04-03 文章分类：电脑基础投稿人：樱花字号：默认 | 大 | 超大打印

文章目录

一、概述
- 1.1 VRP 问题
- 1.2 CVRP 问题
- 1.3 VRPTW 问题
二、VRPTW 的一般模型
三、Python 调用 Gurobi 建模求解
- 3.1 Solomn 数据集
- 3.2 完整代码
- 3.3 运行结果展示
- - 3.3.1 测试案例：c101.txt
  - 3.3.2 测试案例：r101.txt

一、概述

1.1 VRP 问题

车辆路径规划问题(Vehicle Routing Problem，VRP)一般指的是：对一系列发货点和收货点，组织调用一定的车辆，安排适当的行车路线，使车辆有序地通过它们，在满足指定的约束条件下（例如：货物的需求量与发货量，交发货时间，车辆容量限制，行驶里程限制，行驶时间限制等），力争实现一定的目标（如车辆空驶总里程最短，运输总费用最低，车辆按一定时间到达，使用的车辆数最小等）。

下图给出了一个简单的VRP的例子

1.2 CVRP 问题

最基本的VRP问题叫做带容量约束的车辆路径规划问题（Capacitated Vehicle Routing Problem，CVRP）。在CVRP中，需要考虑每辆车的容量约束、车辆的路径约束和装载量约束

1.3 VRPTW 问题

为了考虑配送时间要求，带时间窗的车辆路径规划问题（Vehicle Routing Problem with Time Window，VRPTW）应运而生。

VRPTW 不仅考虑CVRP的所有约束，还需要考虑时间窗约束，也就是每个顾客对应一个时间窗 $e_i,l_i]$ ，其中 $e_i$ 和 $l_i$ 分别代表该点的最早到达时间和最晚到达时间。顾客点 $\in V$ 的需求必须要在其时间窗内被送达

VRPTW 已经被证明是 NP-hard 问题，其求解复杂度随着问题规模的增加而急剧增加，求解较为困难。到目前为止，求解 VRPTW 的比较高效的精确算法是分支定价算法和分支定价切割算法。

二、VRPTW 的一般模型

VRPTW 可以建模为一个混合整数规划问题，在给出完整数学模型之前，先引入下面的决策变量：

${x_i}_j=\begin{cases} 1\text{，如果在最优解中，弧}\left( i,j \right) \text{被车辆}k\text{选中}\\ 0\text{，其他}\\ \end{cases} \\ {s_i}_k=\text{车辆}k\text{到达}i\text{的时间} \\ \text{模型中涉及的其他参数为}: \\ {t_i}_j\text{表示车辆在弧}\left( i,j \right) \text{上的行驶时间} \\ M\text{为一个足够大的正数}$

关于M的取值，实际上可以直接取非常大的正数，但是为了提高求解效率，拉紧约束。我们可以采用下面的取值方法：

$M=max\{b_i+t_{ij}-a_j\} , \forall (i,j)\in A$

综合上面引出的决策变量，并参考文献（Desaulniers et al.，2006），给出的 VRPTW 的标准模型如下：

$\min \sum_{k\in K}{\sum_{i\in V}{\sum_{i\in V}{{c_i}_j{x_i}_{j_k}}}} \\ s.t. \sum_{k\in K}{\sum_{j\in V}{{x_i}_{j_k}=1 , \forall i\in C}} \\ \,\, \sum_{j\in V}{{x_0}_{j_k}=1 , \forall k\in K} \\ \,\, \sum_{i\in V}{{x_i}_{h_k}-\sum_{j\in V}{{x_h}_{j_k}=0 , \forall h\in C,\forall k\in K}} \\ \,\, \sum_{i\in V}{x_{i,n+1,k}=1 , \forall k\in K} \\ \,\, \sum_{i\in C}{q_i\sum_{j\in V}{{x_i}_{j_k}=1 , \forall k\in K}} \\ \,\, {s_i}_k+{t_i}_j-M\left( 1-{x_i}_{j_k} \right) \leqslant {s_j}_k\,\,, \forall \left( i,j \right) \in A,\forall k\in K \\ \,\, e_i\leqslant {s_i}_k\leqslant l_i\,\,, \forall i\in V,\forall k\in K \\ \,\, {x_i}_{j_k}\in \left\{ 0,1 \right\} \,\,, \forall \left( i,j \right) \in A,\forall k\in K$

其中：

目标函数是为了最小化所有车辆的总行驶成本（距离）
约束1~4保证了每辆车必须从仓库出发，经过一个点就离开那个点，最终返回仓库
约束5为车辆的容量约束
约束6~7是时间窗约束，保证了车辆到达每个顾客点的时间均在时间窗内，点n+1是点o的一个备份，是为了方便实现。

三、Python 调用 Gurobi 建模求解

3.1 Solomn 数据集

Solomn 数据集下载地址

3.2 完整代码

注意，在下面代码中，将弧 $i$ 到弧 $j$ 所需的时间 $t_{ij}$ 和成本 $c_{ij}$ 都当作了弧 $i$ 到弧 $j$ 所需的距离来看待

# -*- coding: utf-8 -*-#
# Author: WSKH
# Blog: wskh0929.blog.csdn.net
# Time: 2023/2/8 11:14
# Description: Python 调用 Gurobi 建模求解 VRPTW 问题
import time
import matplotlib.pyplot as plt
import numpy as np
from gurobipy import *
class Data:
    customerNum = 0
    nodeNum = 0
    vehicleNum = 0
    capacity = 0
    corX = []
    corY = []
    demand = []
    serviceTime = []
    readyTime = []
    dueTime = []
    distanceMatrix = [[]]
def readData(path, customerNum):
    data = Data()
    data.customerNum = customerNum
    if customerNum is not None:
        data.nodeNum = customerNum + 2
    with open(path, 'r') as f:
        lines = f.readlines()
        count = 0
        for line in lines:
            count += 1
            if count == 5:
                line = line[:-1]
                s = re.split(r" +", line)
                data.vehicleNum = int(s[1])
                data.capacity = float(s[2])
            elif count >= 10 and (customerNum is None or count <= 10 + customerNum):
                line = line[:-1]
                s = re.split(r" +", line)
                data.corX.append(float(s[2]))
                data.corY.append(float(s[3]))
                data.demand.append(float(s[4]))
                data.readyTime.append(float(s[5]))
                data.dueTime.append(float(s[6]))
                data.serviceTime.append(float(s[7]))
    data.nodeNum = len(data.corX) + 1
    data.customerNum = data.nodeNum - 2
    # 回路
    data.corX.append(data.corX[0])
    data.corY.append(data.corY[0])
    data.demand.append(data.demand[0])
    data.readyTime.append(data.readyTime[0])
    data.dueTime.append(data.dueTime[0])
    data.serviceTime.append(data.serviceTime[0])
    # 计算距离矩阵
    data.distanceMatrix = np.zeros((data.nodeNum, data.nodeNum))
    for i in range(data.nodeNum):
        for j in range(i + 1, data.nodeNum):
            distance = math.sqrt((data.corX[i] - data.corX[j]) ** 2 + (data.corY[i] - data.corY[j]) ** 2)
            data.distanceMatrix[i][j] = data.distanceMatrix[j][i] = distance
    return data
class Solution:
    ObjVal = 0
    X = [[]]
    S = [[]]
    routes = [[]]
    routeNum = 0
    def __init__(self, data, model):
        self.ObjVal = model.ObjVal
        # X_ijk
        self.X = [[([0] * data.vehicleNum) for _ in range(data.nodeNum)] for _ in range(data.nodeNum)]
        # S_ik
        self.S = [([0] * data.vehicleNum) for _ in range(data.nodeNum)]
        # routes
        self.routes = []
def getSolution(data, model):
    solution = Solution(data, model)
    for m in model.getVars():
        split_arr = re.split(r"_", m.VarName)
        if split_arr[0] == 'X' and m.x > 0.5:
            solution.X[int(split_arr[1])][int(split_arr[2])][int(split_arr[3])] = m.x
        elif split_arr[0] == 'S' and m.x > 0.5:
            solution.S[int(split_arr[1])][int(split_arr[2])] = m.x
    for k in range(data.vehicleNum):
        i = 0
        subRoute = []
        subRoute.append(i)
        finish = False
        while not finish:
            for j in range(data.nodeNum):
                if solution.X[i][j][k] > 0.5:
                    subRoute.append(j)
                    i = j
                    if j == data.nodeNum - 1:
                        finish = True
        if len(subRoute) >= 3:
            subRoute[-1] = 0
            solution.routes.append(subRoute)
            solution.routeNum += 1
    return solution
def plot_solution(solution, customer_num):
    plt.xlabel("x")
    plt.ylabel("y")
    plt.title(f"{data_type} : {customer_num} Customers")
    plt.scatter(data.corX[0], data.corY[0], c='blue', alpha=1, marker=',', linewidths=3, label='depot')  # 起点
    plt.scatter(data.corX[1:-1], data.corY[1:-1], c='black', alpha=1, marker='o', linewidths=3,
                label='customer')  # 普通站点
    for k in range(solution.routeNum):
        for i in range(len(solution.routes[k]) - 1):
            a = solution.routes[k][i]
            b = solution.routes[k][i + 1]
            x = [data.corX[a], data.corX[b]]
            y = [data.corY[a], data.corY[b]]
            plt.plot(x, y, 'k', linewidth=1)
    plt.grid(False)
    plt.legend(loc='best')
    plt.show()
def print_solution(solution, data):
    for index, subRoute in enumerate(solution.routes):
        distance = 0
        load = 0
        for i in range(len(subRoute) - 1):
            distance += data.distanceMatrix[subRoute[i]][subRoute[i + 1]]
            load += data.demand[subRoute[i]]
        print(f"Route-{index + 1} : {subRoute} , distance: {distance} , load: {load}")
def solve(data):
    # 声明模型
    model = Model("VRPTW")
    # 模型设置
    # 关闭输出
    model.setParam('OutputFlag', 0)
    # 定义变量
    X = [[[[] for _ in range(data.vehicleNum)] for _ in range(data.nodeNum)] for _ in range(data.nodeNum)]
    S = [[[] for _ in range(data.vehicleNum)] for _ in range(data.nodeNum)]
    for i in range(data.nodeNum):
        for k in range(data.vehicleNum):
            S[i][k] = model.addVar(data.readyTime[i], data.dueTime[i], vtype=GRB.CONTINUOUS, name=f'S_{i}_{k}')
            for j in range(data.nodeNum):
                X[i][j][k] = model.addVar(vtype=GRB.BINARY, name=f"X_{i}_{j}_{k}")
    # 目标函数
    obj = LinExpr(0)
    for i in range(data.nodeNum):
        for j in range(data.nodeNum):
            if i != j:
                for k in range(data.vehicleNum):
                    obj.addTerms(data.distanceMatrix[i][j], X[i][j][k])
    model.setObjective(obj, GRB.MINIMIZE)
    # 约束1：车辆只能从一个点到另一个点
    for i in range(1, data.nodeNum - 1):
        expr = LinExpr(0)
        for j in range(data.nodeNum):
            if i != j:
                for k in range(data.vehicleNum):
                    if i != 0 and i != data.nodeNum - 1:
                        expr.addTerms(1, X[i][j][k])
        model.addConstr(expr == 1)
    # 约束2：车辆必须从仓库出发
    for k in range(data.vehicleNum):
        expr = LinExpr(0)
        for j in range(1, data.nodeNum):
            expr.addTerms(1, X[0][j][k])
        model.addConstr(expr == 1)
    # 约束3：车辆经过一个点就必须离开一个点
    for k in range(data.vehicleNum):
        for h in range(1, data.nodeNum - 1):
            expr1 = LinExpr(0)
            expr2 = LinExpr(0)
            for i in range(data.nodeNum):
                if h != i:
                    expr1.addTerms(1, X[i][h][k])
            for j in range(data.nodeNum):
                if h != j:
                    expr2.addTerms(1, X[h][j][k])
            model.addConstr(expr1 == expr2)
    # 约束4：车辆最终返回仓库
    for k in range(data.vehicleNum):
        expr = LinExpr(0)
        for i in range(data.nodeNum - 1):
            expr.addTerms(1, X[i][data.nodeNum - 1][k])
        model.addConstr(expr == 1)
    # 约束5：车辆容量约束
    for k in range(data.vehicleNum):
        expr = LinExpr(0)
        for i in range(1, data.nodeNum - 1):
            for j in range(data.nodeNum):
                if i != 0 and i != data.nodeNum - 1 and i != j:
                    expr.addTerms(data.demand[i], X[i][j][k])
        model.addConstr(expr <= data.capacity)
    # 约束6：时间窗约束
    for k in range(data.vehicleNum):
        for i in range(data.nodeNum):
            for j in range(data.nodeNum):
                if i != j:
                    model.addConstr(S[i][k] + data.distanceMatrix[i][j] - S[j][k] <= M - M * X[i][j][k])
    # 记录求解开始时间
    start_time = time.time()
    # 求解
    model.optimize()
    if model.status == GRB.OPTIMAL:
        print("-" * 20, "Solved Successfully", '-' * 20)
        # 输出求解总用时
        print(f"Solve Time: {time.time() - start_time} s")
        print(f"Total Travel Distance: {model.ObjVal}")
        solution = getSolution(data, model)
        plot_solution(solution, data.customerNum)
        print_solution(solution, data)
    else:
        print("此题无解")
if __name__ == '__main__':
    # 哪个数据集
    data_type = "c101"
    # 数据集路径
    data_path = f'../../data/solomn_data/{data_type}.txt'
    # 顾客个数设置（从上往下读取完 customerNum 个顾客为止，例如c101文件中有100个顾客点，
    # 但是跑100个顾客点太耗时了，设置这个数是为了只选取一部分顾客点进行计算，用来快速测试算法）
    # 如果想用完整的顾客点进行计算，设置为None即可
    customerNum = 50
    # 一个很大的正数
    M = 10000000
    # 读取数据
    data = readData(data_path, customerNum)
    # 输出相关数据
    print("-" * 20, "Problem Information", '-' * 20)
    print(f'Data Type: {data_type}')
    print(f'Node Num: {data.nodeNum}')
    print(f'Customer Num: {data.customerNum}')
    print(f'Vehicle Num: {data.vehicleNum}')
    print(f'Vehicle Capacity: {data.capacity}')
    # 建模求解
    solve(data)

3.3 运行结果展示

3.3.1 测试案例：c101.txt

设置 customerNum = 20

-------------------- Problem Information --------------------
Data Type: c101
Node Num: 22
Customer Num: 20
Vehicle Num: 25
Vehicle Capacity: 200.0
-------------------- Solved Successfully --------------------
Solve Time: 0.2966279983520508 s
Total Travel Distance: 160.81590595966603
Route-1 : [0, 20, 13, 17, 18, 19, 15, 16, 14, 12, 0] , distance: 101.32767502613292 , load: 200.0
Route-2 : [0, 5, 3, 7, 8, 10, 11, 9, 6, 4, 2, 1, 0] , distance: 59.48823093353308 , load: 160.0

设置 customerNum = 50

Data Type: c101
Node Num: 52
Customer Num: 50
Vehicle Num: 25
Vehicle Capacity: 200.0
-------------------- Solved Successfully --------------------
Solve Time: 4.383494138717651 s
Total Travel Distance: 363.2468004115909
Route-1 : [0, 5, 3, 7, 8, 10, 11, 9, 6, 4, 2, 1, 0] , distance: 59.48823093353308 , load: 160.0
Route-2 : [0, 32, 33, 31, 35, 37, 38, 39, 36, 34, 0] , distance: 97.2271627850669 , load: 200.0
Route-3 : [0, 43, 42, 41, 40, 44, 46, 45, 48, 50, 49, 47, 0] , distance: 59.843107259523165 , load: 140.0
Route-4 : [0, 20, 24, 25, 27, 29, 30, 28, 26, 23, 22, 21, 0] , distance: 50.80359030264955 , load: 170.0
Route-5 : [0, 13, 17, 18, 19, 15, 16, 14, 12, 0] , distance: 95.88470913081827 , load: 190.0

设置 customerNum = None

-------------------- Problem Information --------------------
Data Type: c101
Node Num: 102
Customer Num: 100
Vehicle Num: 25
Vehicle Capacity: 200.0
-------------------- Solved Successfully --------------------
Solve Time: 272.5895857810974 s
Total Travel Distance: 828.9368669428341
Route-1 : [0, 20, 24, 25, 27, 29, 30, 28, 26, 23, 22, 21, 0] , distance: 50.80359030264955 , load: 170.0
Route-2 : [0, 57, 55, 54, 53, 56, 58, 60, 59, 0] , distance: 101.88256760196126 , load: 200.0
Route-3 : [0, 5, 3, 7, 8, 10, 11, 9, 6, 4, 2, 1, 75, 0] , distance: 59.618077542105574 , load: 180.0
Route-4 : [0, 98, 96, 95, 94, 92, 93, 97, 100, 99, 0] , distance: 95.94313062205805 , load: 190.0
Route-5 : [0, 81, 78, 76, 71, 70, 73, 77, 79, 80, 0] , distance: 127.29748041459519 , load: 150.0
Route-6 : [0, 32, 33, 31, 35, 37, 38, 39, 36, 34, 0] , distance: 97.2271627850669 , load: 200.0
Route-7 : [0, 43, 42, 41, 40, 44, 46, 45, 48, 51, 50, 52, 49, 47, 0] , distance: 64.80747449698114 , load: 160.0
Route-8 : [0, 90, 87, 86, 83, 82, 84, 85, 88, 89, 91, 0] , distance: 76.06956532288787 , load: 170.0
Route-9 : [0, 13, 17, 18, 19, 15, 16, 14, 12, 0] , distance: 95.88470913081827 , load: 190.0
Route-10 : [0, 67, 65, 63, 62, 74, 72, 61, 64, 68, 66, 69, 0] , distance: 59.403108723710105 , load: 200.0

3.3.2 测试案例：r101.txt