Kartoffel-transport - optimering

By logistikekspert, 2 July, 2011

Forums

Kartoffeltransport optimeret via matematisk model lavet til landbrug og fabrikker.
_______ ___
|ooooooo|_|__\
|ooooooo|_____||
()) ()) ())

Grzegorz Nowak 2011-07-02.

Modellen er lavet i GLPK.

Det antages at "v" vogne med kapaciteten "k" henter kartofler hos "n" antal landbrugsbedrifter og afleverer derefter kartoflerne på en fabrik med en daglig efterspørgsel på "e". Der kan angives en straffaktor "f1", hvis man forsøger at optimere efter, at så få bedrifter besøges af gangen. Der er en kartoffellæsser, som skal flyttes til den bedrift, hvor kartoflerne hentes.

Det er nødvendigt at angive en række parametre, så modellen har nogle data arbejde med.

Parameteren "a" angiver alle afstande fra fabrikken til bedrifterne.

Parameteren "l" angiver kartoffellagerniveauet på hver bedrift.

"q" angiver kartoflernes kvalitet og kan have en værdi fra 1 til 5. Med kvalitet menes holdbarheden, hvor 1 er friske kartofler mens 5 er kartofler, som hurtigst muligt skal afhentes, for ellers bliver de dårlige.

"c" er afstanden mellem bedrifterne.

Denne model kan sandsynligvis anvendes til andre afgrøder og andre problemstillinger, hvor en bestemt mængde af et produkt skal hentes ved forskellige geografiske positioner og afleveres på en bestemt geografisk position.

Samtlige modelfiler og resultater er vedhæftede og vist herunder

Modelkode (Indtransport-af-kartofler_dev-grn.dk.mod) kan afvikles via (go.bash bash skript i Linux eller med bash installeret på Windows eller en anden platform)

go.bash

glpsol -o output.txt -m Indtransport-af-kartofler_dev-grn.dk.mod

Indtransport-af-kartofler_dev-grn.dk.mod

# Parametre
param v := 1, integer >= 1;    #antal tilgængelige vogne.
param n := 3, integer >= 1;    #antal bedrifter.
param e := 500, integer >= 0; #efterspørgslen efter kartofler på fabrikken.
param k := 25, integer >= 1;   #vognkapaciteten, antages at være homogen.
param f1:= 0, integer >=0;        #faktor 1, der angiver straffen ved besøg af flere bedrifter (kun til demo).
param ls:= 2, integer >=0;       #Læsserens startbedrift.
#param f1:= 23000, integer >=0;    #faktor 1, der angiver straffen ved besøg af flere bedrifter (kun til demo).

#Sæt
set V := 1..v; #vognsættet.
set B := 1..n; #bedriftsættet.

#Parametre fortsat
param a {i in B}, integer >= 1; #afstand fra fabrik til hver bedrift (angives i dataafsnittet).
param l {i in B}, integer >= 0; #lagerstatus for hver bedrift (det er et lille L ikke et et-tal) - (angives i dataafsnittet).
param q {i in B}, integer >= 1, <=5; #kartoffelkvaliteten på hver bedrift (angives i dataafsnittet i værdier fra 1 til 5).
param c {i in B, j in B}, integer, >=0; #Afstand mellem bedrifterne
#Variable
#
#var b {i in B, j in V}, binary; #1 hvis bedrift i besøges af vogn j ellers 0. Fravalgt.. keep it simple..

var b {i in B}, binary;            #1 hvis bedrift i besøges ellers 0.
var x {i in B}, integer, >=0; #Kartoffelmængde i ton leveret fra bedrift i.
var m {i in B, j in B}, binary; #1 hvis kartoffellæsser transporteres fra bedrift i til bedrift j

#Objektfunktion maksimeringsproblem.
maximize objekt: sum{i in B} (x[i]*q[i] + x[i]*a[i] - b[i]*f1) - sum{i in B, j in B} m[i,j]*c[i,j]; #Det foretrækkes at afhente kartofler med dårlig kvalitet, der er langt væk. Der forsøges at besøge så få bedrifter på en gang (b[i]*f1) samme dag. Kartoffellæsserens afstand minimeres - sum{i in B, j in B} m[i,j]*c[i,j]

#Test objektfunktioner
#maximize objekt: - sum{i in B, j in B} m[i,j]*c[i,j]; #Kun afstand af kartoffellæssertransport.
#maximize objekt: sum{i in B} x[i]*q[i]; #kun kvalitet i forhold til mængden

#Bonusting der kan implementeres.
#Prioriter bedrifter med stor lagerbeholdning?
#Bonus, hvis lageret tømmes på bedriften?
#Straf, hvis der ikke kan køres med hele læs.
#Straf, hvis en lille rest efterlades?

#Begrænsninger

#Angivelse af, om bedrift i besøges.
s.t. bedrift_besoeg {i in B}: x[i] <= 9999*b[i];

#Summen af leverede kartofler, skal svare til efterspørgslen på fabrikken.
s.t. lev_eft: sum {i in B} x[i] = e;

