Βοήθεια - Πρόβλημα Περιοδεύοντος Πωλητή - TSP

[Watt]

Καλησπέρα σας.

 

έχω μία εργασία με τίτλο "Ανάπτυξη προγράμματος Η/Υ για τον προγραμματισμό ενός πλεονεκτικού αλγορίθμου εισαγωγής πελατών (route insertion heuristic)". Κατά προτίμηση, ο αλγοριθμος πρέπει να γραφεί σε VBA ή σε ή σε Fortran. Έχει κανείς ασχοληθεί με κάτι παρόμοιο;

[chiossif]

Simulated annealing ή κάτι άλλο;

Γίνε σαφέστερος...

[Watt]

Η Λογική είναι η εξής: Έχω τις συντεταγμένες κάποιων πόλεων, από τις οποίες θα περάσει ο πωλητής. Παίρνω, έστω τις 2 πρώτες πόλεις στη λίστα και υπολογίζω την απόσταση όλων των υπόλοιπων πόλεων από τις δύο αυτές πόλεις, δημιουργείται δηλαδή κάθε φορά ένα τρίγωνο όπου η τρίτη κορυφή είναι η εκάστοτε πόλη. Η πόλη που απέχει λιγότερο από τις δύο άλλες μπαίνει ως τρίτη. Στη συνέχεια επαναλαμβάνεται η διαδικασία για τη δεύτερη και την τρίτη πόλη και ψάχνεται η τέταρτη και ούτω καθεξής. Για όλη αυτή τη διαδικασία πρέπει να γραφτεί ένας αλγόριθμος, αν όχι σε VBA έστω σε FORTRAN, Matlab, ή ότι άλλο. Είναι μία κλασσικη περίπτωση heuristic algorithm.

Υπάρχει κανείς να με διαφωτίσει;

[tarantules]

Βρήκα κάτι ενδιαφέρον σχετικά με τις μέλισσες και το πρόβλημα του περιοδεύοντος πωλητή που πιστεύω αξίζει να το διαβάσετε ενημερωτικά:

 

Οι μέλισσες κάνουν "μαθηματικούς" υπολογισμούς;

Οι μέλισσες είναι σε θέση να λύνουν πολύπλοκα μαθηματικά προβλήματα, τα οποία παίρνουν μέρες στους ηλεκτρονικούς υπολογιστές για να τα λύσουν, σύμφωνα με μια νέα βρετανική επιστημονική έρευνα, που έρχεται να αναδείξει μια ακόμη ικανότητα ενστικτώδους νοημοσύνης στο ζωικό βασίλειο.

 

Οι ερευνητές του πανεπιστημίου του Λονδίνου (Royal Holloway), υπό τον δρα Νάιτζελ Ρέιν της Σχολής Βιολογικών Επιστημών, δημοσίευσαν τη σχετική μελέτη στο αμερικανικό περιοδικό οικολογίας και βιολογίας "The American Naturalist", σύμφωνα με τις βρετανικές "Γκάρντιαν" και "Ιντεπέντεντ". Οι επιστήμονες διαπίστωσαν ότι οι μέλισσες μαθαίνουν να πετούν ακολουθώντας τη συντομότερη δυνατή διαδρομή ανάμεσα στα λουλούδια που έχουν προηγουμένως ανακαλύψει με τυχαία σειρά, με τον τρόπο αυτό ουσιαστικά "λύνοντας" το λεγόμενο "πρόβλημα του περιοδεύοντος πωλητή", ένα διάσημο και δισεπίλυτο γρίφο στον χώρο των οικονομικών και των μαθηματικών.

Στο πρόβλημα αυτό, ένας άνθρωπος (πωλητής) καλείται να βρει τη συντομότερη δυνατή διαδρομή ανάμεσα σε όλους τους προορισμούς που πρέπει να επισκεφτεί. Οι ηλεκτρονικοί υπολογιστές λύνουν το πρόβλημα συγκρίνοντας το μήκος όλων των πιθανών διαδρομών και επιλέγοντας τον πιο σύντομο. Όμως οι μέλισσες φαίνεται να κάνουν ουσιαστικά το ίδιο πράγμα κάθε μέρα, χωρίς καν τη βοήθεια κομπιούτερ, απλώς με ένα εγκέφαλο που δεν είναι μεγαλύτερος από ένα σπόρο φυτού.

Όπως είπαν οι επιστήμονες, καθημερινά οι μέλισσες ξεκινούν να επισκεφτούν μια πληθώρα λουλουδιών σε διάφορες τοποθεσίες και, επειδή θέλουν να κάνουν εξοικονόμηση ενέργειας για το πέταγμα τους, "υπολογίζουν" μια διαδρομή που τους επιτρέπει να βρίσκονται στον αέρα το ελάχιστο δυνατό χρονικό διάστημα.

Χρησιμοποιώντας τεχνητά άνθη, συνδεμένα με υπολογιστές, οι ερευνητές έδειξαν ότι οι μέλισσες δεν χαράζουν μια πορεία απλώς με βάση την τυχαία σειρά που βρήκαν προηγουμένως τα λουλούδια, αλλά πάνε από λουλούδι σε λουλούδι ακολουθώντας συγκεκριμένο "σχέδιο", που τους επιτρέπει να πετάνε όσο γίνεται λιγότερο. Αφού εντοπίσουν τις θέσεις των λουλουδιών, στη συνέχεια οι μέλισσες επιστρέφουν σε αυτά έχοντας μάθει -με μυστηριώδη τρόπο- να ακολουθούν πια τον καλύτερο δυνατό δρόμο, δηλαδή τον πιο σύντομο, ώστε να εξοικονομούν χρόνο και ενέργεια (ή χρήμα, όπως θα έλεγε ένας πωλητής!).

"Παρά τους μικροσκοπικούς εγκεφάλους τους, οι μέλισσες είναι ικανές για εντυπωσιακά κατορθώματα στη συμπεριφορά τους. Πρέπει να καταλάβουμε με ποιο τρόπο μπορούν να λύσουν το πρόβλημα του περιοδεύοντος πωλητή χωρίς κομπιούτερ", δήλωσε ο υπεύθυνος της έρευνας.

Οι επιστήμονες ευελπιστούν ότι μια τέτοια ανακάλυψη θα μπορούσε να βοηθήσει και τους ανθρώπους σε διάφορα πρακτικά προβλήματα, όπως στην καλύτερη ρύθμιση της κυκλοφορίας σε ένα δίκτυο (π.χ. κυκλοφοριακό) ή στην εκτεταμένη αλυσίδα τροφοδοσίας μιας επιχείρησης, που στέλνει φορτηγά σε όλα σημεία του ορίζοντα και θέλει να εξοικονομήσει χρόνο και χρήμα στις μετακινήσεις.

Link

[Dr.Fuzzy]

To πρόβλημα του περιοδεύοντος πωλητή μπορεί να λυθεί με διάφορους τρόπους (exact και heuristic). Έχω ασχοληθεί αρκετά με swarm intelligence ή search heuristic αλγορίθμους (ant colony optimization, bees algorithm, particle swarm optimizations, simulated annealing, genetic algorithms, κα) και αν αρχίσω να γράφω θα ξεφύγει το πράγμα, οπότε δες αρχικά εδώ μια σύγκριση.

 

https://louisville.edu/speed/faculty/sheragu/Research/Intelligent/tsp.PDF

 

By the way, αυτό που αναφέρει ο tarantules είναι άλλη μια παραλλαγή του Αnt Colony Optimization (όπου τα μυρμήγκια βρίσκουν τη συντομότερη διαδρομή από τη φωλιά στο φαγητό, πρακτικά μοντελοποιώντας μαθηματικά την εξάτμιση των φερομονών που αφήνουν στη διαδρομή τους) και ονομάζεται Βees algorithm.

 

Αν έχεις MATLAB πες μου να σου δώσω σε .exe ένα application με GUI που είχα φτιάξει και επιλύει το TSP με ACO.

[V.I.Smirnov]

Πολύ ενδιαφέρον πρόβλημα.

Όταν είχα ξεκινήσει να μαθαίνω C++ ήταν από τα πρώτα που έλυσα.

 

To πρόβλημα ΤSP μελετάται με κώδικα στο Numerical Recipes κεφ. 10.12.1 με τεχνική simulated annealing

η οποία είναι ευρετική (heuristic) μέθοδος - δηλ. αυτό που θέλεις.

Από εκεί είχα πάρει την ιδέα και είχα φτιάξει πρόγραμμα που το έλυνε.

Μάλιστα είχα γράψει και ένα σύντομο κείμενο στο οποίο εξηγούσα συνοπτικά την ιδέα του Numerical Recipes

με πιο απλό τρόπο και πώς την εφάρμοσα εγώ ώστε να θυμάμαι τι έχω κάνει αν το ξαναπιάσω.

Τα έχω αναρτήσει σε παλαιότερο thread αλλά για να μην ψάχνεις τα ξαναβάζω και εδώ.

 

Δεν θα σου δώσω έτοιμο τον κώδικα ακόμη (είναι το source σε Fortran για το exe που έβαλα) για να

ασχοληθείς και μόνος σου. Στo επισυναπτόμενο κείμενο περιγράφω πώς έχω φτιάξει το πρόγραμμα,

πώς λειτουργεί και κάνω μια πιο συστηματική δοκιμή για να δω πόσο καλή είναι η μέθοδος.

Θα πάρεις αρκετές ιδέες. Αν τα βρεις πολύ σκούρα πες μας.

 

(Παρεμπιπτόντως, το έχω λύσει και με νευρωνικά στη C++ αλλά αλλά εκεί δεν το κατέχω καλά το ζήτημα...)

 

-

το πρόβλημα TSP (doc).zip

travelling sallesman problem.zip