ABSTRAK
Masalah perancangan rute optimal bus sekolah merupakan suatu permasalahan perancangan rute untuk bus sekolah dengan mengombinasikan pemilihan halte yang akan dikunjungi oleh bus serta perancangan rute yang akan dilalui oleh bus tersebut. Masalah ini bertujuan memilih sekumpulan halte bus yang akan dikunjungi untuk menjemput siswa dan untuk merancang rute yang akan dilalui oleh bus untuk mengantar siswa ke sekolah. Permasalahan ini mempertimbangkan beberapa kendala pada setiap rute seperti batasan jarak maksimal yang mampu dijangkau siswa, batasan banyaknya halte maksimal yang dikunjungi oleh bus sekolah, dan batasan minimum siswa yang dijemput pada satu kali perjalanan. Himpunan siswa dan himpunan halte bus bersesuaian dengan himpunan kolom pada model matematis masalah ini sehingga ketika siswa dan halte berjumlah relatif sangat banyak maka masalah ini melibatkan kolom yang banyak pula. Metode column generation merupakan suatu metode yang efisien untuk menyelesaikan masalah dengan jumlah kolom yang banyak tersebut. Masalah ini merupakan masalah pemrograman linier bilangan bulat. Jika masalah ini menghasilkan solusi yang bernilai pecahan maka masalah ini akan diselesaikan dengan menggunakan metode branch and price. Metode branch and price adalah gabungan dari metode branch and bound dan metode column generation.

---

ABSTRACT
School bus routing problem describes a bus routing problem that combines bus stop selection and bus route generation.This problem aims at selecting a set of bus stops from among a group of potential locations to pick up students and for designing bus routes to visit the selected stops and to carry the students to their school. This problem considers certain constraints on each bus route, such as bounds on the distances traveled by the sudents, bounds on the number of visited bus stops, and bounds on the minimum number of students that a bus has to pick up. A set of students and a set of bus stops associated to columns in the mathematical model of this problem so that when the number of student and the number of bus stop is getting bigger, this problem consists of a huge number of column. Column generation method is an efficient method to solve a problem with a huge size of column. The school bus routing problem is an integer linear programming problem. If the solution is a fraction then this problem is solved using branch and price. Branch and price method is a combination of branch and bound and column generation method.