Pemodelan Waktu Tunggu Antrean Time-Dependent pada Queue-Aware Orienteering Problem untuk Rute Kunjungan Theme Park dan Perbandingan Performa Empat Algoritma

Athaya Harmana Putri, Ir. Azkario Rizky Pratama, S.T., M.Eng., Ph.D., IPM.; Dr. Bimo Sunarfri Hantono, S.T., M.Eng.

2026 | Skripsi | TEKNOLOGI INFORMASI

Model Orienteering Problem (OP) yang umum digunakan mengasumsikan biaya kunjungan bersifat statis, sedangkan pada kondisi nyata waktu tunggu antrean di taman hiburan dapat berubah sepanjang jam operasional. Penelitian ini mengembangkan model Queue-Aware OP yang menempatkan waktu tunggu antrean sebagai komponen biaya time-dependent pada simpul, serta membandingkan performa algoritma Greedy, GRASP, Ant Colony Optimization (ACO), dan Adaptive Large Neighborhood Search (ALNS) dalam menyelesaikan model tersebut melalui eksperimen komputasional menggunakan 25 wahana terpilih pada Disneyland Resort yang dimodelkan sebagai graf berbobot. Waktu tempuh antarnode dihitung menggunakan algoritma Dijkstra, sedangkan waktu tunggu antrean disusun secara sintetis berdasarkan pola kepadatan pada fitur Popular Times Google Maps. Hasil eksperimen pertama menunjukkan bahwa model OP standar menghasilkan rute yang identik pada keempat skenario dengan reward sebesar 167,78, tetapi rute tersebut menjadi tidak layak ketika waktu tunggu antrean diperhitungkan, dengan waktu kunjungan mencapai 286,1?ri anggaran yang tersedia. Sebaliknya, model Queue-Aware OP menghasilkan rute yang layak pada seluruh skenario, meskipun reward yang diperoleh 53,4–76,4% lebih rendah dibandingkan estimasi pada model OP standar. Pada eksperimen kedua, GRASP dan ALNS menghasilkan rata-rata RPD masing-masing sebesar 0,715?n 0,737%, sedangkan ACO dan Greedy masing-masing sebesar 3,762?n 4,029%. Hasil uji Friedman Aligned-Ranks dan Conover-Friedman menunjukkan bahwa GRASP dan ALNS memiliki performa yang secara signifikan lebih baik dibandingkan ACO, sedangkan keduanya tidak menunjukkan perbedaan performa yang signifikan satu sama lain. Berdasarkan hasil tersebut, model Queue-Aware OP mampu merepresentasikan waktu tunggu antrean sebagai komponen biaya time-dependent yang memengaruhi kelayakan dan kualitas rute, sehingga pengabaian komponen tersebut pada model OP standar dapat menghasilkan estimasi kualitas rute yang terlalu optimistis dan tidak sesuai dengan kondisi antrean yang sebenarnya. Pada kondisi antrean padat yang diuji dalam penelitian ini, GRASP dan ALNS menunjukkan performa terbaik dan setara secara statistik.

The commonly used Orienteering Problem (OP) model assumes that visiting costs are static, whereas under real-world conditions, queue waiting times at amusement parks vary throughout operating hours. This study develops a Queue-Aware OP model that incorporates queue waiting time as a time-dependent cost component at each node, and compares the performance of the Greedy, GRASP, Ant Colony Optimization (ACO), and Adaptive Large Neighborhood Search (ALNS) algorithms in solving the proposed model through computational experiments using 25 selected attractions at Disneyland Resort, modeled as a weighted graph. Travel time between nodes was computed using Dijkstra’s algorithm, while queue waiting times were synthetically constructed based on density patterns from Google Maps’ Popular Times feature. The results of the first experiment show that the standard OP model produced an identical route across all four scenarios with a reward of 167.78; however, this route became infeasible once queue waiting time was taken into account, with the total visiting time reaching 286.1% of the available time budget. In contrast, the Queue-Aware OP model produced feasible routes across all scenarios, although the resulting reward was 53.4–76.4% lower than the estimate obtained from the standard OP model. In the second experiment, GRASP and ALNS achieved average RPD values of 0.715% and 0.737%, respectively, whereas ACO and Greedy achieved 3.762% and 4.029%, respectively. The Friedman Aligned-Ranks and Conover–Friedman tests indicated that GRASP and ALNS performed significantly better than ACO, while showing no statistically significant difference between one another. Based on these findings, the Queue-Aware OP model is able to represent queue waiting time as a time-dependent cost component that affects route feasibility and quality, indicating that neglecting this component in the standard OP model may lead to overly optimistic route quality estimates that do not reflect actual queuing conditions. Under the high-congestion conditions examined in this study, GRASP and ALNS demonstrated the best and statistically equivalent performance.

Kata Kunci : Orienteering Problem, waktu tunggu antrean, time-dependent, metaheuristik, taman hiburan