A Simulated Annealing Heuristic for Blood Pick-Up Routing Problem

TITI ISWARI, Anna Maria Sri Asih, S.T., M.M., M.Sc., Ph.D.

2016 | Tesis | S2 Teknik Industri

Blood service operation adalah komponen penting dari sistem kesehatan di seluruh dunia. Mengangkut produk dengan waktu terbatas seperti darah menghadirkan tantangan spesifik dan unik. Sebagai produk yang mudah rusak dan memiliki umur tertentu, produk tersebut harus digunakan atau diolah sebelum waktu umurnya berakhir. Jika waktu pembusukan terlampaui, maka produk tersebut harus dibuang. Blood Pick-up Routing Problem (BPRP) berfokus pada kegiatan upstream logistik darah, mulai dari pengumpulan kantong darah di tempat donasi yang tetap sampai ke pengiriman kantong darah ke bank darah. BPRP merupakan ekstensi dari vehicle routing problem dengan time windows. Dalam BPRP, rute dibangun untuk meminimalkan total jarak dengan mempertimbangkan batasan time window dan batasan waktu umur darah. Setiap tempat donasi memiliki waktu pick-up untuk kendaraan dapat mulai mengumpulkan darah di lokasi. Kantong darah tersebut harus diangkut kembali ke bank darah sebelum waktu tutup bank dan waktu pembusukan darah tersebut. Penelitian ini mengembangkan model matematika untuk BPRP. Karena CPLEX hanya dapat menyelesaikan model untuk small instance, penelitian ini mengembangkan pendekatan berbasis heuristik untuk memecahkan large instance, yaitu Simulated Annealing dengan strategi restart (SA_RS). Strategi restart dikembangkan untuk diversifikasi proses pencarian solusi dan menghindari terjebak pada local optimum. SA_RS ini kemudian diuji pada instance VRPTW dari Solomon dan pada instance BPRP. Hasil komputasi menunjukkan bahwa SA_RS menghasilkan performa yang baik dalam menyelesaikan permasalahan BPRP.

Blood service operation is a key component of healthcare systems all over the world. Transporting time-sensitive products like blood presents a specific and unique challenge, as such perishable products that have a spoilage time. If the spoilage time is exceeded, then the product should be discarded. The blood pick-up routing problem (BPRP) focuses on the upstream activities of blood logistics, starting from collection or pick-up of blood at fixed donation sites and then delivering the blood bags to the blood bank. BPRP is an extension of the well-known vehicle routing problem with time windows. In BPRP, the routes are constructed to minimize total distances while at the same time observing time window constraints of donation sites and the spoilage time constraint of the blood. More specifically, each donation site has its pick-up time window during which vehicles can start collecting blood at the site. The blood must be transported back to the blood bank before the bank�s closing time and the blood�s spoilage time. This study develops a mathematical programming model for BPRP. CPLEX can only solve the model to optimality for small instances, so this study proposes a simulated annealing with restart strategy (SA_RS) based heuristic approach to solve large BPRP instances. The restart strategy is developed to diversify the search process in order to avoid getting trapped at a local optimum. The proposed SA_RS is tested on VRPTW instances from Solomon, and then on BPRP instances. Computational results show that the proposed SA_RS heuristic performs well on solving BPRP.

Kata Kunci : blood pick-up, time window, spoilage time, simulated annealing, vehicle routing