IMPLEMENTASI ALGORITMA PARTICLE SWARM OPTIMIZATION UNTUK PENENTUAN RUTE LAYAK PADA PICKUP AND DELIVERY TRAVELLING SALESMAN PROBLEM WITH HANDLING COST

Ikhlasul Amallynda

Abstract


Pickup and delivery travellig salesman problem (PDTSPH) merupakan salah satu variasi permasalahan PDTSP dengan mempertimbangkan biaya bongkar muat. Dalam PDTSPH, kendaraan tunggal yang berbasis di depot pusat harus memenuhi satu set permintaan. Setiap permintaan menentukan rencana  pemuatan dan pembongkaran barang dari lokasi penjemputan ke lokasi pengiriman tertentu. Penelitian ini menggunakan dua skenario kebijakan pemuatan ulang (reload policy) barang ke dalam kontainer. Pada skenario pertama kami berasumsi bahwa urutan pemuatan ulang (reload) adalah kebalikan dari urutan pembongkaran (unloading). Sedangkan pada skenario kedua, barang yang dimuat ulang diposisikan sesuai dengan urutan lokasi pengiriman selanjutnya. Penelitian ini berfokus pada pengembangan algoritma partikel swarm optimization (PSO) untuk menentukan rute layak pada kasus PDTSPH dengan waktu komputasi yang lebih singkat. Dalam penelitian ini, PSO dikembangkan berdasarkan GLNPSO, yakni sebuah varian algoritma PSO yang memiliki struktur pembelajaran sosial yang lebih baik dari PSO standar dengan menggabungkan beberapa posisi terbaik. Pencarian solusi dan metode pengkodingan berbasis algoritma  heuristik large neighborhood search (LNS) digunakan dalam mengimplementasikan PSO untuk menyelesaikan PDTSPH. Percobaan numerik dilakukan dengan menggunakan beberapa data set berukuran kecil dengan parameter-parameter yang telah ditentukan sebelumnya. Hasil percobaan numerik menunjukkan bahwa algoritma yang diusulkan mampu memberikan solusi yang optimal untuk beberapa kompleksitas masalah dengan waktu komputasi yang lebih singkat.Pickup and delivery travellig salesman problem (PDTSPH) merupakan salah satu variasi permasalahan PDTSP dengan mempertimbangkan biaya bongkar muat. Dalam PDTSPH, kendaraan tunggal yang berbasis di depot pusat harus memenuhi satu set permintaan. Setiap permintaan menentukan rencana  pemuatan dan pembongkaran barang dari lokasi penjemputan ke lokasi pengiriman tertentu. Penelitian ini menggunakan dua skenario kebijakan pemuatan ulang (reload policy) barang ke dalam kontainer. Pada skenario pertama kami berasumsi bahwa urutan pemuatan ulang (reload) adalah kebalikan dari urutan pembongkaran (unloading). Sedangkan pada skenario kedua, barang yang dimuat ulang diposisikan sesuai dengan urutan lokasi pengiriman selanjutnya. Penelitian ini berfokus pada pengembangan algoritma partikel swarm optimization (PSO) untuk menentukan rute layak pada kasus PDTSPH dengan waktu komputasi yang lebih singkat. Dalam penelitian ini, PSO dikembangkan berdasarkan GLNPSO, yakni sebuah varian algoritma PSO yang memiliki struktur pembelajaran sosial yang lebih baik dari PSO standar dengan menggabungkan beberapa posisi terbaik. Pencarian solusi dan metode pengkodingan berbasis algoritma  heuristik large neighborhood search (LNS) digunakan dalam mengimplementasikan PSO untuk menyelesaikan PDTSPH. Percobaan numerik dilakukan dengan menggunakan beberapa data set berukuran kecil dengan parameter-parameter yang telah ditentukan sebelumnya. Hasil percobaan numerik menunjukkan bahwa algoritma yang diusulkan mampu memberikan solusi yang optimal untuk beberapa kompleksitas masalah dengan waktu komputasi yang lebih singkat.

Keywords


Routing, Particle Swarm Optimization, Pickup and Delivery Travelling Salesman Problem with Handling Cost

Full Text:

PDF

References


M. Veenstra, K. J. Roodbergen, I. F. A. Vis, and L. C. Coelho, “The pickup and delivery traveling salesman problem with handling costs,” Eur. J. Oper. Res., vol. 257, no. 1, pp. 118–132, Feb. 2017.

Y. Marinakis and M. Marinaki, “A Hybrid Multi-Swarm Particle Swarm Optimization algorithm for the Probabilistic Traveling Salesman Problem,” Comput. Oper. Res., vol. 37, no. 3, pp. 432–442, Mar. 2010.

M. Mahi, Ö. K. Baykan, and H. Kodaz, “A new hybrid method based on Particle Swarm Optimization, Ant Colony Optimization and 3-Opt algorithms for Traveling Salesman Problem,” Appl. Soft Comput., vol. 30, pp. 484–490, May 2015.

M.-C. Chen, Y.-H. Hsiao, R. Himadeep Reddy, and M. K. Tiwari, “The Self-Learning Particle Swarm Optimization approach for routing pickup and delivery of multiple products with material handling in multiple cross-docks,” Transp. Res. Part E Logist. Transp. Rev., vol. 91, pp. 208–226, Jul. 2016.

H. Zhou, M. Song, and W. Pedrycz, “A comparative study of improved GA and PSO in solving multiple traveling salesmen problem,” Appl. Soft Comput., vol. 64, pp. 564–580, Mar. 2018.

Y. Zhong, J. Lin, L. Wang, and H. Zhang, “Discrete comprehensive learning particle swarm optimization algorithm with Metropolis acceptance criterion for traveling salesman problem,” Swarm Evol. Comput., Mar. 2018.

B. Santosa and P. Willy, Metoda Metaheuristik: Konsep dan Implementasi. Surabaya, Indonesia: Guna Widya, 2011.

P. Shaw, “Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems,” in Principles and Practice of Constraint Programming --- CP98, 1998, pp. 417–431.

N. Azi, M. Gendreau, and J.-Y. Potvin, “An adaptive large neighborhood search for a vehicle routing problem with multiple routes,” Comput. Oper. Res., vol. 41, pp. 167–173, Jan. 2014.

J.-F. Côté, M. Gendreau, and J.-Y. Potvin, “Large neighborhood search for the pickup and delivery traveling salesman problem with multiple stacks,” Networks, vol. 60, no. 1, pp. 19–30.

R. Masson, F. Lehuédé, and O. Péton, “An Adaptive Large Neighborhood Search for the Pickup and Delivery Problem with Transfers,” Transp. Sci., vol. 47, no. 3, pp. 344–355, 2013.

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by Simulated Annealing,” Science (80-. )., vol. 220, no. 4598, pp. 671–680, 1983.

S. Ropke and D. Pisinger, “An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows,” Transp. Sci., vol. 40, no. 4, pp. 455–472, 2006.




DOI: https://doi.org/10.22219/sentra.v0i4.2281

Refbacks

  • There are currently no refbacks.


Seketariat

Fakultas Teknik

Universitas Muhammadiyah Malang Kampus III

Jl. Raya Tlogomas 246 Malang, 65144