#Der kan ikke leveres flere kartofler end lagerstatus på bedriften.
s.t. maks_lev {i in B}: x[i] <= l[i];

#rutelægning af kartoffellæsser
s.t. antal_ture: sum {i in B} b[i] - 1 = sum {i in B, j in B} m[i, j]; #Der skal kun køres n-1 ture hvis n bedrifter besøges.

#Kør kun mellem bedrifter der er besøges.
s.t. kun_besoegte {i in B, j in B}: m[i, j] <= b[i];

#Der køres ikke fra og til samme bedrift.
s.t. ikke_fra_til_samme {i in B, j in B}: m[i, j] + m[j, i] <=1;

#Der køres ikke til samme bedrift mere end én gang.
s.t. kun_en_gang_til {j in B}: sum {i in B} m[i, j] <= 1;
#Der køres ikke fra samme bedrift mere end én gang.
s.t. kun_en_gang_fra {j in B}: sum {i in B} m[j, i] <= 1;

#Læsserens startbedrift.
s.t. laesser_start_01: sum {i in B} m[ls, i] = 1;
s.t. laesser_start_02: sum {i in B} m[i, ls] = 0;

solve; #løs problemet.

printf " _______ ___ \n|ooooooo|_|__\\ \n|ooooooo|____|| \n ()) ()) ())\n";

data; #Dataafsnittet kan lægges i en selvstændig datafil.

#Afstand fra bedrift til fabrik for alle bedrifter.
param a:=
1   75
2   45
3   25;

#Eventuelt anden syntaks: param a := 1 75, 2 45, 3 25;

#Afstand mellem bedrifterne (symmetrisk afstandsmatrice)
param c:
   1   2   3:=
1   50000 45 100
2   45 50000 65
3   100 65 50000;

param l:= 1 200, 2 150, 3 200; #Lagerstatus for alle bedrifter.

param q:= 1 3, 2 5, 3 2; #kartoffelkvalitet for alle bedrifter.

end;

output-fra-kartoffelmodellen-linear-programming.txt

I ovenstående tilfælde er det optimale resultat, hvis vognen henter 200 ton kartofler fra bedrift 1 og 150 ton kartofler fra bedrift 2 og 3.

Problem: Indtransport
Rows: 35
Columns: 15 (15 integer, 12 binary)
Non-zeros: 93
Status: INTEGER OPTIMAL
Objective: objekt = 27005 (MAXimum)

No. Row name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 objekt 27005
2 bedrift_besoeg[1]
-9799 -0
3 bedrift_besoeg[2]
-9849 -0
4 bedrift_besoeg[3]
-9849 -0
5 lev_eft 500 500 =
6 maks_lev[1] 200 200
7 maks_lev[2] 150 150
8 maks_lev[3] 150 200
9 antal_ture 1 1 =
10 kun_besoegte[1,1]
-1 -0
11 kun_besoegte[1,2]
-1 -0
12 kun_besoegte[1,3]
0 -0
13 kun_besoegte[2,1]
0 -0
14 kun_besoegte[2,2]
-1 -0
15 kun_besoegte[2,3]
-1 -0
16 kun_besoegte[3,1]
-1 -0
17 kun_besoegte[3,2]
-1 -0
18 kun_besoegte[3,3]
-1 -0
19 ikke_fra_til_samme[1,1]
0 1
20 ikke_fra_til_samme[1,2]
1 1
21 ikke_fra_til_samme[1,3]
1 1
22 ikke_fra_til_samme[2,1]
1 1
23 ikke_fra_til_samme[2,2]
0 1
24 ikke_fra_til_samme[2,3]
0 1
25 ikke_fra_til_samme[3,1]
1 1
26 ikke_fra_til_samme[3,2]
0 1
27 ikke_fra_til_samme[3,3]
0 1
28 kun_en_gang_til[1]
1 1
29 kun_en_gang_til[2]
0 1
30 kun_en_gang_til[3]
1 1
31 kun_en_gang_fra[1]
1 1
32 kun_en_gang_fra[2]
1 1
33 kun_en_gang_fra[3]
0 1
34 laesser_start_01
1 1 =
35 laesser_start_02
0 -0 =

No. Column name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 b[1] * 1 0 1
2 b[2] * 1 0 1
3 b[3] * 1 0 1
4 x[1] * 200 0
5 x[2] * 150 0
6 x[3] * 150 0
7 m[1,1] * 0 0 1
8 m[1,2] * 0 0 1
9 m[1,3] * 1 0 1
10 m[2,1] * 1 0 1
11 m[2,2] * 0 0 1
12 m[2,3] * 0 0 1
13 m[3,1] * 0 0 1
14 m[3,2] * 0 0 1
15 m[3,3] * 0 0 1

Integer feasibility conditions:

KKT.PE: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality

KKT.PB: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality

End of output

Attachments

indtransport-af-kartofler_dev-grn.dk_.mod (5.11 KB)

output-fra-kartoffelmodellen-linear-programming.txt (4.64 KB)

go.bash (66 bytes)