Paramestha, Dominico Laksma (2017) Pengembangan Algoritma Cross Entropy Genetic Algorithm Untuk Penyelesaian Two Dimensional Loading Heterogeneous Fleet Vehicle Routing Problem. Masters thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
2514203203-Master_Theses.pdf - Published Version Download (32MB) | Preview |
Abstract
Two dimensional loading heterogeneous fleet vehicle routing problem (2L-HFVRP) merupakan permasalahan kombinatorial gabungan dari vehicle routing problem dan bin packaging problem. Pada 2L-HFVRP pesanan konsumen berupa muatan berbentuk persegi panjang yang harus dikirim dari depot dengan beberapa vehicle yang memiliki kapasitas container/box yang berbeda-beda. Tujuan dari 2L-HFVRP adalah meminimalkan total biaya perjalanan dari depot ke seluruh konsumen dan kembali ke depot. Setiap rute yang terbentuk harus feasible dengan kapasitas dan proses penataan muatan untuk dalam setiap kendaraan.
Proses penataan muatan menggunakan 5 heuristik yang digunakan oleh Zachariadis et.al (2009). Penelitian ini menggunakan dua skenario dalam penataan muatan ke dalam kontainer. Skenario pertama (sequential) adalah menata muatan sesuai dengan urutan kunjungan dan bongkar muat, agar proses bongkar muat dapat dilakukan dengan mudah. Skenario kedua (unrestricted) adalah dengan menata muatan dengan memasukan muatan tanpa mempertimbangkan urutan kunjungan. Rotasi muatan dimungkinkan dalam proses penataan muatan untuk memaksimalkan utilitas ruang dari kontainer.
Sebagai gabungan dari dua NP-hard problem penelitian ini menggunakan algoritma cross entropy genetic algorithm (CEGA) untuk menyelesaikan 2L-HFVRP. Algoritma ini menutupi kekurangan dari algoritma CE dan GA jika digunakan sendiri dengan kelebihan dari masing-masing algoritma. Proses pencarian solusi awal menggunakan mekanisme matriks probabilitas transisi dibantu dengan mekanisme local improvement yang dikembangkan oleh Ai & Kachitvichyanukul (2009) untuk mendapatkan solusi awal yang baik. Hasil akan dibandingkan dengan algoritma lain dari penelitian sebelumnya untuk melihat performansi dari algoritma yang dikembangkan dalam penelitian ini.
==================================================================================================================
Two dimensional loading heterogeneous fleet vehicle routing problem (2L-HFVRP) is a combination of Heterogeneous Fleet VRP and a packing problem well-known as Two Dimensional Bin Packing Problem (BPP). 2L-HFVRP is a Heterogeneous Fleet VRP in which these costumer demands are formed by a set of two-dimensional rectangular weighted item. These demands must be served by a heterogeneous fleet of vehicles with a fix and variable cost from the depot. The objective function 2L-HFVRP is to minimize the total transportation cost which relies on the type of vehicle and the route while satisfying all of the customer demands. All formed routes must be consistent with the capacity and loading process of the vehicle.
In this paper, the loading process follows the 5 heuristic which was used by Zachariadis et.al (2009) and allowed to 90o rotation position. Allowing rotation position on loading process is used to maximize the utility of vehicle. Sequential and unrestricted scenarios are considered on this paper. Sequential scenario is a scenario that deals with loading and unloading item into vehicle. The sequence of the loading process is affected by the sequence of the route. Whereas unrestricted scenario is a scenario that only deals with feasible loading of item into the vehicle.
We propose a metaheuristic which is a combination of the Genetic Algorithm (GA) and the Cross Entropy (CE) named Cross Entropy Genetic Algorithm (CEGA) to solve the 2L-HFVRP. The mutation concept on GA is used to speed up the algorithm CE to find the optimal solution. The mutation mechanism was based on local improvement that was developed by Ai & Kachitvichyanukul (2009). The probability transition matrix mechanism on CE is used to avoid getting stuck in local optimum. The effectiveness of CEGA was tested on benchmark instance based 2L-HFVRP. The result of experiments show a competitive result compared with another algorithm.
| Item Type: | Thesis (Masters) |
|---|---|
| Uncontrolled Keywords: | Metaheuristic, Cross Entropy, Genetic Algorithm, Vehicle Routing Problem, Two-loading constraint |
| Subjects: | Q Science > Q Science (General) Q Science > QA Mathematics > QA75 Electronic computers. Computer science. EDP T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK5105.546 Computer algorithms |
| Divisions: | Faculty of Industrial Technology > Industrial Engineering > 26101-(S2) Master Thesis |
| Depositing User: | - DOMINICO LAKSMA PARAMESTHA |
| Date Deposited: | 29 Mar 2017 03:00 |
| Last Modified: | 05 Mar 2019 06:25 |
| URI: | http://repository.its.ac.id/id/eprint/2386 |
Actions (login required)
 |
View Item |