Vehicle Routing Problem < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hi!
Ich schreibe gerade meine Diplomarbeit über Tourenplanung und bin gerade dabei mein konkretes Problem mathematisch zu formulieren. Allerdings habe ich dabei ein Problem:
es sind auf einer Tour mehrere Kunden i aus einer Gesamtmenge n von verschiedenen Fahrzeugen k zu beliefern. Bestellt ein Kunde mehr als 250 kg wird ihm ein eigener Stellplatz zugewiesen. Bestellt er weniger, werden bis zu 4 Kunden auf einen Stellplatz zusammengefasst, Gesamtgewicht 250kg. Übersteigt die Bestellmenge 500kg bzw. 1000 kg (anderes Produkt) muss dem Kunden mehr als ein Stellplatz zugeteilt werden. Insgesamt sind
pro Fahrzeug k nur 17 Stellplätze vorhanden.
Die Bestellmengen sind also den Fahrzeugen k zuzuordnen unter Einhaltung der genannten Bedingungen.
Ich habe an die Einführung einer Variablen gedacht, die den Wert 1 annimmt, falls Bestellung größer als 250kg und den Wert 250kg/Bestellmenge annimmt falls Bestellung kleiner als 250 kg ist. Die Summe der Variable muss kleiner gleich 17 sein für alle k.
Allerdings hab ich noch Probleme, den Sachverhalt darzustellen, dass nicht mehr als vier Kunden auf einen Stellplatz dürfen. Außerdem muss ich noch die beiden Bedingungen hinzufügen, falls Bestellung größer als 500 bzw 1000kg. Ich möchte hier nicht nach Produkten unterscheiden!
Ich habe im Anhang zwei Formeln angehängt!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt!
Viele Grüße
Kikolino
Dateianhänge:
Anhang Nr. 1 (Typ: docx) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:36 Do 03.04.2008 | | Autor: | DaMenge |
Hi,
darfst du überhaupt nach Hilfe für deine Diplomarbeit fragen - musst du nicht irgendwann eine eidesstattliche Erklärung abliefern, dass du alles selbst gemacht hast oder die Quellen vollständig angibst.
Willst du wirklich auf ein Matheforum in deiner DA referenzieren oder riskieren, dass deine Note nachträglich aberkannt wird, wenn es jemand herausfindet?
Ich kenn mich leider nicht so genau aus, was denn erlaubt ist und was nicht - vielleicht solltest du aber deine Fragen eher allgemeiner halten, also nicht speziell für dein Problem formulieren...
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:56 Fr 04.04.2008 | | Autor: | kikolino |
Hi,
also ehrlich gesagt habe ich mir darüber gar keine Gedanken gemacht. Ich möchte auch gar keine Hilfe in dem Sinne, dass mir jemand meine Diplomarbeit löst und ich dann die fertige Arbeit abgebe! Das ist ja nur ein winziger Teil vom Ganzen über den ich diskutieren wollte, um mir einen Denkanstoß zu geben. Ich habe mir ja schon selbst Gedanken gemacht und diese dargestellt, ich denke nicht, dass es verboten sein kann über etwas zu diskutieren und sich hier und da Tipps geben zu lassen. So gesehen dürfte ich auch meinen Betreuer nicht um Rat fragen, obwohl das ja seine Aufgabe ist.
Außerdem bin ich auf das Forum aufmerksam geworden, weil eine Benutzerin ebenfalls bezüglich ihrer Diplomarbeit eine Frage gestellt hat. Aus all diesen Gründen, dass das eine Verletzung der eidesstattlichen Erklärung ist.Wenn ihr anderer Meinung seid, könnt ihr meinen Beitrag gerne löschen.
Gruß Kikolino
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:38 Fr 04.04.2008 | | Autor: | VNV_Tommy |
Hallo Kikolino,
> So gesehen dürfte ich auch
> meinen Betreuer nicht um Rat fragen, obwohl das ja seine
> Aufgabe ist.
Um Rat fragen darfst du ihn schon, dann solltest du ihm aber auch einen Lösungsansatz präsentieren können, damit er diesen bewerten kann und dich auf den richtigen Weg geleitet.
Soweit ich das hier ersehen kann stellst du jedoch nur das Problem dar, lieferst allerdings keinen Ansatz zur Lösung. Sollte im Rahmen dieses Forums ein für dich verwertbarer Ansatz zu Stande kommen, dann wärest du zur Zitation dieses Forums gezwungen, da du dir fremdes Wissen zur Lösung deines Problems zu Nutze machst.
Welches Wissen du in deiner DA verarbeitest ist im Grunde egal, du musst nur auf die entsprechende(n) Quelle(n) hinweisen.
Viele Grüße,
Tommy
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:51 Fr 04.04.2008 | | Autor: | bazzzty |
Mir ist noch nicht so ganz klar, was Du suchst.
Du hast n Kunden, die jeweils etwas bestellen. Jetzt willst Du die Bestellungen auf k Fahrzeuge verteilen. Jedes Fahrzeug hat 17 Stellplätze. Es können bis zu vier Bestellungen von unter 250kg auf einem Stellplatz gesammelt werden. Bestellungen über 250kg sollen einen einzelnen Stellplatz einnehmen, Bestellungen über 500kg bzw. 1000kg benötigen mehr als einen Stellplatz.
Ist das soweit richtig? Dann wäre das Problem leicht zu lösen, wenn es keine Bestellungen über 500kg gäbe. Sehe ich das richtig?
Wenn Du jetzt eine mathematische Beschreibung suchst, dann nehme ich an, daß Du eine Formulierung als (Mixed-Integer-)Lineares Programm oder ähnliches brauchst? Was für eine BEschreibung schwebt Dir vor?
Deinen Anhang kann ich leider nicht öffnen. Ich vermute, daß das irgendein Word 200x-Format ist. Hast Du das vielleicht auch in einem Format, das jeder öffnen kann?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:08 Fr 04.04.2008 | | Autor: | kikolino |
Hi,
ja du hast das Problem soweit richtig verstanden! Es gibt zwei verschiedene Produkte, die bestellt werden können. Wenn jeweils eine ganze Palette bestellt wird, dann beträgt das Gewicht beim einen Produkt 500kg und beim anderen 1000kg. Es könnte natürlich auch sein, dass ein Kunde z. B. 2000kg bestellt, also je nach Produkt 4 bzw. Paletten/Stellplätze.
Ich möchte ein Modell mit linearer Programmierung aufstellen, später soll dies dann noch in ein Computerprogramm implementiert werden.
Ich habe die Datei nochmals als pdf angehängt und überarbeitet!
Ist eine solche vierfach Fallunterscheidung ratstam oder macht es das Ganze zu komplex, auch im Bezug auf die Umsetzung im Programm? Mein Problem besteht noch in der Darstellung der Obergrenze von jeweils vier Kunden auf einen Stellplatz, muss ich da ne Hilfsvariable einführen?
Beste Grüße
Kikolino
Dateianhänge:
Anhang Nr. 1 (Typ: pdf) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:04 Mo 07.04.2008 | | Autor: | bazzzty |
Hi kikolino,
was ich nicht verstehe: Wenn die Regeln so einfach sind, wie ich sie beschrieb, warum dann noch reellwertige Belegungen?
Sowit ich das verstanden habe, kann man jeder Bestellung eine PLatzzahl zuweisen: 1/4 für kleine Bestellungen <250kg, 1 für Bestellungen ab 250kg bis zur Grenze von 500/1000 kg. und sonst entsprechend der Größe 2,3,4...
Wenn Du diese Werte statt der Kilogramm-Werte als Eingabe behandelst, dann sollten sich die zulässigen Beladungen einfacher ausdrücken lassen: Ist die Summe der Platztzahlen kleiner gleich 17, dann läßt sich alles entsprechend packen. Habe ich etwas außer acht gelassen?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:00 Mo 07.04.2008 | | Autor: | kikolino |
Hi bazzty,
danke für die Antwort. Du hast Recht ich könnte den Kilogrammwerten Platzzahlen zuweißen, allerdings muss ich auch noch die maximale Tonnage pro Lkw einhalten, die in kg gegeben ist, d. h. ich brauch zum Einen die Summe aus den Kilogrammwerten, die kleiner gleich eines bestimmten Wertes sein muss und die Summe aus den Platzhaltern, die kleiner gleich 17 sein muss.
Allerdings sind Bestellungen <250 kg nicht automatisch gleich 1/4, sie sind beispielsweise gleich 1/2, wenn 2 Bestellungen zu 125 kg vorliegen! Es muss also gewährleistet sein, dass die Bestellungen kleiner als 250 kg auf einen Stellplatz zusammengefasst werden bis entweder 250 kg erreicht sind oder bis zu vier Kunden auf einem Stellplatz sind! Hast du mein Anliegen jetzt verstanden?
Viele Grüße
Kikolino
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 06:55 Di 08.04.2008 | | Autor: | bazzzty |
> Hi bazzty,
> danke für die Antwort. Du hast Recht ich könnte den
> Kilogrammwerten Platzzahlen zuweißen, allerdings muss ich
> auch noch die maximale Tonnage pro Lkw einhalten, die in kg
> gegeben ist, d. h. ich brauch zum Einen die Summe aus den
> Kilogrammwerten, die kleiner gleich eines bestimmten Wertes
> sein muss und die Summe aus den Platzhaltern, die kleiner
> gleich 17 sein muss.
> Allerdings sind Bestellungen <250 kg nicht automatisch
> gleich 1/4, sie sind beispielsweise gleich 1/2, wenn 2
> Bestellungen zu 125 kg vorliegen!
Genau das würde doch passieren: Beide Bestellungen würden mit 1/4 gewichtet, und zusammen wär's dann 1/2. Da es nur ganzzahlige Gewichte und 1/4 gibt, werden die "leichten" Besteullungen automatisch zusammengefaßt, wenn Du als Variable nur den Truck, nicht aber den Stellplatz modellierst.
> Es muss also
> gewährleistet sein, dass die Bestellungen kleiner als 250
> kg auf einen Stellplatz zusammengefasst werden bis entweder
> 250 kg erreicht sind oder bis zu vier Kunden auf einem
> Stellplatz sind! Hast du mein Anliegen jetzt verstanden?
Ich bin mir nicht sicher. Meine Vorstellung wäre: jede Bestellung wird modelliert als ein Volumen (1/4,1,2,...) und ein echtes Gewicht. Das Programm enthält dann Variablen, die zu jeder Bestellung einen Truck angeben. Nebenbedingung: Die Volumina dürfen in der Summe 17 nicht übersteigen, die Gewichte in der Summe nicht die zulässige Last.
Wenn Du jetzt eine Lösung hast, dann mußt Du nur die Bestellungen mit Volumina 1/4 beliebig in Vierergruppen gruppieren. Wenn daran etwas nicht stimmt: Was habe ich nicht verstanden?
>
> Viele Grüße
> Kikolino
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:22 Mo 07.04.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
