小工具知识网

当前位置: 首页 > 行业知识 > 【运筹优化】带时间窗约束的车辆路径规划问题(VRPTW)详解 + Python 调用 Gurobi 建模求解

行业知识

【运筹优化】带时间窗约束的车辆路径规划问题(VRPTW)详解 + Python 调用 Gurobi 建模求解

2026-11-17 11:08:31 来源:互联网转载

文章目录

  • 一、概述
    • 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] [ei​,li​],其中 e i e_i ei​ 和 l i l_i li​ 分别代表该点的最早到达时间和最晚到达时间。顾客点 i ∈ V i \in V i∈V 的需求必须要在其时间窗内被送达

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


          二、VRPTW 的一般模型

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

          x i j k = { 1 ,在最优解中,弧 ( i , j ) 被车辆 k 选中 0 ,其他 s i k = 车辆 k 到达 i 的时间 模型中涉及的其他参数为 : t i j 表示车辆在弧 ( i , j ) 上的行驶时间 M 为一个足够大的正数 {x_{ijk}}=\begin{cases} 1\text{,在最优解中,弧}\left( i,j \right) \text{被车辆}k\text{选中}\\ 0\text{,其他}\\ \end{cases} \\ {s_{ik}}=\text{车辆}k\text{到达}i\text{的时间} \\ \text{模型中涉及的其他参数为}: \\ {t_{ij}}\text{表示车辆在弧}\left( i,j \right) \text{上的行驶时间} \\ M\text{为一个足够大的正数} xijk​={1,在最优解中,弧(i,j)被车辆k选中0,其他​sik​=车辆k到达i的时间模型中涉及的其他参数为:tij​表示车辆在弧(i,j)上的行驶时间M为一个足够大的正数

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

          M = m a x { b i + t i j − a j } , ∀ ( i , j ) ∈ A M=max\{b_i+t_{ij}-a_j\} , \forall (i,j)\in A M=max{bi​+tij​−aj​},∀(i,j)∈A

          综合上面引出的决策变量,并参考文献(Desaulniers et al.,2006),给出的 VRPTW 的标准模型如下:

          min ⁡ ∑ k ∈ K ∑ i ∈ V ∑ j ∈ V c i j x i j k s . t . ∑ k ∈ K ∑ j ∈ V x i j k = 1 , ∀ i ∈ C    ∑ j ∈ V x 0 j k = 1 , ∀ k ∈ K    ∑ i ∈ V x i h k − ∑ j ∈ V x h j k = 0 , ∀ h ∈ C , ∀ k ∈ K    ∑ i ∈ V x i , n + 1 , k = 1 , ∀ k ∈ K    ∑ i ∈ C q i ∑ j ∈ V x i j k ⩽ Q , ∀ k ∈ K    s i k + t i j − M ( 1 − x i j k ) ⩽ s j k    , ∀ ( i , j ) ∈ A , ∀ k ∈ K    e i ⩽ s i k ⩽ l i    , ∀ i ∈ V , ∀ k ∈ K    x i j k ∈ { 0 , 1 }    , ∀ ( i , j ) ∈ A , ∀ k ∈ K \min \sum_{k\in K}{\sum_{i\in V}{\sum_{j\in V}{{c_{ij}}{x_{ijk}}}}} \\ s.t. \sum_{k\in K}{\sum_{j\in V}{{x_{ijk}}=1 , \forall i\in C}} \\ \,\, \sum_{j\in V}{{x_{0jk}}=1 , \forall k\in K} \\ \,\, \sum_{i\in V}{{x_{ihk}}-\sum_{j\in V}{{x_{hjk}}=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_{ijk}} \leqslant Q , \forall k\in K}} \\ \,\, {s_{ik}}+{t_{ij}}-M\left( 1-{x_{ijk}} \right) \leqslant {s_{jk}}\,\,, \forall \left( i,j \right) \in A,\forall k\in K \\ \,\, e_i\leqslant {s_{ik}}\leqslant l_i\,\,, \forall i\in V,\forall k\in K \\ \,\, {x_{ijk}}\in \left\{ 0,1 \right\} \,\,, \forall \left( i,j \right) \in A,\forall k\in K mink∈K∑​i∈V∑​j∈V∑​cij​xijk​s.t.k∈K∑​j∈V∑​xijk​=1,∀i∈Cj∈V∑​x0jk​=1,∀k∈Ki∈V∑​xihk​−j∈V∑​xhjk​=0,∀h∈C,∀k∈Ki∈V∑​xi,n+1,k​=1,∀k∈Ki∈C∑​qi​j∈V∑​xijk​⩽Q,∀k∈Ksik​+tij​−M(1−xijk​)⩽sjk​,∀(i,j)∈A,∀k∈Kei​⩽sik​⩽li​,∀i∈V,∀k∈Kxijk​∈{0,1},∀(i,j)∈A,∀k∈K

          其中, Q Q Q 为车容量, q i q_i qi​ 为第 i i i 个顾客的需求:

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

            三、Python 调用 Gurobi 建模求解

            3.1 Solomn 数据集

            Solomn 数据集下载地址

            3.2 完整代码

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

            # -*- coding: utf-8 -*-## Author: WSKH# Blog: wskh0929.blog.csdn.net# Time: 2023/2/8 11:14# Description: Python 调用 Gurobi 建模求解 VRPTW 问题import timeimport matplotlib.pyplot as pltimport numpy as npfrom 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  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 solutiondef 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 

上一篇:搜狗双拼输入法,轻松掌握高效便捷打字技巧

下一篇:摩托车怎么在交管12123备案