0

我正在建模具有容量限制的调度问题。任务是安排一组必须由特定机器执行的操作。更具体地说,我有一组车辆和一组位置,车辆必须访问这些位置才能执行一些操作。每个位置最多可以处理一辆车,并且每辆车都有最大容量。有两种类型的操作:取货和送货操作。取货操作对应于正需求,而交付操作对应于负需求。任务是安排所有操作,同时尊重车辆的容量限制。

我想使用 CPLEX 的 CP 优化器,并且我正在使用 Java Eclipse 对其进行建模。

我尝试使用 cumul 函数表达式对此进行建模,因为我可以使用 StepAtStart 函数来指示操作开始时容量的增加。但是,该函数不模拟负值。

我已经尝试过这段代码,灵感来自 SchedRCPSP 示例。但我不能输入负值,也不能减去负需求的表达式。

IloIntervalVar[] opList = new IloIntervalVar[nbOp];
[...]
[...]
IloCumulFunctionExpr[] resources = new IloCumulFunctionExpr[nbVeh];
for(int v = 1; v < nbVeh -1 ; v++) {
      resources[v] = cp.cumulFunctionExpr();          
}
for(int i = 0; i < nbOp; i++) {
      Operation opi = operations.get(i);
      if(opi.Demand> 0) {
            resources[opi.vehicle] = 
            cp.sum(resources[opi.vehicle], 
                   cp.stepAtStart(opList[i], opi.Demand));
      }else {                        
            resources[opi.vehicle] = 
            // THIS SHOULD BE A SUBSTRACTION (NEGATIVE DEMAND)
            cp.sum(resources[opi.vehicle],
                  cp.stepAtStart(opList[i],opi.Demand));                        
      }
      if(opi.StartOperation){            
        resources[opi.vehicle] = 
        cp.sum(resources[opi.vehicle],
               cp.stepAtStart(opList[i],opi.initialLoad));
      }
}
for(int v = 1; v < nbVeh - 1 ; v++) {
      cp.add(cp.le(resources[v], inst.capacities.get(v)));
}

这是正确的方法吗?有没有办法模拟车辆内货物的这种波动?我想建模一种方法来禁止违反容量限制的车辆的某些排列。

例如,如果我的车辆容量为 10 辆,初始装载量为 8 辆,以及两个操作 A 和 B(操作 A:在城市 1 提取 4 个单元。操作 B:在城市 2 交付 5 个单元)。我希望不允许排列(A->B),因为它违反了城市 1 车辆的容量限制。

4

1 回答 1

0

更好的解决方案是为每个项目和每个可能的车辆创建一个可选的间隔变量,其开始日期是装载日期,结束日期是卸载日期,将其最小尺寸设置为装载和卸载位置之间的时间距离。(不要忘记为项目添加车辆的替代品)

然后为每辆车添加的累积约束为:

cp.add(cp.le(cp.sum(pulse(transport[v][i],opi.initialLoad)), inst.capacities.get(v)));

由于加载和卸载日期之间的时间相关性,这将简化模型声明并提高求解器的性能

希望有所帮助

于 2019-08-14T15:26:59.577 回答