Algoritma Simulated Annealing untuk Optimasi Rute Kendaraan dan Pemindahan Lokasi Sepeda pada Sistem Public Bike Sharing


Anak Agung Ngurah Perwira Redi(1*), Anak Agung Ngurah Agung Redioka(2),

(1) Scopus ID = 56436570600, Universitas Pertamina, Indonesia, Subject Area: Operation Research, Metaheuristic, Vehicle Routing Problem.
(2) STIMIK Primakara
(*) Corresponding Author

Abstract


Sistem public bike sharing memiliki permasalahan dimana jumlah sepeda pada docking station (tempat parkir sepeda) perlu diseimbangkan untuk menjamin kepuasan pengguna sistem. Untuk itu solusi yang sering dilakukan adalah distribusi sepeda agar pengguna sistem tetap dapat parkir untuk lokasi yang biasanya penuh dengan sepeda ataupun mengambil sepeda pada lokasi yang biasanya kekurangan sepeda. Tujuan dari pemecahan masalah ini adalah untuk mendapatkan rute kendaraan dengan total biaya operasi dari kendaraan tersebut. Total biaya operasi kendaraan diasosiasikan dengan total waktu yang dibutuhkan kendaraan untuk melakukan distribusi sepeda. Selain itu terdapat juga biaya penalti yang berasosiasi dengan kekurangan jumlah sepeda ataupun slot parkir pada waktu operasi dari fasilitas public bike-sharing. Dalam penelitian ini, dua variasi algoritma simulated annealing (SA) dikembangkan untuk menyelesaikan permasalahan SBRP disebut dengan SA_BF dan SA_CF. Data yang digunakan berasal dari studi kasus milik Velib bike sharing system di Paris, Prancis. Hasil dari eksperimen menunjukkan bahwa kedua algoritma SA_BF dan SA_CF berhasil dengan baik menghasilkan solusi untuk SBRP. Algoritma ini memiliki selisih rata-rata 2.21% dan 0.36% terhadap algoritma Arc-Indexed (AI) dari penelitian sebelumnya pada dataset pertama. Sedangkan untuk rata-dataset kedua, algoritma Tabu Search, SA_BF dan SA_CF memperoleh selisih rata-rata 0.65%, 1.08% dan 0.38%  terhadap hasil optimal.


Keywords


Bike-Sharing; Simulated Annealing; Static Repositioning Problem

Full Text:

PDF

References


[1] S. D. Parkes, G. Marsden, S. A. Shaheen, and A. P. Cohen, “Understanding the diffusion of public bikesharing systems: evidence from Europe and North America,” J. Transp. Geogr., vol. 31, pp. 94–103, Jul. 2013, doi: 10.1016/j.jtrangeo.2013.06.003.

[2] C.-C. Hsu, J. J. H. Liou, H.-W. Lo, and Y.-C. Wang, “Using a hybrid method for evaluating and improving the service quality of public bike-sharing systems,” J. Clean. Prod., vol. 202, pp. 1131–1144, Nov. 2018, doi: 10.1016/j.jclepro.2018.08.193.

[3] R. Alvarez-Valdes et al., “Optimizing the level of service quality of a bike-sharing system,” Omega, vol. 62, pp. 163–175, Jul. 2016, doi: 10.1016/j.omega.2015.09.007.

[4] T. Raviv, M. Tzur, and I. A. Forma, “Static repositioning in a bike-sharing system: models and solution approaches,” EURO J. Transp. Logist., vol. 2, no. 3, pp. 187–229, Aug. 2013, doi: 10.1007/s13676-012-0017-6.

[5] J.-R. Lin and T.-H. Yang, “Strategic design of public bicycle sharing systems with service level constraints,” Transp. Res. Part E Logist. Transp. Rev., vol. 47, no. 2, pp. 284–294, Mar. 2011, doi: 10.1016/j.tre.2010.09.004.

[6] T. Raviv and O. Kolka, “Optimal inventory management of a bike-sharing station,” IIE Trans., vol. 45, no. 10, pp. 1077–1093, Oct. 2013, doi: 10.1080/0740817X.2013.770186.

[7] M. Rainer-Harbach, P. Papazek, B. Hu, and G. R. Raidl, “Balancing Bicycle Sharing Systems: A Variable Neighborhood Search Approach,” in European conference on evolutionary computation in combinatorial optimization, Springer, 2013, pp. 121–132, doi: 10.1007/978-3-642-37198-1_11.

