Skip to content

Instantly share code, notes, and snippets.

@c3c

c3c/camions.dat

Last active December 15, 2015 11:59
Show Gist options
  • Save c3c/5256957 to your computer and use it in GitHub Desktop.
Save c3c/5256957 to your computer and use it in GitHub Desktop.
Download ZIP
C+VRP+TW working + asserts added Updated data English comments
Raw
camions.dat
/*********************************************
* OPL 12.5 Data
* Author: crash
* Creation Date: Mar 6, 2013 at 3:38:56 PM
*********************************************/
// 17 nodes, first node is depot.
// <Name, NodeType {collab|client}, WGS84-Lat, WGS84-Lon, Lam93-X, Lam93-Y, TimeWin-Min, TimeWin-Max>
AllNodes = {
<"Poitiers" 1,46.589069,0.340576,496421,6613320,360,1200>, // 0
<"La Rochelle" 2,46.176027,-1.145325,380354,6572413,360,660>, // 1
<"Angouleme" 2,45.660127,0.140076,477343,6510763,660,990>, // 2
<"Perigueux" 2,45.18978,0.722351,521155,6457075,840,1000>, // 3
<"Limoges" 1,45.830713,1.263428,565198,6527156,360,1200>, // 4
<"Clermont-Ferrand" 2,45.784764,3.109131,708479,6520577,780,940>, // 5
<"Chateauroux" 2,46.80758,1.672668,598786,6635010,360,1200>, // 6
<"Bourges" 2,47.073863,2.384033,653259,6663917,420,630>, // 7
<"Blois" 2,47.585789,1.340332,575264,6721912,500,750>, // 8
<"Angers" 2,47.476376,-0.563049,431735,6714499,360,700>, // 9
<"Nantes" 1,47.215837,-1.554565,355488,6689443,360,1200>, // 10
<"Cholet" 2,47.062638,-0.884399,405299,6669738,900,1200>, // 11
<"La Roche-sur-Yon" 2,46.675826,-1.422729,362092,6628992,800,1000>, // 12
<"Saintes" 1,45.73686,-0.6427,416833,6521784,360,1200>, // 13
<"Tours" 2,47.394631,0.686646,525525,6701921,400,900>, // 14
<"Orleans" 1,47.908978,1.895142,617461,6757086,360,1200>, // 15
<"Le Mans" 2,48.004625,0.192261,490662,6770859,360,1200> // 16
};
Dist = [ // distance pairs, in meter, /1000 als kostbepaling?
123,104,158,110,231,104,164,134,120,160,107,135,121,93,187,157,
114,182,190,332,227,287,245,151,119,100,59,62,194,300,227,69,89,
231,173,233,232,208,216,174,165,61,197,283,260,82,197,194,245,270,
272,285,242,234,122,244,315,315,143,112,162,195,230,265,214,227,
148,179,235,254,158,153,241,337,391,337,362,291,257,253,331,61,
90,184,249,196,236,214,99,123,173,97,227,298,248,293,275,133,99,
194,143,222,177,232,255,53,54,97,80,51,110,193,94,190,81,53,60,178,
170,270,157,59,148,124,229,132,120,178,285,191,210,309,259,107,77,127
];
// <Destination, From, NumPalettes>
Deliveries = {
<1,0,5>,
<2,0,15>,
<3,0,14>,
<4,0,30>,
<5,0,13>,
<6,0,16>,
<7,0,19>,
<8,0,11>,
<9,0,18>,
//<1,10,10>,
//<2,13,19>,
//<5,10,6>,
//<14,15,16>,
//<9,10,13>,
//<2,4,17>,
//<8,10,15>,
//<0,10,20>,
//<0,4,20>
};
// <ID, MaxPalettes, MaxTimeOnRoute>
Camions = {
<1,33,600>,
<2,16,600>,
<3,33,600>,
<4,22,600>,
<5,33,600>,
<6,16,600>,
<7,33,600>,
<8,33,600>,
<9,33,600>,
<10,22,600>,
<11,33,600>,
<12,33,600>,
<13,16,600>,
<14,33,600>,
<16,33,600>,
<17,33,600>,
<18,16,600>,
<19,33,600>,
<15,33,600>
};
Raw
vrp.mod
/*********************************************
* OPL 12.5 Model
* Author: crash
* Creation Date: Mar 6, 2013 at 3:33:35 PM
*********************************************/
using CP;
// Nodes
tuple node { string name; int type; float lat; float lon; int x; int y; int tmin; int tmax; }
{node} AllNodes = ...;
int N = card(AllNodes);
range nodes = 0..N-1;
// Edges
tuple edge {int i; int j;}
setof(edge) AllEdges = { <i,j> | i,j in nodes : i != j }; // not filtered!
setof(edge) OrderedEdges = { <i,j> | ordered i,j in nodes};
int Dist[OrderedEdges] = ...;
// Deliveries
tuple delivery {int destination; int from; int numpalettes;}
{delivery} Deliveries = ...;
// Only keep concerned nodes
sorted {int} clients = { d.from | d in Deliveries : d.numpalettes > 0 } union { d.destination | d in Deliveries : d.numpalettes > 0 } diff {0};
sorted {int} cities = {0} union clients;
int numCities = card(cities);
int demand[t in cities] = sum (d in Deliveries : d.destination == t) d.numpalettes;
int tmin[t in cities] = item(AllNodes, t).tmin;
int tmax[t in cities] = item(AllNodes, t).tmax;
setof(edge) Edges = { <i,j> | i,j in cities : i != j }; // filtered! :)
// Camions
tuple camion {key int id; int capacity; int maxtime;}
{camion} Camions = ...;
// Travel time
int vitesse = 65; // km/h
int tempstrajet[<i,j> in OrderedEdges] = ftoi(round(Dist[<i,j>]/vitesse*60));
int tempsservice = 30;
// Model consistency
{int} CollabNodes = { c | c in cities : item(AllNodes, c).type == 1}; // We can only collect from collaborative nodes
assert forall(d in Deliveries) CollectFromCollaborativeNode:(sum(c in CollabNodes : c == d.from) 1) > 0;
{int} ClientNodes = { c | c in cities : item(AllNodes, c).type == 2}; // Client nodes can only receive
assert forall(c in ClientNodes) ClientCanOnlyReceive:(sum (d in Deliveries : d.from == c) 1) == 0;
// Decision variables
dvar boolean x[Edges,Camions]; // if truck visits the edge
dvar boolean y[Camions,cities]; // if truck visits the node (for convenience)
dvar int+ z[Deliveries][Camions]; // how many palettes of a certain order will the truck take
dvar boolean takenby[Deliveries][Camions]; // if a certain truck takes a certain order
dvar int+ arrival[Camions][cities] in 1..numCities; // expresses continuity
dvar int+ tarrival[Camions][cities] in 0..1440; // provides actual timeframe
dexpr int charge[w in cities][k in Camions] = (sum (d in Deliveries : d.from == 0) z[d][k]) + y[k][w] * sum (i in cities, d in Deliveries) ((y[k][i]+(arrival[k][i]<=(arrival[k][w]+1)) == 2) * (z[d][k]*((d.from==i && i != 0)-(d.destination==i)))); // how many palettes does the truck have at a certain arc <v,w>
dexpr int treated[k in Camions][i in clients] = sum(d in Deliveries : d.destination == i || d.from == i) z[d][k]; // number of palettes treated at node
execute {
cp.param.TimeMode = "ElapsedTime";
cp.param.TimeLimit = 1800;
};
minimize sum (<i,j> in Edges, m in Camions) Dist[<minl(i,j), maxl(i,j)>]*x[<i,j>,m];
subject to {
// fill up dvar "takenby"
// whether a truck takes a delivery or not
forall (k in Camions, d in Deliveries)
(z[d][k]>=1) == takenby[d][k];
// fill up dvar "y"
// whether or not a truck passes by a certain node
forall (k in Camions, j in cities)
(sum(i in cities : j!=i) x[<i,j>][k]) == y[k][j];
forall (k in Camions, j in cities)
(sum(i in cities : j!=i) x[<j,i>][k]) == y[k][j];
// order must be taken by at least one truck
forall (d in Deliveries)
sum (k in Camions) takenby[d][k] >= 1;
// if the order is taken by the truck, that truck must visit both the pickup node & delivery node
forall (d in Deliveries, k in Camions)
(takenby[d][k] == 1) => (y[k][d.from] == 1 && y[k][d.destination] == 1);
// continuity
forall (p in cities, k in Camions)
((sum(i in cities : i!=p) x[<i,p>][k]) - (sum(j in cities : j!=p) x[<p,j>][k])) == 0;
// continuity, forces truck to pick a number in the "arrival" interval
forall (k in Camions, <i,j> in Edges : i!=0)
(x[<i,j>][k] == 1) => (arrival[k][i] + 1 == arrival[k][j]);
// the number of palettes that all trucks will take for a certain delivery must match the size of the delivery
forall (d in Deliveries)
sum(k in Camions) z[d][k] == d.numpalettes;
// the sum of palettes carried by all trucks to a certain node, must match the demand of that node
forall (i in cities)
sum(k in Camions, d in Deliveries : d.destination == i) z[d][k] == demand[i];
// the amount of palettes the truck is carrying must be inferior|equal to his capacity at all times
forall (k in Camions, i in cities)
(y[k][i] == 1) => (charge[i][k] <= k.capacity);
// respect timewindows (special case of depot)
forall(j in clients, k in Camions)
(x[<0,j>][k] == 1) => (tarrival[k][j] >= (tempstrajet[<0,j>] + tmin[0]));
// respect timewindows
forall (<i,j> in Edges : i!=0, k in Camions)
(x[<i,j>][k] == 1) => ((tarrival[k][i] + tempstrajet[<minl(i,j), maxl(i,j)>] + 15+(3 * treated[k][i])) <= tarrival[k][j]);
// min max timeframe for entry at client
forall(i in cities, k in Camions)
(y[k][i] ==1) => ((tmin[i] <= tarrival[k][i]) && (tarrival[k][i] <= tmax[i]));
// truck can't be longer than a certain time on route
forall (m in Camions)
m.maxtime >= ((sum (<i,j> in Edges) x[<i,j>,m]*(tempstrajet[<minl(i,j),maxl(i,j)>]+tempsservice))-tempsservice);
// pickup is before delivery
forall (d in Deliveries : d.from != 0, m in Camions)
(takenby[d][m] == 1) => (arrival[m][d.from] <= arrival[m][d.destination]);
};
// POST-processing
edge E = <0,1>; // intermediary object
execute {
writeln(charge);
var unused = "We didn't use the following trucks: ";
var nUnused = 0;
for (var k in arrival) {
var num = 0;
var last = 0;
var timetotal = 0;
var str = "- Camion "+k.id+": 0 -> ";
for (var f = 1; f <= numCities-1; f++) {
for (var i in y[k]) {
if (y[k][i] == 1 && arrival[k][i] == f) {
if (!(last == 0 && i == 0)) {
E.i = Math.min(last, i);
E.j = Math.max(i, last);
timetotal += tempstrajet[E] + tempsservice;
last = i;
if (i!=0) {
str += i+" -> ";
}
}
num++;
}
}
}
timetotal -= tempsservice;
if (num > 0) {
writeln(str + "0 (total time: "+timetotal+")");
} else {
nUnused++;
unused += "c"+k.id + " ";
}
}
if (nUnused > 0) {
writeln(unused);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment