Πλανόδιοι πωλητές, ταχυδρόμοι και μυρμήγκια.

Ένα από τα πιο διάσημα προβλήματα των μαθηματικών, αλλά και της πληροφορικής, είναι το πρόβλημα του πλανόδιου πωλητή:

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

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

Travelling salesman movie

Όπως θα δείτε και στο παραπάνω άρθρο το πρόβλημα του πλανόδιου πωλητή είναι τρομερά δύσκολο να επιλυθεί με τις ως τώρα υπάρχουσες μεθόδους. Ένας υπάλληλος της UPS με 25 πακέτα προς παράδοση έχει 15 τρισεκατομμύρια διαδρομές! Το πρόβλημα αυτό ανήκει σε μια κατηγορία προβλημάτων, τα λεγόμενα πλήρη NP προβλήματα, για τα οποία εικάζεται ότι δεν υπάρχει "γρήγορος" αλγόριθμος που να τα επιλύει. Η εικασία αυτή είναι μια από τις πιο διάσημες εικασίες των μαθηματικών και ίσως η πιο διάσημη εικασία της πληροφορικής. Είναι δε επικυρηγμένη για 1 εκατομμύριο δολάρια από το Clay math institute! Επίσης, υπάρχει και μια ταινία με το τίτλο "Travelling salesman" η οποία διηγείται την ιστορία μιας ομάδας μαθηματικών που έχει προσλάβει η αμερικανική κυβέρνηση για να λύσουν το πρόβλημα αυτό.

Για να δείτε την πρακτική σημασία που έχει η επίλυση του προβλήματος του πλανόδιου πωλητή παρατηρήστε ότι αν κάθε υπάλληλος της UPS κάνει ένα παραπάνω μίλι κάθε μέρα, τότε το συνολικό της κόστος είναι 30 εκατομμύρια δολάρια το χρόνο. Συνεπώς, έχουν αναπτυχθεί πολλές μέθοδοι που προσπαθούν να δώσουν μια ικανοποιητική απάντηση στο πρόβλημα του πλανόδιου πωλητή.

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

Υ.Γ. Και μια ερώτηση. Άραγε στην Ελλάδα υπάρχει κάποιος (δημόσιος οργανισμός, ιδιωτική εταιρεία ή άλλος) που να ασχολείται με το πρόβλημα της εύρεσης της μικρότερης διαδρομής; για παράδειγμα, τα ΕΛΤΑ και τα συνεργεία καθαριότητας κάθε δήμου θα είχαν άμεσα οφέλη από την ελαχιστοποίηση των διαδρομών που κάνουν. Φοβάμαι, όμως, ότι στη χώρα είναι η εφαρμογή των μεθόδων μαθηματικής βελτιστοποίησης απέχει έτη φωτός. Κι ας διδάσκεται στα ελληνικά πανεπιστήμια εδώ και δεκαετίες...

Παραπομπές:

1. Το άρθρο του περιοδικού wired  για τη UPS.
2. Η σελίδα της wikipedia  για το πρόβλημα του πλανόδιου πωλητή (στα αγγλικά). Εκεί θα βρείτε και παραπομπή στη μέθοδο επίλυσης του με την αποικία μυρμηγκιών.
3. Η επίσημη σελίδα της ταινίας "Travelling salesman".