CPLEX约束编程中表达式未绑定问题求助

问题背景 #

基于Kyle.E.C.Booth的论文《A Constraint Programming Approach to Electric Vehicle Routing with Time Windows》，使用CPLEX约束编程（CP）开发带时间窗的电动车路径模型时，遇到错误：stepAtEnd函数内的distancematrix[typeOfPrev(route_time[v], vehvisit_time[b][v],0,0)][b]为未绑定表达式。核心问题是typeOfPrev无法在stepAtEnd函数内使用。

原代码试图通过typeOfPrev获取序列中前一个节点，进而计算行驶距离消耗，但这种写法不符合CPLEX CP的语法规则。

原因分析 #

CPLEX CP中，stepAtEnd（或stepAtStart）的步长参数必须是编译时可确定的常量，或已绑定的变量，而typeOfPrev是依赖于序列决策变量的动态表达式——其值只有在求解过程中确定了序列顺序后才能得到，属于未绑定表达式，因此无法直接用于stepAtEnd的步长定义。

解决方案 #

改用stateFunction跟踪电池电量变化，结合transition约束处理路径中相邻节点的距离消耗，同时用when约束处理充电节点的电量重置。这种方式可以正确关联序列的动态顺序与电池状态的变化。

修改后的关键代码片段 #

1. 替换原cumulFunction battery_load定义，改用stateFunction：

// 替换原battery_load的cumulFunction定义为stateFunction
stateFunction battery_state[v in vehicle] = initial(batterycapa[v]);

2. 添加transition约束，处理相邻节点的电池消耗：

// 约束：序列中从prev节点到curr节点时，电池减少对应行驶距离的电量
ct_transition_battery:
forall(v in vehicle, prev, curr in allnode)
  transition(route_time[v], prev, curr, battery_state[v], battery_state[v] - distancematrix[prev][curr]);

3. 添加充电节点的电量重置约束：

// 约束：当车辆到达充电节点时，电池立即充满
ct_charge_reset:
forall(v in vehicle, f in charge)
  when(startOf(vehvisit_time[f][v]))
    battery_state[v] == batterycapa[v];

4. 修改原电量范围检查约束，基于stateFunction实现：

// 修改原ct10，基于stateFunction检查电量范围
ct10:
forall(v in vehicle)
    alwaysIn(battery_state[v], start[1], end[1], 0, batterycapa[v]);

// 修改原ct11，基于stateFunction检查充电时的电量
ct11:
forall(v in vehicle, f in charge)
    alwaysIn(battery_state[v], vehvisit_time[f][v], batterycapa[v], batterycapa[v]);

完整修改后代码框架 #

using CP;

int NoDepot = ...;
int NoCharge = ...;
int NoCustomer = ...;
int NoVehicle = ...;

range depot = 1 .. NoDepot;
range dummydepot = NoDepot+1 .. NoDepot*2;
range charge = NoDepot*2+1 .. NoDepot*2+NoCharge;
range customer = NoDepot*2+NoCharge+1 .. NoDepot*2+NoCharge+NoCustomer;
range allnode = 1..NoDepot*2+NoCharge+NoCustomer;
range vehicle = 1..NoVehicle;

int start[allnode] = ...;
int end[allnode] = ...;

int demand[customer] = ...;
int servicetime[customer] = ...;
int batterycapa[vehicle] = ...;
int loadcapa[vehicle] = ...;

int consumerate = 1;
int rechargerate = 1;

int alpha = 1;
int beta = 1;

int distancematrix[0..NoDepot*2+NoCharge+NoCustomer][0..NoDepot*2+NoCharge+NoCustomer] = ...; 
int timematrix[0..NoDepot*2+NoCharge+NoCustomer][0..NoDepot*2+NoCharge+NoCustomer] = ...;

tuple triplet { int id1; int id2; int value; };
{triplet} Mdist = {<id1,id2,distancematrix[id1][id2]> | id1,id2 in allnode};
{triplet} Mtime = {<id1,id2,timematrix[id1][id2]> | id1,id2 in allnode};

