Penyelesaian CCVRPTW Menggunakan Biased Random Key Genetic Algorithm-Populasi Degradasi

Listy Avri Christiana(1*), Hari Prasetyo(2),

(1) 
(2) Jurusan Teknik Industri Universitas Muhammadiyah Surakarta
(*) Corresponding Author
DOI: https://doi.org/10.23917/jiti.v16i1.3846

Abstract

The article presents the Biased Random Key Genetic Algorithm-Population Degradation (BRKGA-PD) design for completing Capacitated Closed Vehicle Routing Problem with Time Windows (CCVRPTW) on soft drink distributions that have been studied by Sembiring (2008). The goal is to determine some closed routes in meeting consumer demand with time limits and limit the capacity of vehicles used, so the total cost of distribution is minimal. The proposed algorithm adopts the extinction of population size. BRKGA-PD is coded using Matlab programming with the best parameter setting. The resulting solution is a subrute with a minimum of distribution fee. This algorithm is compared with two other methods, namely BRKGA general and heuristic methods. The results of this study can be concluded that the BRKGA-PD method is able to improve the general BRKGA because with a time difference that is not significant can provide cost savings of Rp. 6.857,- and BRKGA-PD is better than heuristic method because it can save more cost Rp. 87.000,-.

Keywords

BRKGA; CCVRPTW; population degradation; minimum cost

Full Text:

PDF

References

Asteria, C. (2008). Penentuan Rute Distribusi dengan Algoritma Tabu Search untuk VRP dengan Time Windows. Tesis. Universitas Indonesia.

Awansari, S.A.; S. Abusini. (2013). “Impementasi model Capacitated Vehicle Routing problem pada pengiriman pupuk urea bersubsidi”. Jurnal Mahasiswa Matematika, Vol. 1(5).

Ballou, R.H.; Agarwal, Y.K. (1998). “A performance comparison of several popular algorithms for vehicle routing and scheduling”. Journal of Business Logistics, Vol. 9 (1), pp.: 51 – 65.

Baskoro, S. (2011). Penerapan Algoritma Tabu Search Untuk Penyelesaian Capacitated Vehicle Routing Problem (CVRP) Studi Kasus di PT. Wahyu Jaya. Skripsi. Diponegoro University. Semarang.

Bean, J.C. (1994). “Genetic algorithms and random keys for sequencing and optimization”. ORSA Journal on Computing, Vol. 6, pp.: 154 – 160.

Darwin, C. (2004). Britannica Concose Encylopedia from Encyclopedia Britanica. Available from: .

Garey M.R.; Johnson, D.S. (1979). Computers and Intractability: A guide to The Theory of NP-Completeness. W.H. Freeman & Co. San Francisco.

Gonçalves, J.F.; Resende, M.G. (2011). “Biased random-key genetic algorithms for combinatorial optimization”. Journal of Heuristics, Vol. 17, pp.: 487 – 525.

Grasas, A.; Ramalhinho, H.; Pessoa, L.S.; Resende, M.G.; Caballé, I.; Barba, N. (2014). “On the improvement of blood sample collection at clinical laboratories”. BMC Health Services Sesearch, Vol. 14, pp.: 12.

Hendrawan, B.E. (2007). Implementasi Algoritma Pararel Genetic Algorithm untuk Penyelesaian Heterogeneous Fleet Vehicle Routing Problem. Tugas Akhir. Institut Teknologi Sepuluh November. Surabaya.

Putri, F.B.; Mahmudy, W.F.; Ratnawati, D.E. (2014). Penerapan Algoritma Genetik Untuk Vehicle Routing Problem with Time Window (VRPTW) Pada Kasus Optimasi Distribusi Beras Bersubsidi. Skripsi . Malang: Universitas Brawijaya.

Sembiring, A. C. (2008). Penentuan Rute Distribusi Produk yang Optimal dengan Menggunakan Algoritma Heuristik Pada PT. Coca-Cola Bottling Indonesia Medan. Tugas Akhir. Universitas Sumatera Utara. Medan.

Slamet, A.S., Siregar, H.H.; Kustiyo, A. (2014). “Vehicle routing problem (VRP) dengan algoritma genetika pada pendistribusian sayuran dataran tinggi”. Jurnal Teknologi Industri Pertanian, Vol. 24 (1), pp.: 1 – 10.

Spears, V.M.; De Jong, K.A. (1991). “On The Virtues of Parameterized Uniform Crossover”. In Proceedings of the Fourth International Conference on Genetic Algorithms, pp.: 230–236.

Sundarningsih, D.; Mahmudy, W.F.; Sutrisno. (2015). Penerapan Algoritma Genetika untuk Optimasi Vehicle Routing Problem With Time Window (VRPTW) Studi Kasus Air Minum Kemasan. Skripsi. Malang: Universitas Brawijaya.

Toth, P.; Vigo, D. (2002). An Overview of Vehicle Roting Problem. In The Vehicle Routing Problem. Edited by Toth P, Vigo D. Philadelphia: SIAM, pp.:1 – 26.

Article Metrics

Abstract view(s): 640 time(s)
PDF: 700 time(s)

Refbacks

  • There are currently no refbacks.