CPLEX OPL实现VRP车辆路径问题建模及代码修正求助

原代码核心问题 #

• 集合定义逻辑错误：将配送中心单独拆分到独立节点集合，未构建包含配送中心、客户点的全量节点集合，距离矩阵维度与节点数量完全不匹配
• 决策变量定义错误：未绑定车辆维度，且错误使用连续型变量表示路径选择关系，无法实现「车辆-路径-客户」的关联映射
• 目标函数逻辑错误：未关联决策变量，直接对距离值求和，无法实现总行驶路径最短的优化目标
• 约束缺失：仅保留了不完整的需求约束，缺少流平衡约束、车辆容量约束、子回路消除约束、车辆出发/返回配送中心约束，无法生成合法的配送路径

可直接运行的修正代码 #

1. 模型文件（.mod） #

{string} Vehicles = ...;       // 配送车辆集合
{string} Customers = ...;      // 客户点集合
{string} Depot = {"Enns"};     // 单配送中心
{string} Nodes = Depot union Customers; // 全量节点 = 配送中心 + 客户点

// 模型参数
int demand[Customers] = ...;   // 各客户点需求量
int cap[Vehicles] = ...;       // 各车辆额定载重
int dist[Nodes][Nodes] = ...;  // 节点间两两距离矩阵

// 决策变量
dvar boolean x[Vehicles][Nodes][Nodes]; // x[k][i][j]=1 表示车辆k从节点i行驶到节点j，否则为0
dvar float+ u[Nodes];                   // MTZ子回路消除辅助变量

// 目标函数：最小化所有车辆总行驶距离
minimize totalDistance:
  sum(k in Vehicles, i in Nodes, j in Nodes) dist[i][j] * x[k][i][j];

subject to {
  // 约束1：每个客户恰好被1台车访问1次
  forall(c in Customers)
    visitOnce:
      sum(k in Vehicles, j in Nodes: j != c) x[k][c][j] == 1;
  
  // 约束2：流平衡，车辆到达某节点后必须离开该节点
  forall(k in Vehicles, n in Nodes)
    flowBalance:
      sum(i in Nodes: i != n) x[k][i][n] == sum(j in Nodes: j != n) x[k][n][j];
  
  // 约束3：所有车辆从配送中心出发，完成配送后返回配送中心，每台车最多出勤1次
  forall(k in Vehicles)
    startDepot:
      sum(j in Customers) x[k]["Enns"][j] <= 1;
  forall(k in Vehicles)
    backDepot:
      sum(i in Customers) x[k][i]["Enns"] == sum(j in Customers) x[k]["Enns"][j];
  
  // 约束4：车辆载重约束，单台车服务客户总需求不超过额定容量
  forall(k in Vehicles)
    capLimit:
      sum(c in Customers, j in Nodes: j != c) demand[c] * x[k][c][j] <= cap[k];
  
  // 约束5：MTZ子回路消除，避免出现不经过配送中心的客户点闭环
  forall(i in Customers, j in Customers: i != j)
    subTourCut:
      u[i] - u[j] + card(Nodes) * sum(k in Vehicles) x[k][i][j] <= card(Nodes) - 1;
}

// 求解结果自动输出
execute{
  writeln("=== VRP求解结果 ===");
  for(var k in Vehicles){
    var route = ["Enns"];
    var current = "Enns";
    var totalLoad = 0;
    var routeDist = 0;
    while(true){
      var next = "";
      for(var n in Nodes){
        if(n != current && x[k][current][n] >= 0.9){
          next = n;
          break;
        }
      }
      if(next == "Enns" || next == "") break;
      route.push(next);
      totalLoad += demand[next];
      routeDist += dist[current][next];
      current = next;
    }
    routeDist += dist[current]["Enns"];
    if(route.length > 1){
      route.push("Enns");
      writeln("车辆",k," 服务客户：", route.slice(1, route.length-1), " 总载重：", totalLoad, " 路径长度：", routeDist);
    }else{
      writeln("车辆",k," 未启用");
    }
  }
}

2. 数据文件（.dat） #

注：你提供的原始距离数据仅包含客户点到配送中心的单边距离，缺少客户点之间的两两距离，以下代码临时用「客户i到配送中心距离 + 客户j到配送中心距离」近似客户间距离，后续替换为真实路网距离即可获得精准结果

Vehicles = {k1,k2,k3,k4,k5,k6,k7,k8,k9,k10,k11,k12,k13,k14,k15};

Customers = {Taubenmarkt,Landstrasse,LLenaupark,LLandstrasse,Industriezeile,LentiaCity,LLeonding,LInterspar,KarlSteigerStrasse,Kornstrasse,Traunerkreuzung,PlusKaufStrasse,FMZ,Haid,Marchtrenk,EferdingPupping,Walding,Rohrbach,BadLeonfelden,LAltenbergerstrasse,Gallneukirchen,Unterweitersdorf,FMZNord,Mauthausen,Furnpark,FMZEnnspark,NaarerStrasse,Steyr,SteyrResthofstrasse,SteyrHaagerStrasse,Sierning,LHartheimeerstrasse,BadHall,Micheldorf,Vorchdorf,WelsBäckergasse,Dalistrasse,WelsOberfeldstrasse,MaxCenter,GrieskirchenSchlüsselberg,DruckereistrasseSEP,Laakirchen,Schwanenstadt,Ampflwang,RiedTumeltshamFMZ,Weberzeile,Schärding,BadIschlFMZ,BadIschlZentrum,VöcklabruchZentrum,Varena,FMZTimelkam,StGeorgen,Mondsee,CityCenter,Mattighofen};

cap = [17,17,17,17,17,17,17,17,17,17,17,17,17,17,17];

demand = [2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2];

// 你提供的客户点到配送中心Enns的距离
int depotDist[Customers] = [23,22,22,24,12,24,19,18,22,23,23,16,20,33,41,35,68,52,28,37,42,63,10,4,3,17,22,21,21,28,11,36,63,52,43,37,38,43,55,75,64,64,90,82,81,106,111,108,77,76,80,87,110,123,117,120];

// 自动生成全节点距离矩阵
dist = arrayInit(Nodes, Nodes, 0);
execute{
  for(var c in Customers){
    dist["Enns"][c] = depotDist[c];
    dist[c]["Enns"] = depotDist[c];
    dist[c][c] = 0;
    for(var c2 in Customers: c2!=c){
      // 此处替换为客户c到c2的真实距离即可
      dist[c][c2] = depotDist[c] + depotDist[c2];
    }
  }
}

运行说明 #

• 单台车辆容量17，单个客户需求为2，单台车最多可服务8个客户，15台车辆总容量可完全覆盖56个客户的总需求，模型存在可行解
• 求解完成后控制台会直接输出每台车辆对应的服务客户列表、总载重、路径总长度，未出勤的车辆会单独标注
• 替换客户间真实距离后，求解结果可直接用于实际配送调度参考

内容的提问来源于stack exchange，提问作者Johanna Weber