I have built the model, but at this point, I am not sure how do I ensure that each fighter starts from the assigned depot and comes back to that depot. here is my code. The dist2 matrices is of size $\{1..19\}$ while all the depots have the same location.

Han Solo is heading a major relief operation across the galaxy. He needs to deliver relief goods to many planets that were attacked by the imperial fleet. The deliveries are achieved by dispatching a fleet of X-wing fighters from the ice planet Hoth (planet 0). He must design a route for each fighter so that all the planets are served by exactly one fighter.

The fighters have a fixed storage capacity and the planets have different demands in relief goods. Solo must minimize the time at which the latest planet gets its relief (not the time at which the fighter comes back). Time in the galaxy is directly proportional to distance. Thanks to the new generation of X-wing fighters that are now using a combination of hydrogen and carbon that was captured in the long extinguished planet Earth.

The data declarations, and some helpful code, are given by:

  • On Hoth, each fighter is hosted in a specific depot, and fighter $i$ is in depot $i$.
  • The locations consist of all the depots on Hoth and all the planets that must be visited.
  • The array element data[l] gives you, for a location $l$, its $(x,y)$ coordinate, and its demand.
  • The depots on Hoth obviously have no demand.
  • It is highly recommended to have decision variables for the predecessor and successor of each location, i.e., where the fighter comes from before arriving at a location and where it is flying to, and to build a circuit.
  • The output should be an array next[Locations].

The code is:

using CP;

int nbSites = ...;
int nbFighters = ...;
int capacity[1..nbFighters] = ...;

range Sites = 0..nbSites-1;
    tuple Site {
    int demand;
    int x;
    int y;
Site siteData[Sites] = ...;

int nbLocations = nbFighters + nbSites - 1;
range Locations = 1..nbLocations;
range Depots = 1..nbFighters;
range Customers = (nbFighters + 1)..nbLocations;
Site data[l in Locations] = (l <= nbFighters)? siteData[0] : siteData[l-nbFighters];

int dist[i in Locations,j in Locations] = 
ftoi(round(sqrt((data[i].x - data[j].x)^2 + (data[i].y - data[j].y)^2)));

dvar interval visit[t in Locations][l in 1..nbFighters] optional  ;
dvar sequence figheroute[l in 1..nbFighters] in all (t in Locations) visit [t][l];

tuple triplet { int p1; int p2; int d; };

{triplet} dist2 = 
{<p1,p2,dist[p1][p2]> | p1,p2 in Locations } ;

// Constraints
subject to {
    forall (t in Customers)
    sum(l in 1..nbFighters)presenceOf(visit [t][l])==1;

forall (l in 1..nbFighters){
    noOverlap(figheroute[l], dist2);
    sum(t in Customers) data[t - nbFighters].demand * presenceOf(visit[t][l]) <= capacity[l];

In the current solution, each fighter does not start from its corresponding depot. I don't know why, can anybody help? (I am new to using global constraints).



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.