Originally posted by: SystemAdmin

[Dav said:]

Hello,

I want to establish a flights planning with CP-optimizer.
So I have a list of flights (one flight = a departure and an arrival), a number of plane, and I want to affect flights to planes.

So how can I simply create the constraint which say that one flight can directly follow another one (airport arrival of the first is airport departure of the second), knowing that I don't want to allow empty flights.

The IloPrevious constraint can't be used because one flight can succeed another one but this is not a requirement.

Thank you very much for your help.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[Didier Vidal said:]

A possible model (if the dimension of the problems allows this) would be
  * create one optional interval per combination of flight/plane
  * one alternative per flight
  * a noOverlap constraint for each flight - optionally with transition times.

Didier.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[Didier Vidal said:]

Forget the previous answer... It ignored the constraint that consecutive flights have to be in the same airport.

Sorry.

Didier.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[Sylvain said:]

I guess from your question that you used activities to represent flights and unary resources for planes.
If so, you just need to create a reservoir resource for each pair (plane, airport) with capacity 1.
Then, you can write :

flight.requires((plane, departure_airport),1,IlcAfterStart);

flight.provides((plane, arrival_airport),1,IlcAfterEnd);

(plane, initial_airport(plane)).setInitialLevel(1);


Another way might be to map the flights assigned to a given plane to an array of integer variables which can be constrained so that any two successive flights assigned to a plane must have identical arrival and departure airport.

Does this helps ?
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[Dav said:]

Thank you very much for your answers!

Didier, what you suggest is exactly what I did but as you say, the problem is the contraints for consecutive flight :(

So I tried what Sylvain suggested (the first idea) and I think it works! I use IloCumulFunction because I'm with CP-optimizer, not Ilog Scheduler but the principle seems to work ... So for the moment, thank you and if I face to another problem I will come back :)
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[dgravot@noos.fr said:]

Hello,

You might also want to enforce the consecutive flight info directly into your data. In the following sample, I assume that trips possible connections are a given. The connection graph has trips as nodes and connections between flights as edges. The problem is now to find a partition of all nodes by paths in the graph, which can be formulated in different ways using CP. Following code uses a bijection between variables "follow" and "previous" defined for each node. Two dummy nodes are added (source and sink). Therefore, the number of flights will be the number of trips with the sink as a successor (or, equivalent, the number of trips with the source as a predecessor).


/*********************************************
* OPL 6.1.1 Model
* Author: dgravot
* Creation Date: 27 Apr 2009 at 19:07:28
*********************************************/

// assume we have a set of Trips O-D . Each trip must be covered.
// we can model the flight assigment to trip by saying that each trip belongs to a path
// we also have to force each trip to be covered exactly once.
// to count the number of paths, or to bound this number, we introduce dummy nodes source and sink
// each beginning of a trip is connected to the source
// each end of a trip is connected to the sink

using CP;


int nbTrips = ...;
range trips = 1..nbTrips;
int Source = 0;
int Sink = nbTrips+1;

tuple Link
{
int o;//first trip index
int d;//second trip index
}

{Link} links with o in trips,d in trips= ...;//assume this graph is acyclic

{int} followPossible[t in trips] = {d | <t,d> in links} union {Sink};
{int} previousPossible[t in trips] = {o | <o,t> in links} union {Source};


dvar int follow[t in trips];
dvar int previous[t in trips];

dexpr int nbFlights = count(all (t in trips) follow[t],Sink);

minimize nbFlights; //or other : min<=nbFlights<=max<br />
constraints
{
forall(t in trips)
{
follow[t] in followPossible[t];
previous[t] in previousPossible[t];
}

inverse(follow, previous);

}

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[Dav said:]

Ok thanks David.
I will also think about your idea.
And I will keep you informed of my conclusions about the different models ;)
#DecisionOptimization
#OPLusingCPOptimizer