Permasalahan optimalisasi jaringan merupakan permasalahan yang sering kita jumpai dalam aktifitas sehari-hari antara lain transportasi udara, darat, laut, rute perjalan bus, rute antar surat (pos) seta banyak lagi kasus lainnya. Proses pedagang keliling dari sebuah kota ke kota berikutnya merupakan bentuk dari optimalisasi biaya, waktu yang ditempuh sehingga proses tersebut dapat meminimalkan biaya dan waktu perjalanan. Travelling Salesman Problem (TSP) merupakan suatu masalah optimasi untuk menentukan jarak terpendek dalam sebuah rute perjalanan yang mana dalam tiap kota hanya dapat dilewati tepat satu kali dalam satu kali perjalanan dan kemudian kembali ke kota awal dimana sales tersebut memulai perjalanannya. Pada penelitian ini hibridisasi local dengan population based search diusulkan untuk meminimalkan kesamaan individu dalam populasi pada setiap generasi serta menganalisis kelebihan dari masing-masing metode sebelum dan sesudah hibridisasi. Hasil dari algoritma yang diusulkan tercipta variasi yang lebih banyak. Sehingga search space lebih ter eksplose dan eksploitasi dan hasil yang didapat lebih baik. Kata Kunci- Algoritma Evolusi, Simulated Annealing, Pencarian Lokal, Hibridisasi LBS dengan PBS.