[8] H. M. Espegren, J. Kristianslund, H. Andersson, and K. Fagerholt, “The Static Bicycle Repositioning Problem - Literature Survey and New Formulation,” in International Conference on Computational Logistics, Springer, 2016, pp. 337–351, doi: 10.1007/978-3-319-44896-1_22.

[9] I. A. Forma, T. Raviv, and M. Tzur, “A 3-step math heuristic for the static repositioning problem in bike-sharing systems,” Transp. Res. Part B Methodol., vol. 71, pp. 230–247, Jan. 2015, doi: 10.1016/j.trb.2014.10.003.

[10] C. Kloimüllner, P. Papazek, B. Hu, and G. R. Raidl, “Balancing Bicycle Sharing Systems: An Approach for the Dynamic Case,” in European Conference on Evolutionary Computation in Combinatorial Optimization, Springer, 2014, pp. 73–84, doi: 10.1007/978-3-662-44320-0_7.

[11] L. Caggiani and M. Ottomanelli, “A Dynamic Simulation based Model for Optimal Fleet Repositioning in Bike-sharing Systems,” Procedia - Soc. Behav. Sci., vol. 87, pp. 203–210, Oct. 2013, doi: 10.1016/j.sbspro.2013.10.604.

[12] A. A. N. Perwira Redi, M. F. N. Maghfiroh, and V. F. Yu, “Discrete Particle Swarm Optimization with Path-Relinking for Solving the Open Vehicle Routing Problem with Time Windows,” in Proceedings of the Institute of Industrial Engineers Asian Conference 2013, Singapore: Springer Singapore, 2013, pp. 853–859, doi: 10.1007/978-981-4451-98-7_102.

[13] V. F. Yu, P. Jewpanya, S.-W. Lin, and A. A. N. P. Redi, “Team orienteering problem with time windows and time-dependent scores,” Comput. Ind. Eng., vol. 127, pp. 213–224, Jan. 2019, doi: 10.1016/j.cie.2018.11.044.

[14] V. F. Yu, P. Jewpanya, and A. A. N. P. Redi, “Open vehicle routing problem with cross-docking,” Comput. Ind. Eng., vol. 94, pp. 6–17, Apr. 2016, doi: 10.1016/j.cie.2016.01.018.

[15] N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, “Equation of State Calculations by Fast Computing Machines,” J. Chem. Phys., vol. 21, no. 6, pp. 1087–1092, Jun. 1953, doi: 10.1063/1.1699114.

[16] F. Y. Vincent, A. A. N. P. Redi, Y. A. Hidayat, and O. J. Wibowo, “A simulated annealing heuristic for the hybrid vehicle routing problem,” Appl. Soft Comput., vol. 53, pp. 119–132, 2017, doi: 10.1016/j.asoc.2016.12.027.

[17] S.-W. Lin, V. F. Yu, and S.-Y. Chou, “Solving the truck and trailer routing problem based on a simulated annealing heuristic,” Comput. Oper. Res., vol. 36, no. 5, pp. 1683–1692, May 2009, doi: 10.1016/j.cor.2008.04.005.

[18] S. C. Ho and W. Y. Szeto, “Solving a static repositioning problem in bike-sharing systems using iterated tabu search,” Transp. Res. Part E Logist. Transp. Rev., vol. 69, pp. 180–198, Sep. 2014, doi: 10.1016/j.tre.2014.05.017.

[19] V. F. Yu, A. A. N. P. Redi, P. Jewpanya, A. Lathifah, M. F. N. Maghfiroh, and N. A. Masruroh, “A Simulated Annealing Heuristic for the Heterogeneous Fleet Pollution Routing Problem,” in Environmental Sustainability in Asian Logistics and Supply Chains, Singapore: Springer Singapore, 2019, pp. 171–204, doi: 10.1080/0305215X.2018.1437153.

[20] V. F. Yu, S. S. Purwanti, A. A. N. P. Redi, C.-C. Lu, S. Suprayogi, and P. Jewpanya, “Simulated annealing heuristic for the general share-a-ride problem,” Eng. Optim., vol. 50, no. 7, pp. 1178–1197, Jul. 2018, doi: 10.1080/0305215X.2018.1437153.


Article Metrics

Abstract view : 45 times| PDF : 19 times

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Jurnal Sistem dan Manajemen Industri have been indexed on:

                                                        

 

Jurnal Sistem dan Manajemen Industri

web
analytics View My Stats