Pengembangan Metode Pengambilan Keputusan pada Multi-Agent Reinforcement Learning untuk Multi-Depot Vehicle Routing Problem with Time Window

SALSABILA Q, Suprapto, Drs., M.Kom., Dr.

2022 | Skripsi | S1 ILMU KOMPUTER

Permasalahan Multi-Depot Vehicle Routing Problem with Time Window (MDVRPTW) yang merupakan bagian dari Vehicle Routing Problem (VRP) sudah ada sejak lama dan merupakan bagian dari permasalahan NP-hard. Modified Pointer Network (MPN) serta Mutli-Agent Attention Model (MAAM) dapat menyelesaikan Capacitated VRP serta Multi-VRP with Soft Time Window dengan sangat baik. Pada penelitian ini, kami memodifikasi MPN dan MAAM sehingga arsitektur dapat menerima permasalahan MDVRPTW dan dapat menerima jumlah kapasitas kendaraan yang berbeda dengan mengubah kedua arsitektur menjadi multi-agent. Dengan hyperparameter yang sama, arsitektur MPN dan MAAM dengan formulasi decoding multi-agent terbukti memiliki performa yang lebih baik dibandingkan dengan single agent sebanyak 18 dari 20 dataset.

Multi-Depot Vehicle Routing Problem with Time Window (MDVRPTW), part of Vehicle Routing Problem (VRP) is already exists for a long time and is one of NP-hard problem. Modified Pointer Network (MPN) and Multi-Agent Attention Model (MAAM) are able to solve Capacitated VRP and Multi-VRP with Soft Time Window respectively with a good performance. In this research, we modify MPN and MAAM so that the architectures are able to recieve MDVRPTW with difference in total vehicles by modifying both architecture to be a multi-agent. With the same hyperparameter, MPN and MAAM with multi-agent decoding formulation shown outperforming MPN and MAAM with single agent in 18 out of 20 dataset.

Kata Kunci : Vehicle Routing Problem, Reinforcement Learning, Pointer Network, Transformer, Multi-Agent