Originally posted by: jef_ti

Hi all,

my name is Jefferson, i'm working on ALL, a provider of logistic services in South America. Some weeks ago i decided to try constraint optimization to solve train cross rescheduling problem using ILOG CP, there are several articles on this subject but the coding process is a little bit complicated.

this model below is a simplificated form of the occupation structure, a resource (section) can be used (occupied by a train - dvOcupacao) and after released this resource remains used (dvDesocupacao) by the train tail by 1 unit of time (minutes).

the section 5 and 45 allow crossing and the trains are in oposite direction (1 - section 1 to 50 and 2 - section 50 to 1), the tail ocuppation starts after a section release and just 1 resource can be used at a time.

My problem:
if my dvOcupacao have 1..100 of domain my solution is achieved in 2 seconds, decreasing to 1..40 (reducing the domain) my solution came only after 5 seconds.

With 2 trains this seconds are ok but in a complex scene my response time increases without control.

Someone can help me?

/*********************************************
* OPL 12.2.0.2 Model
* Author: jefferson.biernastki
* Creation Date: Jul 30, 2011 at 3:35:46 PM
*********************************************/

int maxSections = 50;
{int} stationYard = { 5, 45 }; // Simulation of yard station

range sections = 1..maxSections;
range trains = 1..2;

execute
{
var f = cp.factory;

//cp.param.SearchType = "multipoint";
//cp.param.TimeLimit = 20;
//cp.param.SolutionLimit = 1;
}

using CP;

// At least 1 minute for pass
dvar interval dvOcupacaosectionstrains size 1..10;
// 1 minute for tail
dvar interval dvDesocupacaosectionstrains size 1;

cumulFunction cfOcupacaoc in sections = sum(k in sections, l in trains : c == k && k not in stationYard) pulse(dvOcupacao[k][l], 1);
cumulFunction cfDesocupacaoc in sections = sum(k in sections, l in trains : c == k && k not in stationYard) pulse(dvDesocupacao[k][l], 1);

// Tardiness of activities
//dexpr int totalTardiness = sum(k in sections, l in trains) (sizeOf(dvOcupacao[k][l]) - 1);

//dexpr float totalWeightedTardiness = sum(k in sections, l in trains) ((sizeOf(dvOcupacao[k][l]) - 1) * 1 / k);
dexpr float totalLinWeightedTardiness = sum(k in sections, l in trains) ((sizeOf(dvOcupacao[k][l]) - 1) * (maxSections - k) / maxSections);

minimize totalLinWeightedTardiness;

subject to
{
// Start of Activities
startOf(dvOcupacao[1][1]) == 0;
startOf(dvOcupacaomaxSections[2]) == 0;

// Max time in arrives
sizeOf(dvOcupacaomaxSections[1]) == 1;
sizeOf(dvOcupacao[1][2]) == 1;

// Sequence of activities
forall (i in sections : i < maxSections)
{
// From section 1 to max sections (down)
startAtEnd(dvOcupacaoi + 1[1], dvOcupacao[i][1]);

// From section MAX to section 1 (oposite direction - up)
startAtEnd(dvOcupacaomaxSections - i[2], dvOcupacao(maxSections + 1) - i[2]);
}

// Section use
forall (i in sections, j in trains)
{
startAtEnd(dvDesocupacao[i][j], dvOcupacao[i][j]);
}

// Ocupation control
forall (i in sections)
{
cfOcupacao[i] + cfDesocupacao[i] <= 1;
}
}
</code>

sorry my english...

Thanks in advance,

Jefferson Soares Biernastki
Coordenação de Sistemas Operacionais
Gerência de Tecnologia
ALL - América Latina Logística
Fone: (41) 2141-8613
Fax: (41) 2141-7408

Visit our website: www.all-logistica.com
#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

Hello,
The problem is due to the fact the engine does not notice early enough that once he has started to schedule two trains to run on opposite direction on a part of the network where crossing is not allowed (say sections 6..44) then, this whole sub-tree is infeasible.

You could try to add redundant constraints that for each segment (segment = set of contiguous sections) on which no crossing is allowed will post the constraint that at any moment, there cannot be several trains moving on different directions along this segment. This can be done thanks to a state function per segment. The state of the state function represents the direction that is currently used (at most one). Here is a model adapted from yours that implement this idea. Note that I hard-coded the additional interval variables and state functions, this is only for illustrative purpose. Depending on the exact topology of the network this idea may be harder to implement.

using CP;   

int maxSections = 50; 
{

int
} stationYard = 
{ 5, 45 
}; 
// Simulation of yard station   range sections = 1..maxSections; range trains = 1..2;   
// 1 minute for tail 

int TailTime = 1; 
// At least 1 minute for pass 

int DMin = 1; 

int DMax = 10;   dvar interval dvOcupacao[k in sections][l in trains] size (TailTime+DMin)..(TailTime+DMax); 
//..10;   cumulFunction cfOcupacao[c in sections] = sum(k in sections, l in trains : ((c==k) && (k not in stationYard))) pulse(dvOcupacao[k][l], 1); 
// Tardiness of activities dexpr 

float totalLinWeightedTardiness = sum(k in sections, l in trains) ((sizeOf(dvOcupacao[k][l]) - DMin - TailTime) * (maxSections - k) / maxSections);   execute 
{ cp.param.TimeLimit = 20; 
}   
// Those model elements (stateFunction, intervals) are hard-coded for illustration   stateFunction Dir1_4;   
// Segment of line between sections 1 and 4  (no crossing allowed, so at most one direction used) stateFunction Dir6_44;  
// Segment of line between sections 6 and 44 (no crossing allowed, so at most one direction used) stateFunction Dir46_50; 
// Segment of line between sections 46 and 50 (no crossing allowed, so at most one direction used)   dvar interval T1Sections1To4;   
// Segment {1..4}  used by Train 1, direction 1 dvar interval T1Sections6To44;  
// Segment {6..44} used by Train 1, direction 1 dvar interval T1Sections46To50; 
// Segment {46..50} used by Train 1, direction 1 dvar interval T2Sections4To1;   
// Segment {1..4}  used by Train 2, direction 2 dvar interval T2Sections44To6;  
// Segment {6..44} used by Train 2, direction 2 dvar interval T2Sections50To46; 
// Segment {46..50} used by Train 2, direction 2   minimize totalLinWeightedTardiness;   subject to 
{   startAtStart(T1Sections1To4,   dvOcupacao[1][1]);  endAtEnd(T1Sections1To4,    dvOcupacao[4][1]); alwaysEqual(Dir1_4,T1Sections1To4,1); startAtStart(T1Sections6To44,  dvOcupacao[6][1]);  endAtEnd(T1Sections6To44,   dvOcupacao[44][1]); alwaysEqual(Dir6_44,T1Sections6To44,1); startAtStart(T1Sections46To50, dvOcupacao[46][1]); endAtEnd(T1Sections46To50,  dvOcupacao[50][1]); alwaysEqual(Dir46_50,T1Sections46To50,1); startAtStart(T2Sections4To1,   dvOcupacao[4][2]);   endAtEnd(T2Sections4To1,   dvOcupacao[1][2]); alwaysEqual(Dir1_4,T2Sections4To1,2); startAtStart(T2Sections44To6,  dvOcupacao[44][2]);  endAtEnd(T2Sections44To6,  dvOcupacao[6][2]); alwaysEqual(Dir6_44,T2Sections44To6,2); startAtStart(T2Sections50To46, dvOcupacao[50][2]);  endAtEnd(T2Sections50To46, dvOcupacao[46][2]); alwaysEqual(Dir46_50,T2Sections50To46,2); 
// Start of Activities startOf(dvOcupacao[1][1]) == 0; startOf(dvOcupacao[maxSections][2]) == 0;   
// Max time in arrives sizeOf(dvOcupacao[maxSections][1]) == 1+TailTime; sizeOf(dvOcupacao[1][2]) == 1+TailTime;   
// Sequence of activities forall (i in sections : i < maxSections) 
{ 
// From section 1 to max sections (down) endAtStart(dvOcupacao[i][1], dvOcupacao[i+1][1],-TailTime); 
// From section MAX to section 1 (oposite direction - up) endAtStart(dvOcupacao[(maxSections+1)-i][2], dvOcupacao[maxSections - i][2],-TailTime); 
}   
// Ocupation control forall (i in sections) 
{ cfOcupacao[i] <= 1; 
} 
}

This model works indeed much better.

Philippe
#CPOptimizer
#DecisionOptimization