ich habe ein Skript mit einem Fahrplan geschrieben. Meine Fahrzeuge fahren immer zum Zeitpunkt 0, 20, 40, 60, 80 usw. los. Jede Lieferung hat ein Zeitfenster von 30 Minuten und muss zwischen den Zeitpunkten START und ENDE durchgeführt werden. Es sollen möglichst viele Lieferungen durchgeführt werden, eine Lieferung soll aber nicht mehrfach erfolgen. Jedes Fahrzeug darf pro Tour maximal 3 Lieferungen machen. Ermittelt wird das durch eine Matrix von 24 * 24 Feldern für die 24 Lieferungen und 24 Touren, die gefahren werden. Eine 1 bedeutet, dass die Lieferung auf der Tour erledigt wird, eine 0 bedeutet, dass diese ausgelassen wird. Es gibt 4 Nebenbedingungen, die ich abbilde:
Frühester Zeitpunkt zur Anlieferung mal 1/0 (ausgeführ oder nicht) <= Startzeit + Wegzeit
Startzeit plus Wegzeut * 1/0 <= spätester Anlieferzeitpunkt
Spaltensumme der Matrix <= 1
Zeilensumme der Matrix <= 3
% Zielfunktion f = (- 1,- 1, - 1, - 1, - 1...)
f = - ones(1, 576);
% Aufnahme der Begrenzungen:
tpluss = zeros(576);
% 1. Früheste Lieferzeit
start = [14154105120165180180195206207240285285315352381390390405405435435450];
% 2. Zeitfenster für die Lieferung = 30 Minuten
ende = start + 30;
% 3. Die Dauer des Fahrtweges wird berücksichtigt
s = [99911612115119951151199691185511];
% 4. Dauer des Fahrtweges plus Anfahrt (t_i = 0, 20, 40...) entspricht % Ankunftszeit in [min] for i = 1 : 24 for j = 1 : 24
tpluss((i - 1) * 24 + j) = 20 * (j-1) + s(i);
end end
% Koeffizienten für Nebenbedingungen (A)
A = zeros(1200, 576);
for i = 1 : 24 for j = 1 : 24 % Nebenbedingung 1: A_j * a <= t + s
A((i-1) * 24 + j, (i-1) * 24 + j) = start(i);
% Nebenbedingung 2: (t + s)* a <= Z_j
A((i-1) * 24 + j + 576, (i-1) * 24 + j) = tpluss(i);
% Nebenbedingung 3: Spaltensumme <= 1
A((i-1) + 1153, (i - 1) * 24 + 1 : i * 24) = 1;
% Nebenbedingung 4: Zeilensumme <= 3
A((i-1) + 1177, (j-1)*24 + i) = 1;
end end
% Rechte Seite der Nebenbedingungen (b) for i = 1:576 % Nebenbedingung 1: A_j * a <= t + s
b(i) = tpluss(i);
end for i = 1:24 % Nebenbedingung 2: (t + s)* a <= Z_j
b((i - 1) * 24 + 577 : i * 24 + 577) = ende(i);
end for i = 1:24 % Nebenbedingung 3 + 4: Spaltensumme <= 1, Zeilensumme <= 3
b(i + 1152) = 1;
b(i + 1176) = 3;
end
% Berechnung und Ausgabe
erg = bintprog(f, A, b);
for i = 1:24
ausg(1:24, i) = erg((i-1)*24+1:(i-1)*24+24);
end
ausg
Jetzt hat er heute Nacht zwei Stunden daran gerechnet, dann behauptet, die options.MaxTime oder so sei erreicht und abgebrochen. Als Ergebnis hat er mir eine Matrix mit 24 * 24 Nullen ausgespuckt, die mir nicht wirklich weitergeholfen hat. Ich hatte vorher in der START-Variable versehentlich zu niedrige Werte (alle zweistellig), damals hat die Berechnung unter 100 Sekunden gedauert. Natürlich sehe ich ein, dass es jetzt etwas anspruchsvoller ist, aber das ist wirklich zu viel Rechenzeit.
Ein Mensch kann das Problem innerhalb von 5 Minuten lösen (natürlich nicht mit linearer Optimierung, sondern mit gesundem Menschenverstand) und einfaches "Durchprobieren" aller 2^576 Kombinationen, bis eine gültige mit f = 24 (erwiesenermaßen der Maximalwert) gefunden ist, ist vermutlich auch noch flotter! Es geht mir aber darum, dass das Skript da oben funktionieren soll und nicht, dass die Lösung gefunden wird! Könnt Ihr mir in irgendeiner Weise helfen? Wie kann ich die Rechenzeit senken? Habe ich einen Fehler gemacht? Im schlimmsten Fall: Wie erhöhe ich dieses options.Maxtime?
Kudzu
Einstellungen und Berechtigungen
Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
RSS