Nebenbedingung für Minimierungsmodell

Neue Frage »

Skip2MyLou44 Auf diesen Beitrag antworten »
Nebenbedingung für Minimierungsmodell
Meine Frage:
Hallo,

ich soll ein Modell aufstellen, bei dem für eine gebuchte Fahrt, das optimale Taxi gefunden wird. Dabei gibt der Kunde an, wie viele Sitzplätze er benötigt und das Modell soll nun das nächstgelegenste Taxi finden, unter der Bedingung, dass es groß genug ist.

In der Zielfunktion muss also die Distanz zwischen Fahrgast und Taxi minimiert werden. So jetzt will ich aber dafür sorgen, dass Taxis mit zu wenigen Sitzplätzen nicht mehr die optimale Lösung sein können, weil Sie zwar vielleicht am nähsten dran sind aber eben nicht die Kriterien für die Fahrt erfüllen.



Meine Ideen:
Meine erste Idee war eine Variable s(i) einzuführen unter der für jedes Taxi i die Anzahl der Sitzplätze hinterlegt ist. Dann wollte ich eine NB einführen wie s(i) >= s(g) wobei s(g) für die geforderte Taxigröße des Fahrgastes steht.

Jetzt sagte mir meine Dozentin, dass das nicht funktioniert, weil die Nebenbedingungen eines Modells immer erfüllt sein müssen. Hat jemand eine Idee, wie ich die zu kleinen Taxis sonst noch aus der Zielfunktion bekommen könnte?
Kasen75 Auf diesen Beitrag antworten »

Hallo,

ich weiß zwar nicht, wie genau deine Zielfunktion aussieht aber die Nebenbedingung könnte so aussehen:



Dabei ist

Die Restriktion ist nur bindend, wenn der anfordernde Gast g (und seine Mitfahrer) mit dem Taxi i fahren.

Grüße
Skip2MyLou44 Auf diesen Beitrag antworten »

Danke erstmal für die Hilfe. Ja, wie die Zielfunktion aussieht weiß ich ehrlich gesagt auch noch nicht genau. Die Aufgabe ist nämlich genau genommen noch etwas komplexer, ich wollte meine Fragestellung nur nicht unnötig ausweiten.

Aber ich kann dir ja mal die komplette Aufgabe geben, vielleicht hast du ja Lust dich mal auszuprobieren.

Und zwar soll ich ein möglichst realistisches Taximodell aufstellen. Ich habe mir überlegt man könnte so beginnen:

Es gibt t€T Taxistände und i€I Taxis, die sich beliebig auf die Taxistände verteilen und dort den Warteschlangenplatz w(t,i) € {0…unendlich/ bzw. Kapazität Taxistand} einnehmen, wobei null bedeutet, dass Sie sich nicht in der Warteschlange/am Taxistand i befinden. Außerdem haben die Taxifahrer die Möglichkeit ein Fahrtenangebot abzulehnen, was ich über die Variable a(i) abbilden möchte, welche zunächst den Wert 0 hat und mit 1 belegt wird, falls ein Fahrer eine Fahrt ablehnt.

Meine Idee für die ZF bisher: argmin(t,i) F = d(t,g) + M * a(i)

Ich will quasi erreichen, dass mir das optimale Taxi und der dazugehörige Taxistand ausgegeben werden, bei denen die Distanz zwischen dem Fahrgast g und dem nächsten Taxistand t minimal ist aber trotzdem alle Fahrgastwünsche erfüllt sind. M ist dabei eine hinreichend große Zahl, welche die Distanz explodieren lässt falls a(i) = 1 wird (also ein Fahrer die Fahrt nicht bedienen will).

Die die meisten anderen Eigenschaften lassen sich über das gleiche Prinzip abbilden, wie die Sitzplätze bei denen du mir bereits weitergeholfen hast.

Ich habe nur noch keine Idee, wie ich die Warteschlange einbeziehen soll...
Kasen75 Auf diesen Beitrag antworten »

