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