ΘΕΜΑ IΙ Το πρόβλημα δρομολόγησης στόλου οχημάτων - VRP

Γενικά Βασικές έννοιες

Transportation Logistics

Τα logistics συνδέονται με την ανάπτυξη των πόλεων. Οι πόλεις δεν παράγουν αγαθά, άρα οι μεταφορές αναπτύσσονται στις πόλεις. Ενδεικτικά υπάρχουν 25 Mega cities (πόλεις με πληθυσμό άνω των 10 εκατομυρίων).

Η διακίνηση αγαθών περιγράφεται με δυο βασικά προβλήματα, το TSP -Travelling Salesman Problem- (το πρόβλημα του περιοδεύοντος πωλητή), και το VRP -Vehicle Routing Problem- (το πρόβλημα δρομολόγησης στόλου οχημάτων). Το TSP πρόβλημα είναι κυρίως θεωρητικό, είναι μαθηματικό και γεωμετρικό πρόβλημα. Αντίθετα το VRP πρόβλημα είναι ένα πρόβλημα το οποίο είναι κυρίως εμπορικό.

Μήτρα Κόστους

Ορισμός

Μήτρα κόστους Cij ορίζεται το nxn μητρώο που καταχωρείται το κόστος για την μετακίνηση από την πόλη i στην πόλη j.

Το κόστος είναι η απόσταση που χρειάζεται να διανύσει κάποιος για να πάει από την πόλη i στην πόλη j, αλλά γενικότερα το κόστος μπορεί να αναφέρεται στον απαιτούμενο χρόνο ή το οικονομικό κόστος ή ακόμη πιο γενικότερα την κατανάλωση πόρων για την μετακίνηση από την πόλη i στην πόλη j.

Το κόστος συνδέεται άμεσα με το objective function, δηλαδή το στόχο του προβλήματος που έχουμε να επιλύσουμε, μιας και ο στόχος μας είναι η ελαχιστοποίηση του κόστους.

Οδικά δίκτυα

Τα οδικά δίκτυα αναπαρίστανται με γράφους (graphs). Ένα δίκτυο έχει δυο βασικές οντότητες:
nodes - κόμβους
και
arcs - προσανατολισμένα τόξα ή edges - ακμές