Erst einmal eine grundsätzliche Frage bzw. Anmerkung.

Du willst doch, das ein Taxi bestellt wird ? Inwiefern haben die Taxistände damit zu tun ?
Die Taxen, an den Taxiständen, nehmen doch nur Fahrgäste am Stand auf.

Ich bin mir über deine Annahmen noch nicht im klaren. Geht es um ein Taxiunternehmen mit verschiedenen Taxen ?

Die Bedingungen müssten, meiner Meinung nach, klarer formuliert sein.
Skip2MyLou44 Auf diesen Beitrag antworten »

Also vielleicht erkläre ich dir mal die übliche Vorgehensweise (habe mich dahingehend beim Geschäftsführer der Dresdner Taxigenossenschaft informiert):

In Deutschland ist es so, dass über 95% der Taxiunternehmen einer Genossenschaft angehören. Also egal ob Einzelunternehmer oder Großunternehmen mit Taxiflotte...in der jeweiligen Stadt gehören Sie meist alle der selben Genossenschaft an. Nun gibt es zwar Laufkundschaft, die direkt zu Taxiständen geht und sich ein Taxi nimmt aber die nehmen dann einfach am jeweiligen Stand das Taxi, welches ganz vorn steht und fertig...da muss man nichts optimieren.

Der weitaus größere Anteil sind aber bestellte Fahrten und dort läuft es eben so ab wie ich beschrieben habe. Alle Taxifahrer, die der Genossenschaft angehören loggen sich am Taxistand ein, wenn sie dort ankommen (meist über ihr GPS Gerät) und das Fahrtenzuordnungsprogramm der Genossenschaft speichert den Standort. Bucht jemand eine Fahrt, sucht das Programm alle Taxistände im Umkreis von 3 km des Kunden ab und sortiert dort zunächst Taxis aus, die die gewünschten Anforderungen nicht erfüllen (Sitzplatzanzahl, etc.). Dann wird der nächstgelegenste Stand angewählt und dem Fahrer mit dem niedrigsten Warteschlangenplatz an diesem Stand die Fahrt vorgeschlagen. Dieser kann die Fahrt annehmen oder ablehnen. Lehnt er sie ab wird die Warteschlange weiter abgearbeitet (immer in Hinblick auf die Nebenbedingungen). Gibt es an diesem Stand keine passenden Taxis mehr, wird der zweitnächste Stand abgearbeitet. Wenn im 3km-Umkreis kein passendes Taxi gefunden wird, dann wird die Fahrt allen Fahrern im Stadtgebiet angeboten und der erste der zuschlägt bekommt sie.

Den letzten Teil, genau wie den 3 km Umkreis würde ich außen vorlassen. Zur Vereinfachung soll mein Modell einfach direkt alle Taxistände der Distanz nach absuchen.

Ich hoffe, dass war einigermaßen verständlich und hilft weiter.

EDIT: Der Quellcode von dem Programm wäre hilfreich, leider wollen die 3 Firmen, die ein solches Programm für Taxigenossenschaften anbieten nicht damit rausrücken ;-)
Kasen75 Auf diesen Beitrag antworten »

Ich versuche jetzt mal deine gegebenen Infos komprimiert darzustellen:

Variablen und Indizes:

d(t): Distanz zwischen Taxistand t und Fahrgast (Parameter)

i ist der Index für das einzelne Taxi i am Taxistand t.

Es gibt Taxis am Taxistand t.

Es gibt m Taxistände.

a(t,i) ist 1, wenn das Taxi i am Taxistand t die Fahrt für Fahrgast g potentiell annimmt. Sonst ist a(t,i) gleich 0.
Ich habe hier das jetzt mal 1 und 0 vertauscht.
a(t,i) ist sowohl Parameter als auch Variable. Wenn man es formal exakt formuliert, müsste man u.U. hier auch noch unterscheiden. Teilweise wird a(t,i) vor dem Start des Programms gleich 0 gesetzt und teilweise ergibt sich der Variablenwert aus der Optimierung.

