Ich arbeite an einem Vehicle Routing Problem mit einem einzigen Depot. Die Problemdefinition ist wie folgt. Es gibt n vechiles, die zu m Anzahl der Aufstellungsorte reisen müssen. Jeder Standort hat seine spezifischen Beschränkungen, da nur Fahrzeuge mit bestimmter Kapazität den Standort bedienen können, einige Standorte müssen zu einer bestimmten Tageszeit bedient werden. Auch die Fahrzeuge haben unterschiedliche Kapazitäten und unterschiedliche Start- und Zielzeiten.Verwendung der Graphentheorie im Fahrzeug-Routing Problem
Die Idee ist, die Fahrzeit für die Fahrzeuge vom Depot zu minimieren.
Ich bin dabei, die Kostenmatrix für das Problem zu erstellen. Obwohl ich kein Experte in der Graphentheorie bin, weiß ich, dass ich den Hamilton-Zyklus verwenden könnte, um das Problem zu lösen, wenn es in ein klassisches Problem des reisenden Verkäufers fällt. Da es sich jedoch um ein Problem mit mehreren Vertriebsmitarbeitern handelt, möchte ich wissen, wie ich das Problem mithilfe von Hamilton-Zyklen lösen kann, oder ob es einen anderen Prozess gibt, der speziell darauf ausgelegt ist, Probleme als solche anzugehen.
Jede Hilfe würde sehr geschätzt werden.
Wie viele Fahrzeuge und Standorte haben Sie? Eine starke Heuristik könnte ein etwas doofes Backtracking ermöglichen. Ja, es ist NP-vollständig, und nur einige Teile können auf klügere Weise gelöst werden, wie einige Pfade, die mit Dijkstra gefunden wurden. –
Ich habe das Problem in Bits zerlegt. Der erste Teil entspricht den Baustellen mit Fahrzeugen mit der höchsten Kapazität/Fähigkeitsanforderung an den Standort, wonach alle anderen Standorte bis zur zulässigen Zeit für das Fahrzeug zu der Fahrzeugroute gehören. Dann finde ich aus dem erhaltenen Graphen den kürzesten Hamilton-Zyklus. Ich mache es in Iteration für alle verfügbaren Fahrzeuge, bis alle Standorte zugewiesen sind. Wie Sie vielleicht vermutet haben, ist die generierte Route nicht optimal. – Purusartha