Tingginya penggunaan kendaraan pribadi yang diakibatkan kurang memadainya layanan angkutan umum di Indonesia, merupakan salah satu faktor utama penyebab kemacetan. Salah satu cara untuk mengatasi permasalahan tersebut yaitu penggunaan sistem ridesharing. Sistem Ridesharing dapat mengurangi jumlah penggunaan kendaraan pribadi sehingga dapat mengurangi kemacetan. Masalah yang dihadapi pada sistem ridesharing ini adalah memasangkan (matching problem) antara pengemudi (driver) dengan penumpang (rider). Mean shift clustering akan digunakan sebagai langkah awal dalam mengoptimalkan matching problem pada ridesharing. Mean shift clustering merupakan salah satu metode pengelompokkan data spasial dengan cara menetapkan titik data ke kelompok secara iteratif dengan menggeser titik ke mode (mode adalah kepadatan tertinggi dari titik data di wilayah tersebut, dalam konteks mean-shift). Sehingga dengan clustering akan lebih mudah dan efektif dalam memasangkan pengemudi dan penumpang secara optimal. Setelah didapatkan hasil clustering, pasangan pengemudi dan penumpang akan dipasangkan berdasarkan fungsi objektif memaksimumkan banyaknya pasangan yang terjadi (match). Ide dasar dari fungsi objektif tersebut yaitu menemukan banyaknya jumlah pasangan maksimum yang dapat melakukan ridesharing. Dengan bantuan algoritma Hopcroft Karp dapat menemukan solusi jumlah maksimum banyaknya pasangan pada ridesharing.

---

The high use of private vehicles due to inadequate public transport services in Indonesia, is one of the main factors causing congestion. One of the solution that problem is the use of a ridesharing system. The ridesharing system can reduce the use of private vehicles so as to reduce congestion. The problem that happened with this ridesharing system is the matching problem between the driver and the passenger (rider). Mean shift clustering will be used in this paper as the first step in optimizing the matching problem in ridesharing. Mean shift clustering is a method of grouping spatial data by iteratively assigning data points to groups by shifting points to mode (mode is the highest density of data points in the region, in the context of mean-shift). So that with clustering it will be easier and more effective in pairing drivers and passengers optimally. After the clustering results are obtained, the driver and passenger will be paired based on the objective function of maximizing the number of pairs that occur (match). The basic idea of this objective function is to find the maximum number of match to do ridesharing. With the help of the Hopcroft Karp algorithm, can find a solution for the maximum number of match to do ridesharing.