Jeder Taxifahrer gibt also durch, ob er potentiell bereit ist die Fahrt anzunehmen. Auf jeden Fall gilt die Bedingung:
Es darf somit nur ein Taxifahrer die Taxifahrt endgültig annehmen.

Es gilt dann noch die Kapazitätsbeschränkung
Ich habe jetzt die Variable für den Gast (und seine Mitfahrer) weggelassen, da das Programm für jeden einzelnen Gast gestartet wird.

Es fehlt die noch die Zielfunktion. Diese summiert alle Distanzen zwischen den Taxis und dem Fahrgast auf, wobei die Variable bzw. der Parameter a(t,i) darüber entscheidet, ob die Distanzen gezählt werden.

Des Weiteren muss in der Zielfunktion noch berücksichtigt werden, dass mehrere Taxis pro Taxi die Kapazitätsbedingung erfüllen und potentiell bereit sind die Fahrt anzunehmen. Hier muss dann das Taxi ausgewählt werden, dass an vorderster Stelle steht. Bezeichnet i auch die Position des Taxis, dann kann man über die Minimierung auch das Taxi wählen, welches dann auch dran ist:


Je weiter vorne ein Taxi steht, um so geringer wird der Wert des Terms.

Ich habe jetzt deine Idee mit dem Parameter M verworfen, da ich gedanklich auf einer anderen Schiene war und da auch nicht mehr runter kam. Es ist sehr wahrscheinlich, dass es auch mit M funktioniert.
 
 
Skip2MyLou44 Auf diesen Beitrag antworten »

Danke dir erstmal für deine Bemühungen.

Also den Anfang habe ich genauso auf meinem Blatt Papier stehen. Für die Sache mit der Ablehnung von Fahrten finde ich deine Variante allerdings eleganter, als meinen Weg mit dem M.

Was jedoch noch immer ungeklärt bleibt, ist die Idee mit der Warteschlange. Ich habe schon verschiedene Dinge ausprobiert (u.a. auch deine Variante) und alle machen auch Sinn aber mir will die Verknüpfung mit der ZF nicht gelingen.

Nehmen wir doch dein Beispiel Wenn man diesen Term multiplikativ mit verknüpft, dann hätte man doch das Problem, dass ein Taxi das zwar am Stand mit der geringsten Entfernung zum Fahrgast ist aber Platz 3 in der Warteliste hat, die Distanz verdreifacht und somit einer schlechteren ZFW erzeugt, als ein Taxi mit i=1 beim zweitbesten (oder noch weiter entfernten) Taxistand. Additiv hätte man im Grunde das gleiche Problem...zumindest wenn die Entfernung in km angegeben wird. Platz 4 in der Warteschlange würde sich wie eine Verschlechterung der Distanz um 4 km auswirken.

Meine Überlegung: Man könnte die Distanz einfach in m angeben. Trifft man dann die Annahmen, dass die größten Taxistände höchstens 30-40 Taxis fassen und die Taxistände immer mindestens 100 voneinander entfernt sind, würde das bedeuten, dass ein Taxi mit i=40 die Distanz um 40 Meter erhöht und damit die schlechtere Lösung wäre als das Taxi am gleichen Stand mit i=3 (weil dieses dann quasi "näher" dran wäre). Gleichzeitig könnte ein weiter entfernter Taxistand nicht näher rücken als der aktuelle, weil die Distanz immer noch mindestens 60m (bei i=40) größer wäre. Das wäre so die einzige Idee, wie ich die Warteschlange verknüpfen könnte. Ist aber eben wieder nicht sonderlich elegant, weil zusätzliche Annahmen getroffen werden müssen.

Siehst du das auch so oder habe ich einen Denkfehler?
Skip2MyLou44 Auf diesen Beitrag antworten »

...meine ZF wäre jetzt quasi:
Kasen75 Auf diesen Beitrag antworten »

Wenn man noch zusätzlich zur Position noch die Distanz berücksichtigt, dann müsste das von Dir angesprochene Problem behoben sein.

Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »