Multi-sample Pareto Hyper Networks with Attention Mechanism for Solving Bi-objective Time-dependent Pickup and Delivery Problem with Late Penalties

KADEK GEMILANG SANTIYUDA, Prof. Drs. Retantyo Wardoyo, M.Sc., Ph.D.

2024 | Disertasi | S3 Ilmu Komputer

Penelitian ini membahas penyelesaian permasalahan bi-objective time-dependent pickup and delivery problem with late penalties (TDPDPLP). Permodelan tingkat kemacetan lalu lintas ke dalam formulasi permasalahan dalam bentuk waktu tempuh yang bergantung pada waktu sangatlah penting untuk mengurangi perbedaan kualitas solusi ketika mengaplikasikan metode optimisasi di dunia nyata. Penelitian ini mengusulkan sebuah metode berbasis multi-objective reinforcement learning (MORL) dengan hypernetwork dan mekanisme attention untuk menyelesaikan bi-objective TDPDPLP. Metode yang diusulkan dapat menghasilkan sebuah aproksimasi dari Pareto optimal front (POF) secara instan setelah pelatihan. Studi yang dilakukan juga menunjukkan bahwa menghapus koordinat dari fitur menghasilkan model yang lebih sederhana yang menghemat waktu pelatihan dan meningkatkan kualitas dari solusi yang dihasilkan. Model yang telah dilatih digunakan untuk menyelesaikan kasus-kasus permasalahan nyata dari Kota Barcelona, Berlin dan Porto-Alegre. Performa metode yang diusulkan dievaluasi dengan mengukur hypervolume (HV) dan epsilon+ dari POF yang dihasilkan. Hasil eksperimen menunjukkan bahwa metode yang diusulkan memiliki performa yang lebih baik dibandingkan dengan metode pembanding berbasis multi-objective evolutionary algorithms (MOEA) dan MORL lainnya. Metode yang diusulkan menghasilkan POF dalam beberapa menit, sedangkan metode-metode MOEA memerlukan waktu beberapa jam. Selain itu, metode yang diusulkan juga mampu menghasilkan POF dengan kualitas yang baik pada kasus-kasus permasalahan dengan karakteristik dan kota yang berbeda dari kasus-kasus permasalahan yang digunakan pada pelatihan.

This study addresses the bi-objective time-dependent pickup and delivery problem with late penalties (TDPDPLP). Incorporating time-dependent travel time into the problem formulation to model traffic congestion is critical,  especially for problems with time-related costs, to decrease the difference in the projected quality of solutions when applying optimization methods in the real-world. This study proposes a multi-objective reinforcement learning (MORL)-based method with hypernetwork and attention mechanism to solve the bi-objective TDPDPLP. The proposed method can generate an approximation of Pareto optimal front (POF) instantly after offline training. The conducted ablation study also showed that discarding coordinates from the features results in a simpler model that saves several hours of training while improving the quality of the solutions. The performance of the trained model is evaluated on real-world-based instances from Barcelona, Berlin, and Porto-Alegre. The performance of the proposed method is evaluated based on the hypervolume (HV) and epsilon+ of the generated POF approximation compared to several well-known multi-objective evolutionary algorithms (MOEA) and nother MORL method named preference-conditioned multi-objective combinatorial  optimization (P-MOCO). The experiments showed that the proposed method outperforms both the MORL and MOEA baselines on all test instances. The trained method only needs  minutes to generate a POF approximation, while the MOEAs require hours. Furthermore, the trained method also generalizes well on different characteristics of problem instances and even performs well on instances from cities other than the city in the training instances.

Kata Kunci : Pickup and delivery problem, Multi-objective, Deep reinforcement learning, Attention mechanism, Hypernetwork