Ridesharing adalah suatu model transportasi dimana seorang pengendara (driver) berbagi tumpangan dengan penumpang lain (rider) yang memiliki lokasi asal tujuan dan jadwal perjalanan yang hampir sama atau sama dengan driver. Masalah utama dalam ridesharing yaitu menentukan pasangan driver dan rider yang paling optimal untuk melakukan ridesharing. Sebagai proses awal untuk mencari pasangan tersebut, dalam penelitian ini digunakan metode Clustering Large Applications (CLARA) untuk melakukan clustering terhadap titik-titik koordinat origin dan destination dari masingmasing driver dan rider. Sesuai dengan cluster dari masing-masing titik lokasi, dibentuk himpunan yang mungkin untuk berpasangan. Selanjutnya, untuk driver dan rider yang berada dalam himpunan yang sama diperiksa kelayakan (feasibility) untuk berpasangan berdasarkan kendala waktu, sehingga dihasilkan himpunan pasangan driver dan rider yang feasible, !" . Pada proses optimasi, fungsi obyektif yang dipertimbangkan yaitu memaksimumkan total Adjusted Distance Proximity (ADP) Index. ADP Index merupakan indikasi terjadinya efisiensi berdasarkan jarak tempuh dari tiap pasangan dalam melakukan ridesharing. Sesuai dengan hasil ADP index, dibentuk suatu weighted bipartite graph yang menggambarkan keterhubungan pasangan dalam !" . Proses mendapatkan himpunan pasangan yang memaksimumkan fungsi objektif diselesaikan dengan algoritma Hungarian dalam menyelesaikan Maximum-Weighted Matching pada Bipartite Graph. Setelah seluruh proses dilakukan, dihasilkan himpunan pasangan yang akan melakukan ridesharing. Pada penelitian ini ditunjukkan bahwa dengan melakukan clustering, proses optimasi menjadi lebih efisien dengan adanya pereduksian pasangan yang diuji dari 400 pasangan menjadi 131 pasangan dan banyak pasangan dalam hasil optimasi dengan clustering sama dengan hasil optimasi tanpa clustering yaitu 13 pasangan.

---

Ridesharing is a model of transportation where the driver share the seat of their vehicle to the rider who has similar departure location and travel schedule with the driver. The main problem in ridesharing is the determination of the optimal pairs of drivers and riders who will conduct ridesharing. As an initial process to find these pairs, in this study the Clustering Large Applications (CLARA) method was used to cluster the coordinate points of origin and destination of each driver and rider. In accordance with the clusters of each location point, a set of possible matches is formed. Furthermore, for drivers and riders who are in the same set, the feasibility of matching is examined based on time constraints, so that a feasible set of driver and rider matches, !" is produced. In the optimization process, the objective function considered is to maximize the total Adjusted Distance Proximity (ADP) Index. The ADP Index is an indication of efficiency based on the distance traveled by each match in ridesharing. In accordance with the results of the ADP index, a weighted bipartite graph is formed which describes the connectedness of the pairs in !" . The process of getting the set of pairs that maximizes the objective function is solved by using the Hungarian algorithm to solve the Maximum-Weighted Matching on a Bipartite Graph. After the whole process is done, a set of pairs that will do ridesharing are generated. In this study it was shown that by clustering, the optimization process became more efficient with the reduction of the matches examined from 400 matches to 131 matches and the number of matches in the optimization results with clustering was the same as the optimization results without clustering, that is 13 matches.