Abstrak- Penelitian ini bertujuan untuk mengoptimalkan rute pengantaran makanan individu di daerah perkotaan khusunya di wilayah Medan Pancing menggunakan metode graf. Empat metode penyelesaian Traveling salesman Problem (TSP) yang diterpakan yaitu Nearest Neighbor, Cheapest Insertion heuristic, Two Way Exchange Improvement Heuristic dan Branch and Bound. Data jarak antar Lokasi dikumpulkan menggunakan Google Maps untuk enam titik pengantaran yang berbeda daerah. Hasil penelitian menunjukkan bahwa metode Branch and Bound menghasilkan rute terpendek dengan total jarak tempuh 11 km, diikuti oleh Cheapest Insertion Heuristic dan Two Way Exchange Improvement Heuristic dengan total jarak tempuh 12.2 Km serta Nearest neighbor dengan total jaral tempuh 13.7 Km. Penerapan graf ini berpotensi untuk meningkatkan efisiensi pengantaran, menghemat waktu dan mengurangi biaya operasional. Kata kunci : Optimasi rute, Metode Graf, Traveling Salesmen Problem(TSP), Catering Makanan Individu Abstract - This research aims to optimize individual food delivery routes in urban areas, especially in the Medan Pancing are using the graph method. Four methods of solving the Travelling Salesman Problem (TSP) are apllied, namely Nearest Neighbor, Cheapest insertion heuristic, Two Way Exchange Improvement Heuristic and Brancj and Bound. Distance between locations was collected using Google Maps for six delivery points in different regions. The results showed that the Brach and Bound method produced the shortest route with a total distance 11 Km, followed by Cheapest Insertion Heuristic and Two Way Exchange Improvement Heuristic with a total distance 12.2 Km and Nearest Neighbor with a total distamce of 13.7 Km. The application of this graph has the potential to improve delivery efficiency, save time and reduce operational costs. Keywords: Route optimization, Graph Method, Traveling Salesman Problem (TSP), Individual Food Catering