|
|
|
Angepasstes Travelling Salesman Problem |
|
| Kobe |
Forum-Newbie
|
 |
Beiträge: 2
|
|
|
|
Anmeldedatum: 10.12.08
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
 |
|
Verfasst am: 10.12.2008, 14:30
Titel: Angepasstes Travelling Salesman Problem
|
 |
| |
 |
 |
Hallo,
ich bin nach einiger Recherche auf dieses Forum gestoßen. Vielleicht könnt ihr mir bei meinem "Problem" weiterhelfen.
Mir wurde von Komilitonen gesagt, dass ich meine Aufgabenstellung damit einfach und schnell lösen kann.
Aufgabenstellung:
Eine Firma hat in einem Umkreis von x km eine bestimmte Anzahl von Kunden. Diese müssen von Angestellten an bestimmten Tagen in der Woche besucht werden (nicht jeder Kunde wird jeden Tag angefahren).
Vor Ort müssen dann Aufträge ausgeführt werden, die eine bestimmte Zeit in Anspruch nehmen. Es sind auch mehrere Aufträge für einen Kunden an einem Tag möglich.
Meine Aufgabe soll nun sein, die richtige Anzahl an Angestellten zu ermitteln die auf optimierten Touren (kürzeste Fahrzeit) die für den Tag vorgesehenen Kunden abfahren und dabei eine Gesamtarbeitszeit von 8h nicht überschreiten (Gesamtzeit = Fahrzeit plus Verweildauer beim Kunden).
Als Eingangsdaten habe ich Tabellen mit allen Fahrzeiten von Firma zum Kunden und von Kunde zu Kunde. Zusätzlich eine Tabelle mit den Zuordnungen, welcher Kunde an welchem Tag angefahren werden muss und die entsprechende Auftragsliste (Aufträge pro Kunde und Tag). Als Verweildauer kann eine Stunde als Durchschnittswert pro Auftrag angenommen werden.
Kann ich so etwas überhaupt mit Matlab lösen? Und wenn ja, wie gehe ich da am besten vor?
Vielen Dank.
Korbi
|
|
|
|
|
|
| Bijick |
Ehrenmitglied
|
|
Beiträge: 914
|
|
|
|
Anmeldedatum: 18.06.07
|
|
|
|
Wohnort: Nürnberg
|
|
|
|
Version: R2006b, R2008b
|
|
|
|
|
|
|
Verfasst am: 10.12.2008, 15:41
Titel:
|
|
Hallo Korbi,
das Travelling Salesman Problem ist ja ein Standardproblem in der Optimierung. Einfaches Googlen sollte Dir eine mathematische Problembescheibung als lineares Optimierungsproblem liefern. Dann muss nur noh Deine Variante für mehrere Fahrer modelliert werden (obwohl es auch das mit Sicherheit im Internet zuhauf gibt). Das mathematische Problem kannst Du dann, wenn Dir die Optimization Toolbox vorliegt, für eine nicht zu große Testinstanz leicht mit Matlab lösen.
Bei der Implementierung eines Verfahrens mit Programmcode oder mithilfe der Matlab-GUI optimtool bin ich gerne behilflich.
Herzliche Grüße
Bijick
_________________
>> why
|
|
|
|
| Kobe |
Themenstarter
Forum-Newbie
|
|
Beiträge: 2
|
|
|
|
Anmeldedatum: 10.12.08
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 11.12.2008, 10:50
Titel:
|
|
Hallo Bijick,
danke für deine schnelle Antwort.
Die allgemeine Definition, etc. vom TSP ist mir bekannt. Nur habe ich bisher nicht mit Matlab oder ähnlichen Solvern gearbeitet. So stellt mich alleine die Implementierung dieses Optimierungsproblems vor eine schwierige Aufgabe, von der Anpassung durch die spezielle Aufgabenstellung ganz zu schweigen.
Wenn möglich bräuchte ich hier eine einfache Heranführung an dieses Problem.
Viele Grüße
Korbi
|
|
|
|
| Bijick |
Ehrenmitglied
|
|
Beiträge: 914
|
|
|
|
Anmeldedatum: 18.06.07
|
|
|
|
Wohnort: Nürnberg
|
|
|
|
Version: R2006b, R2008b
|
|
|
|
|
|
|
Verfasst am: 11.12.2008, 14:35
Titel:
|
|
Hallo Korbi,
dann stell doch das mathematische Grundproblem mal auf, sodass wir entscheiden können, welcher Matlab-Solver dafür geeignet ist. Für die Auswahl kommt es auf die Art der Variablen (ganzzahlig oder kontinuierlich?), die Art der Zielfunktion (linear oder nichtlinear, Fehlerquadrate, minmax, univariat oder gar vektorwertig?) und die Nebenbedingungen (vorhanden oder nicht) an. Diese Fragen müssen beantwortet sein, bevor man sich an die Programmierung wagen kann.
Ist Dir denn im weiteren Verlauf ein flexibler Programmcode lieber oder die Arbeit mit dem einfach zu bedienenden optimtool?
Herzliche Grüße
Bijick
_________________
>> why
|
|
|
|
| samsa10 |
Forum-Fortgeschrittener
|
|
Beiträge: 50
|
|
|
|
Anmeldedatum: 10.12.08
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 11.12.2008, 14:49
Titel:
|
|
Hallo,
"in einem Umkreis von x km eine bestimmte Anzahl von Kunden"
Eine - wenn auch ungenaue - Angabe der Anzahl könnte darüber entscheiden, ob du "mathematisch exakt" oder mit heuristischen Verfahren rechnen musst. Bei den Heuristiken kenne ich mich nicht aus.. aber Bijick wird dir wohl weiterhelfen können.
Grüße
|
|
|
|
|
|
|
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
|
|
Impressum
| Nutzungsbedingungen
| Datenschutz
| FAQ
|  RSS
Hosted by:
Copyright © 2007 - 2024
goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks
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.
|
|
