Perkembangan teknologi memungkinkan perusahaan untuk senantiasa meningkatkan kinerjanya dalam berbagai kegiatan usaha. Salah satu kegiatan usaha yang menjadi perhatian adalah distribusi. Penentuan rute distribusi harus mempertimbangkan permintaan pelanggan dan biaya transportasi. Perancangan rute distribusi yang meminimalisir jarak tempuh transportasi dapat menghemat biaya distribusi. Di sisi lain, ketepatan waktu pengiriman juga masih menjadi salah satu faktor penting distribusi. Penelitian ini berfokus pada perancangan algoritma penyelesaian Vehicle Routing Problem with Time Windows (VRPTW) dengan metode heuristik Lin Kernighan Helsgaun dan Local Search. Hasil dari algoritma ini adalah rute distribusi yang memenuhi permintaan pelanggan dengan memenuthi batasan kapasitas kendaraan dan rentang waktu pelayanan.
Technology development has enabled businesses to continuously improve their performance on various activities. One of the highlighted activity is distribution. The planning of distribution routes must consider customer demands and transportation cost. A better distribution route planning that minimizes transportation distances would save distribution costs. On the other hand, timeliness remains one of the important factors of distribution. This research focuses on designing an algorithm that solves Vehicle Routing Problem with Time Windows (VRPTW) using the heuristic methods which are Lin Kernighan Helsgaun and Local Search. The result of the algorithm is a list of routes that fulfills all demands and within the constraints of limited capacity and a drop off time window.
"Model perencanaan perjalanan telah berkembang dari faktor kuantitatif yaitu pencapaian waktu tersingkat menjadi faktor kualitatif yaitu pencapaian kepuasan. Kepuasan ini didapatkan dari kunjungan ke sejumlah tempat yang dianggap penting, kritis, atau favorit sesuai lingkup model tersebut. Penerapan dalam bidang pariwisata akan membantu wisatawan dalam pembentukan rute perjalanan pariwisata yang layak dan berkualitas tinggi. Model yang dikembangkan pada penelitian ini adalah Team Orienteering Problem with Time Windows (TOPTW). Pada model awal dilakukan penyusunan rute dengan memperhatikan prioritas wisatawan, maksimum total waktu yang dimiliki wisatawan, lokasi awal yang sama dengan lokasi akhir, serta jam operasional destinasi wisata (time window). Penelitian perencanaan perjalanan wisata ini mengubah model awal dengan melakukan penyesuaian kebutuhan wisatawan yang belum terpenuhi dan mencapai tujuan kedua yaitu minimum total waktu yang dibutuhkan. Model usulan memperhatikan waktu kedatangan yang diinginkan wisatawan, lokasi awal dan akhir yang berbeda, serta toleransi waktu yang ditetapkan wisatawan terhadap jam buka dan jam tutup suatu destinasi, serta hari operasional destinasi wisata. Wisatawan juga dapat mengubah waktu kunjungan (service time), skor destinasi yang menunjukan tingkat kefavoritan, dan menentukan waktu kedatangan ke destinasi wisata.
Metode yang digunakan bertujuan untuk mencari keseimbangan (equilibrium solution) antara hasil yang optimal dengan proses perhitungan yang lebih efisien. Metode pencarian hasil akan diawali dengan kontruksi heuristik untuk mengakomodasi destinasi favorit terlebih dahulu dalam rute, dilanjutkan dengan tahapan local search untuk mendapatkan pengaturan terbaik dari rute-rute tersebut. Metode yang digunakan adalah Iterated Local Search (ILS) yang disesuaikan, yaitu Adjusted ILS (AILS). AILS terdiri dari tahapan permutasi dan reversed untuk setiap rute, dan terakhir adalah perturbasi untuk semua rute yang terbentuk. Pada setiap tahapan akan dibandingkan total skor dan total waktunya, dan yang terbaik akan melanjutkan ke tahapan berikutnya. Setiap tahapan ini akan melalui diverifikasi untuk menjamin kelayakan hasil.
Selain itu dilakukan perbandingan metode antara AILS dan metode metaheuristik lain seperti Multi-start Simulated Annealing (MSA), Simulated Annealing (SA), Artificial Bee Colony (ABC) dan ILS. Hasil dari uji statistik menyatakan adanya perbedaan hasil di antara metode AILS dan metode-metode lainnya. Metode AILS memiliki keunggulan lebih tingginya skor per destinasi yang berarti lebih banyak destinasi favorit yang dikunjungi yaitu rata-rata sebesar 26% untuk metode MSA, SA, dan ABC, dan 21% untuk metode ILS. Running time pada AILS lebih singkat 537% daripada metode MSA, SA dan ABC, dan lebih lama 42% dibandingkan metode ILS. Semua metode yang dibandingkan tidak memiliki total waktu seperti yang telah dilakukan dalam AILS. Setelah itu dibuat sistem rekomendasi bernama ROSTER (Routing System Recommendation) untuk kemudahan penggunaan dan pemahaman hasil.
The travel planning model has expanded from quantitative factor with the achievement of the shortest time, into a qualitative factor with the achievement of satisfaction. The satisfaction is obtained from visiting a number of destinations that are considered important, critical, or favorite. Application in the tourism industry will help tourists to develop an appropriate and high-quality travel routes. The development model in this study is Team Orienteering Problem with Time Windows (TOPTW). In the initial model, route planning considers tourist priorities, the maximum total time owned by tourists, the same initial location as the final location, and the operational hours of each destination or time window. This research develop the initial model by adjusting more demand of tourists and achieve the second goal, the minimum total time. The proposed model consider arrival time of tourists, different initial and final locations, time tolerance from tourists to destination operational hours, and operational days of the destinations. Tourists can also adjust the time of visit or service time, destination scores that indicate the level of favorability, and determine the time of arrival to tourist destinations.
The method used aims to find a balancing (equilibrium solution) between optimal results with more efficient running time. The method will begin with a heuristic construction to accommodate the favorite destinations in advance on the route, followed by the local search to get the best routes. The method used is modification of Iterated Local Search (ILS) and being Adjusted ILS (AILS). AILS consists of permutation and reversed stages for each route, and perturbation for all routes formed in previous stages. At each stage the total score and total time will be compared, and the best routes will proceed to the next stage. Each of these stages will be verified through to ensure the feasibility of the results.
A comparison method was conducted between AILS and other metaheuristic methods such as Multi-start Simulated Annealing (MSA), Simulated Annealing (SA), Artificial Bee Colony (ABC) and ILS. The results of the statistical test revealed differences in results between the AILS method and other methods. The AILS method has the advantage of higher scores per destination which means more favorite destinations visited are on average 26% for the MSA, SA, and ABC methods, and 21% for the ILS method. Running time on AILS is 537% shorter than MSA, SA and ABC methods, and 42% shorter than ILS method. All the previous methods do not have the minimum total time that was reached in AILS. A recommendation system named ROSTER (Routing System Recommendation) was made for user convenience.
"
