Pengoptimuman Proses Antar Jemput Barang dan Waktu Penanganan dengan Time Windows Menggunakan Algoritme Ant Colony dan Tabu Search

Abstract

Traveling Salesman Problem with Pick-ups, Deliveries, Handling Costs (times), and Time Windows (TSPPDHTW) merupakan permasalahan antar jemput barang yang memuat kendala keterbatasan pada kapasitas kendaraan, akses angkut pada kendaraan, dan time windows pelanggan. Permasalahan kasus TSPPDHTW telah dimodelkan pada penelitian sebelumnya dan berhasil diselesaikan dengan menggunakan metode eksak untuk mendapatkan rute dan kebijakan penyusunan barang yang meminimumkan waktu tempuh dan waktu penanganan, tetapi pencarian solusi dengan metode eksak membutuhkan waktu komputasi yang sangat lama yaitu sekitar 134 jam sehingga sangat tidak efisien untuk diaplikasikan dalam kehidupan sehari-hari. Pada penelitian ini, kasus TSPPDHTW diselesaikan dengan meggunakan metode metaheuristik. Metaheuristik merupakan metode yang mencari solusi melalui pendekatan pada solusi optimal dengan waktu komputasi yang lebih cepat. Ant Colony Optimization (ACO) dan Tabu Search (TS) merupakan metaheuristik yang sering dikombinasikan oleh para peneliti untuk menyelesaikan kasus TSP dan turunannya. ACO merupakan metode berupa algoritme yang meniru koloni semut ketika mencari sumber makanan dan kembali ke sarangnya yang secara alami mencari rute terpendek, sedangkan TS adalah metaheuristik yang menggunakan prosedur pencarian heuristik lokal untuk mencari solusi berdasarkan keoptimalan lokal. Tujuan penelitian ini adalah mengembangkan algoritme heuristik berbasis ACO dan TS untuk menyelesaikan model TSPPDHTW pada penelitian sebelumnya kemudian membandingkan hasilnya dengan solusi eksak. Data yang digunakan yaitu 14 toko sepeda yang ada di Bogor sebagai pelanggan dan satu sebagai depot. Data waktu tempuh antartoko diperoleh menggunakan bantuan Google maps. Time windows yang didefinisikan sebagai waktu buka dan tutup masing-masing toko serta jumlah permintaan setiap toko menggunakan data hipotetik. Pengembangan algoritme dilakukan dengan menggunakan bahasa pemrograman Octave. Dalam penelitian ini, algoritme ACO dan TS dikembangkan sesuai dengan kompleksitas masalah pada TSPPDHTW, kemudian dilakukan simulasi untuk mengetahui nilai parameter yang cocok untuk menyelesaikan studi kasus TSPPDHTW. Penyelesaian studi kasus yang dilakukan akan dibandingkan hasilnya dengan metode eksak. Pengembangan ACO dimulai dengan menambah beberapa fungsi pada algoritme dasar berupa fungsi clustering, evaluasi kendala, cutting tour, dan penyusunan barang di dalam kendaraan serta modifikasi pada aturan transisi. Fungsi clustering diterapkan sebelum proses pembangunan rute. Fungsi ini bertujuan mengklasifikasikan seluruh pelanggan yang akan dikunjungi berdasarkan kedekatan jarak pada time windows sehingga solusi dapat lebih mudah mengarah pada solusi yang fisibel. Fungsi evaluasi kendala ditujukan agar pelanggan yang akan dihitung peluang transisinya hanyalah pelanggan yang memenuhi kendala, dalam hal ini yaitu kendala kapasitas kendaraan dan time windows pelanggan. Fungsi cutting tour adalah fungsi yang digunakan ketika semut terjebak saat pembangunan rute akibat tidak ada lagi pelanggan yang memenuhi kendala pada saat itu. Selanjutnya adalah fungsi yang mengatur penyusunan barang di dalam kendaraan. Kebijakan penyusunan barang yang digunakan pada penelitian ini adalah menyusun barang jenis I milik pelanggan selanjutnya di posisi paling belakang kendaraan sesaat sebelum dikunjungi, diikuti dengan barang-barang jenis II yang sudah diambil, kemudian barang jenis I yang belum diantar berada di posisi paling depan. Terakhir yaitu memodifikasi aturan transisi, dilakukan dengan menambahkan unsur prioritas pada saat memilih pelanggan selanjutnya, yaitu dengan memilih pelanggan yang memiliki batas awal time windows terkecil sebagai pelanggan selanjutnya yang dikunjungi. Tidak hanya ACO, TS juga memerlukan sedikit pengembangan agar dapat menyelesaikan kasus TSPPDHTW. Pengembangan dilakukan dengan menambahkan fungsi yang dapat mengevaluasi move yang akan dilakukan berdasarkan kendala kapasitas dan time windows. Rute yang terbentuk setelah dilakukan move akan dievaluasi apakah rute tersebut masih fisibel atau tidak. Pada akhirnya fungsi ini yang akan menentukan boleh atau tidaknya suatu move dilakukan pada rute yang terbentuk saat itu. Setelah ACO dan TS berhasil dikembangkan menjadi algoritme ACOTS, maka dilakukan simulasi terhadap beberapa parameter ACO dengan skenario tertentu. Parameter yang disimulasikan yaitu α (faktor pengendali feromon), β (faktor pengendali jarak), ρ (faktor penguapan), nAnt (jumlah semut) dan jumlah iterasi. Hasilnya adalah pada simulasi ini tidak terlihat adanya pengaruh perubahan nilai α dan ρ baik terhadap nilai fungsi objektif maupun waktu komputasi karena secara umum grafik bersifat fluktuatif. Sementara itu, perubahan pada β yang disimulasikan pada kasus ini menunjukkan bahwa semakin besar nilai β menyebabkan semakin besar nilai fungsi objektif yang kemudian konvergen ke suatu nilai, sementara waktu komputasi cukup fluktuatif dengan pola menurun. Adapun peningkatan jumlah iterasi meningkatkan waktu komputasi, meskipun tidak terlihat adanya kecenderungan meningkat atau menurun pada nilai fungsi objektif. Pada simulasi perubahan nAnt, nilai fungsi objektif terlihat menurun pada rentang 10-20 semut, sementara waktu komputasi cenderung fluktuatif dengan pola menaik. Dari hasil simulasi ini juga dihasilkan beberapa kombinasi nilai parameter yang memberikan solusi yang cukup baik, yaitu pada nilai α=5,β=1,ρ=0,5,nAnt=5 dengan 5 iterasi masing-masing pada ACO dan TS. Nilai parameter tersebut digunakan untuk menyelesaikan studi kasus TSPPDHTW yang telah dimodelkan pada penelitian sebelumnya. Solusi yang diperoleh menggunakan ACOTS dalam waktu 61 detik menghasilkan rekomendasi rute dengan nilai fungsi objektif sebesar 408 menit yang terdiri atas 286 menit waktu tempuh perjalanan dan 122 menit waktu penanganan. Jika dibandingkan dengan solusi eksak, nilai tersebut memiliki deviasi sekitar 22% yang didominasi oleh besarnya deviasi waktu penanganan terhadap solusi optimal. Namun demikian, pencarian solusi dengan ACOTS berhasil menghemat waktu komputasi hingga 99,99%. Kata kunci: ACO, antar jemput barang, tabu search, TSP, waktu penanganan

The Traveling Salesman Problem with Pick-ups, Deliveries, Handling Costs (times), and Time Windows (TSPPDHTW) is a problem for picking up goods that includes limitations on vehicle capacity, transportation access on vehicles, and time window of customers. The TSPPDHTW has been modeled in previous studies and was successfully solved using the exact method. However, finding solutions using exact methods requires a very long computational time, it’s about 134 hours, so it is very inefficient to be applied in real life. In this study, the case of TSPPDHTW is solved using the metaheuristic method. A metaheuristic is a method that looks for solutions through an approach to the optimal solution with a faster computation time. Ant Colony Optimization (ACO) and Tabu Search (TS) are metaheuristics that are often combined by researchers to solve cases of TSP and its varians. ACO is a method that imitates an ant colony when looking for food sources and returns to the nest naturally looking for the shortest route, while TS is a metaheuristic that uses a local heuristic search procedure to find solutions based on local optimization. The purpose of this study is to develop a heuristic algorithm based on ACO and TS to complete the TSPPDHTW model in previous studies and then compare the results with the exact method. The data used are 14 bicycle shops in Bogor as customers and one as a depot. Travel times between stores are obtained by Google maps. Time windows are defined as the opening and closing times of each store. The number of requests for each store using hypothetical data. Both algorithms are developed by using Octave programming language. In this study, the ACO and TS algorithms were developed according to the complexity of the problem in the TSPPDHTW, then a simulation was carried out to find out the value of the suitable parameters to complete the TSPPDHTW case study. The completion of the case study will be compared with the exact results. The improvement of ACO began by adding several functions to the basic algorithm in the form of clustering functions, evaluation of constraints, cutting tours, and arrangement of goods in vehicles as well as modifications to transition rules. The clustering function is applied before the route construction process. This function aims to classify all customers to be visited based on the proximity of the time windows so that the solution can more easily lead to a feasible solution. The constraint evaluation function is intended so that the customers whose transition opportunities will be calculated are the only customers who meet the constraints, in this case, the vehicle capacity and time windows constraints. The cutting tour function is a function that is used when ants are trapped during route construction because there are no more customers who meet the constraints at that time. The next is the function that regulates the arrangement of goods in the vehicle. The policy of arranging goods used in this study is to arrange type I goods of the customer who will be visited in the next, in the rearmost position of the vehicle just before being visited, followed by type II goods that have been taken, then type I goods that have not been delivered are in the front position. Lastly, the modification of the transition rules is carried out by adding an element of priority when selecting the next customer, namely by selecting the customer who has the earlier time windows limit as the next customer to be visited. Not only ACO but also TS needs a bit of modification to solve the TSPPDHTW case. Modification is carried out by adding a function that can evaluate the move based on capacity constraints and time windows. The route formed after the move will be evaluated whether route is still feasible or not. In the end, this function will determine whether that move is allowed on the route that was formed at that time. After ACO and TS have been successfully developed into the ACOTS algorithm, several ACO parameters are simulated with certain scenarios. The simulated parameters are α (pheromone control factor), β (distance control factor), ρ (evaporation factor), nAnt (number of ants), and the number of iterations. The result shows that in this simulation, there is no significant impact of changes in the values of α and ρ on the computational time and the value of the objective function because in general, the graph is volatile. Meanwhile, the simulation of β value shows that the larger the value of β causes the larger the objective function value which then converges to a specific value, while the computation time is quite fluctuating with a decreasing pattern. As for the increase in the number of iterations, it increases computational time, although there is no tendency to increase or decrease the value of objective functions. At the simulation of nAnt change, the value of the objective function is seen to decrease in the range of 10-20 ants, while computational time tends to fluctuate with an ascending pattern. From the simulation results, several combinations of parameter values are also known which provide a fairly good solution, namely the value of α=5, β=1, ρ=0,5, nAnt=5 with 5 iterations each for ACO and TS. These parameter values are used to complete the TSPPDHTW case that has been modeled in previous studies. The solution obtained using ACOTS within 61 seconds resulted in a route recommendation with an objective function value of 408 minutes consisting of 286 minutes for travel time and 122 minutes for handling time. When compared to an exact solution, the value has a deviation of about 22% which is dominated by the magnitude of the deviation of the handling time against the optimal solution. However, finding a solution with ACOTS managed to save up to 99,99% of the computation time. Keywords: ACO, handling times, pickup-delivery, tabu search, TSP