dvar interval visit[c in customer] in start[c]..end[c] size servicetime[c];
dvar interval vehvisit_dist[a in allnode][v in vehicle] optional size 0;
dvar interval vehvisit_time[a in allnode][v in vehicle] optional;

dvar sequence route_dist[v in vehicle] in all (a in allnode)vehvisit_dist[a][v] types all(a in allnode) a;
dvar sequence route_time[v in vehicle] in all (a in allnode)vehvisit_time[a][v] types all(a in allnode) a;

dvar interval vehicle_dist[v in vehicle] optional;

cumulFunction carry_load[v in vehicle] = stepAtStart(vehvisit_time[1][v],loadcapa[v]) 
                - sum(c in customer)stepAtStart(vehvisit_time[c][v],demand[c]);

// 替换原battery_load的cumulFunction定义为stateFunction
stateFunction battery_state[v in vehicle] = initial(batterycapa[v]);

subject to
{
    ct1:
    forall(c in customer)
        alternative(visit[c],all(v in vehicle)vehvisit_time[c][v]);
    
    ct2:
    forall(v in vehicle)
        noOverlap(route_dist[v],Mdist,true);
    
    ct3:
    forall(v in vehicle)
        noOverlap(route_time[v],Mtime,true);
    
    ct4:
    forall(v in vehicle)
        sameSequence(route_dist[v], route_time[v]);
    
    ct5:
    forall(v in vehicle)
        presenceOf(vehvisit_time[1][v]);
        
    ct6:
    forall(v in vehicle)
        presenceOf(vehvisit_time[2][v]);

    ct7:
    forall(v in vehicle)
    {
        first(route_time[v],vehvisit_time[1][v]);
        last(route_time[v],vehvisit_time[2][v]);        
    }   
    
    ct8:
    forall(v in vehicle)
        span(vehicle_dist[v], all(a in allnode)vehvisit_time[a][v]);

    ct9:
    forall(v in vehicle)
        alwaysIn(carry_load[v],start[1], end[1], 0, loadcapa[v]);
    
    // 新增：处理相邻节点的电池消耗
    ct_transition_battery:
    forall(v in vehicle, prev, curr in allnode)
      transition(route_time[v], prev, curr, battery_state[v], battery_state[v] - distancematrix[prev][curr]);
    
    // 新增：充电节点的电量重置
    ct_charge_reset:
    forall(v in vehicle, f in charge)
      when(startOf(vehvisit_time[f][v]))
        battery_state[v] == batterycapa[v];
    
    // 修改原ct10，基于stateFunction检查电量范围
    ct10:
    forall(v in vehicle)
        alwaysIn(battery_state[v], start[1], end[1], 0, batterycapa[v]);
    
    // 修改原ct11，基于stateFunction检查充电时的电量
    ct11:
    forall(v in vehicle, f in charge)
        alwaysIn(battery_state[v], vehvisit_time[f][v], batterycapa[v], batterycapa[v]);
}

///////////// .dat file
SheetConnection file("final.xlsx");

NoDepot from SheetRead(file, "NoDepot");
NoCharge from SheetRead(file, "NoCharge");
NoCustomer from SheetRead(file, "NoCustomer");
NoVehicle from SheetRead(file, "NoVehicle");
start from SheetRead(file, "start");
end from SheetRead(file, "end");
demand from SheetRead(file, "demand");
servicetime from SheetRead(file, "servicetime");
batterycapa from SheetRead(file, "batterycapa");
loadcapa from SheetRead(file, "loadcapa");
distancematrix from SheetRead(file, "dist");
timematrix from SheetRead(file, "time");

说明 #

• stateFunction专门用于跟踪随时间变化且依赖于前一状态的变量，非常适合电池电量这类需要根据路径动态更新的指标。
• transition约束可以精准关联序列中的相邻节点转移与状态变量的变化，解决了原写法中动态表达式无法绑定的问题。
• when约束用于在充电节点的时间区间开始时触发电量重置，确保充电逻辑正确。

内容的提问来源于stack exchange，提问作者Son nguyen hoang