optimization - How to write flow constraint for destination node if I have to stay at destination for some time and then move to

admin管理员组

文章数量:1395016

A team travels by car from a source node to a destination node, passing through intermediate nodes based on a predefined network. Upon arriving at a destination node, the team is required to stay for two consecutive time slots to perform a specific task. After completing the work at the current destination, the team proceeds to the next destination node, following the network path. This process is repeated iteratively: the team travels, stays for two time slots to complete the assigned work, and moves to the next destination node. The cycle continues until all designated destination nodes have been visited and the required work at each has been completed.

The problem above has been modeled using OPL CPLEX, and the corresponding code is provided below.

int N = 8;
int num_line = 11;
int num_c = 1;
int num_slot = 15;
int stay_duration = 2;
int N_T = 15;

{int} depot = {1}; 
{int} destination = {6,7}; 

{int} union_destination_depot = depot union destination;

range Line = 1..num_line;
range Node = 1..N;
range Team = 1..num_c;
range Slot = 1..num_slot;

tuple Lined {
    int road_no;
    int from_node;
    int to_node;
    int travel_time;
}

Lined Linedata[Line] = [
<1,  1,  2,   1>,
<2,  1,  3,   1>,
<3,  2,  3,   1>,
<4,  2,  4,   1>,
<5,  2,  5,   2>,
<6,  3,  5,   1>,
<7,  4,  5,   1>,
<8,  4,  6,   1>,
<9,  5,  6,   1>,
<10, 6,  7,   1>,
<11, 7,  8,   1>
];

// Decision variables
dvar boolean Flow_team_ij[Team][Line][Slot];
dvar boolean start_work[Team][Node][Slot];
dvar float z[Slot];

minimize 
    sum(s in Slot) z[s];

subject to {

forall (s in Slot) {
// Objective is to minimize the traveling of car and maximize the work

z[s] == sum (c in Team, r in Line)Flow_team_ij[c][r][s] - 
        sum (c in Team, i in destination)start_work[c][i][s];
       
// Flow Conservation (at source node)
forall (c in Team, i in depot) {
sum(r in Line: Linedata[r].from_node == i) Flow_team_ij [c][r][1] == 1;
        }
    }
    
    // Flow Conservation (at destination node)
forall (c in Team, s in Slot : !(s==1), i in destination) {
   // arrival
   sum(r in Line: Linedata[r].to_node == i) Flow_team_ij [c][r][s-1] == start_work[c][i][s];
}
forall (c in Team, s in Slot : s+2 <= N_T, i in destination) {
   // departure
   sum(r in Line: Linedata[r].from_node == i) Flow_team_ij [c][r][s+2] == start_work[c][i][s];

}
// Flow Conservation (at intermediate node)

forall (c in Team, s in Slot: !(s==1), i in Node: i not in destination) {    
sum(r in Line: Linedata[r].to_node == i) Flow_team_ij[c][r][s-1] - sum(r in Line: Linedata[r].from_node == i) Flow_team_ij[c][r][s] == 0;
  }
    
forall (s in Slot, i in destination) {   
    sum (c in Team) start_work[c][i][s]<=1;
  }   

forall (i in destination) {   
    sum (s in Slot, c in Team) start_work[c][i][s]==1;
  } 
}

The model fails to produce a solution (model is giving no value) because the flow conservation constraint at the destination node is not properly handled. Specifically, the model does not account for the requirement that the crew must remain at the destination node for a fixed duration before continuing to the next node.

I am seeking the correct formulation of flow conservation constraints at destination node that ensures the team: (1) arrives at the destination node, (2) stays for a specified number of time slots (e.g., two slots), and (3) departs only after staying at destination node for two time slots. Please suggest the appropriate constraint structure to correctly represent this behavior.

本文标签：