Mathematical Modeling with LPL : Explain and run a Model
Problem Statement
Modeling Description
||
Back to MatMod
model cvrp "Capacitated Vehicle Routing Problem"; set i,j "customers"; k "trucks"; parameter d{i,j} "distances"; dw{i} "distance from/to the warehouse"; dem{i} "demand"; CA "truck capacity"; alldiff x{k,i} 'partition' [1..#i]; expression cc{k}: count{i} x; trucksUsed{k}: cc[k] > 0; routeDistances{k}: sum{i in 2..cc} d[x[k,i-1],x[k,i]] + if(cc[k]>0, dw[x[k,1]] + dw[x[k,cc[k]]]); nbTrucksUsed: sum{k} trucksUsed[k]; totalDistance: sum{k} routeDistances[k]; constraint CAP{k}: sum{i|x} dem[x[k,i]] <= CA; minimize obj1: nbTrucksUsed; minimize obj2: totalDistance; model data; set h; //h is i plus 1, 1 is depot (warehouse) parameter de{h}; n; m; X{h}; Y{h}; string typ; dum; Read('cvrp-instances/A-n32-k5.vrp,%1;-1:DIMENSION',dum,dum,n); --Read('instances/A-n45-k6.vrp,%1;-1:DIMENSION',dum,dum,n); Read('%1;-1:EDGE_WEIGHT_TYPE',dum,dum,typ); if typ<>'EUC_2D' then Write('Only EUC_2D is supported\n'); return 0; end; Read('%1;-1:CAPACITY',dum,dum,CA); Read{h}('%1:NODE_COORD_SECTION:DEMAND_SECTION', dum,X,Y); Read{h}('%1:DEMAND_SECTION:DEPOT_SECTION', dum,de); m:=Ceil(sum{h} de/CA); k:=1..m; i:=1..n-1; d{i,j}:=Round(Sqrt((X[i+1]-X[j+1])^2+(Y[i+1]-Y[j+1])^2)); dem{i}:=de[i+1]; dw{i}:=Round(Sqrt((X[i+1]-X[1])^2+(Y[i+1]-Y[1])^2)); end model output friend data; parameter y{k,i}; {k} (y[k,1]:=1, y[k,cc+2]:=1,{i|i<=cc} (y[k,i+1]:=x+1)); Draw.Scale(5,5); {k,i in 1..cc+1} Draw.Line(X[y],Y[y],X[y[k,i+1]],Y[y[k,i+1]],k+3,3); {k,i in 1..cc+2} Draw.Circle(y&'',X[y],Y[y],2,1,0); Write{k}('Tour %d: %3d \n',k,{i in 1..cc+2} y[k,i]); Write{k}('Tour Load %d: %d <= %d\n',k,sum{i|x} dem[x[k,i]],CA); end end
Problem Statement
Modeling Description
Back to model
The solution is as follows:
The LOG-File output of LPL is as follows: