Gamayanti, Nurlita (2009) Pengembangan Algoritma Heuristik Ant Colony System untuk Menyelesaikan Permasalahan Dynamic Vehicle Routing Problem dengan Time Window (DVRPTW) pada Proses Konsolidasi Penyedia Jasa Inter-City Courier. Masters thesis, Institut Teknologi Sepuluh Nopember.
![[thumbnail of 2207202001-Master_thesis.pdf]](http://repository.its.ac.id/style/images/fileicons/text.png) |
Text
2207202001-Master_thesis.pdf Restricted to Repository staff only Download (77MB) |
Abstract
Pada penyedia jasa Inter-City Courier, armada pengangkutan beserta kurir berangkat dari depo, mengunjungi sekelompok konsumen untuk mengambil paket-paket konsumen dalam time window tertentu yang tersebar di berbagai lokasi secara meluas, untuk dikumpulkan di salah satu consolidation point, dan selanjutnya dikirimkan ke kota tujuannya masing-masing. Permasalahan yang dihadapi adalah bagaimana menentukan pengelompokan lokasi konsumen yang tersebar sehingga bisa lebih efisien dalam melayaninya, serta menentukan rute yang harus ditempuh oleh tiap-tiap armada pengangkutan sehingga didapatkan waktu tempuh (travel time) paling minimum secara keseluruhan. Permasalahan penentuan rute seperti di atas dirumuskan sebagai Dynamic Vehicle Routing Problem with Time Window (DVRPTW). Pada penelitian ini, dikembangkan suatu algoritma heuristik untuk menyelesaikan permasalahan DVRPTW pada penyedia jasa Inter-City Courier. Algoritma dibagi menjadi dua tahap, yaitu tahap statis dan tahap dinamis. Pada tahap statis digunakan algoritma Ant Colony System yang telah dimodifikasi, sedangkan pada tahap dinamis digunakan algoritma Insertion Heuristics. Berbeda dengan permasalahan Vehicle Routing Problem with Time Window (VRPTW) klasik, pada DVRPTW rute kendaraan dibangkitkan secara dinamik berdasarkan informasi real-time seperti penerimaan order baru dan posisi kendaraan saat itu. Untuk menguji performansi algoritma, dilakukan uji eksperimen dengan menggunakan data uji standar milik Chen. Setelah itu, algoritma diterapkan pada data jaringan jalan di kota Surabaya. Selain itu, algoritma dibandingkan dengan algoritma nearest neighbor dan nearest neighbor + node insertion. Akhirnya, penulis menyimpulkan bahwa algoritma yang dikembangkan pada permasalahan Inter-City Courier menghasilkan total travel time yang lebih baik daripada nearest neighbor dan nearest neighbor + insertion heuristics, serta mampu membangkitkan rute secara dinamik dalam rangka merespons order baru.
==================================================================================================================================
In an inter-city courier service provider, vehicles start from a depot, visit a set of customers to collect packages within specified time windows across widespread locations, and finish at one of the consolidation points to be dispatched to their respective destination cities. The main challenge is determining how to construct routes for each vehicle in order to minimize the overall total travel time while serving scattered customers efficiently. This route construction problem is formulated as a Dynamic Vehicle Routing Problem with Time Window (DVRPTW). In this paper, we develop a heuristic algorithm to solve the DVRPTW for inter-city courier services. The algorithm is divided into two phases: a static phase and a dynamic phase. In the static phase, a modified Ant Colony System algorithm is applied, whereas in the dynamic phase, an insertion heuristic algorithm is utilized. Unlike the classic Vehicle Routing Problem with Time Window (VRPTW), vehicle routes in DVRPTW are dynamically generated in response to real-time information, such as incoming new customer requests and current vehicle locations. To evaluate the performance of the proposed algorithm, numerical experiments were conducted using Chen's standard benchmark test datasets. The algorithm was subsequently implemented using the street network data of Surabaya. Furthermore, the performance of the algorithm was benchmarked against the nearest neighbor and nearest neighbor + node insertion algorithms. Experimental results demonstrate that the developed algorithm effectively solves the inter-city courier DVRPTW, yields a superior total travel time compared to nearest neighbor and nearest neighbor + insertion heuristics, and dynamically updates routes in response to new orders.
| Item Type: | Thesis (Masters) |
|---|---|
| Uncontrolled Keywords: | Intercity Courier, Dynamic Vehicle Routing Problem dengan Time Window (DVRPTW), Ant Colony System, Insertion Heuristics, Dispatcher , Intercity Courier, Dynamic Vehicle ,Routing Problem dengan Time Window (DVRPTW), Ant Colony System, Insertion Heuristics, Dispatcher |
| Subjects: | T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK5105.546 Computer algorithms |
| Divisions: | Faculty of Electrical Technology > Electrical Engineering > 20101-(S2) Master Thesis |
| Depositing User: | magang . |
| Date Deposited: | 29 Sep 2026 04:17 |
| Last Modified: | 29 Sep 2026 04:17 |
| URI: | http://repository.its.ac.id/id/eprint/145009 |
Actions (login required)
 |
View Item |