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

Authors

  • Anak Agung Ngurah Perwira Redi Scopus ID = 56436570600, Universitas Pertamina, Indonesia, Subject Area: Operation Research, Metaheuristic, Vehicle Routing Problem. http://orcid.org/0000-0003-3520-5260
  • Anak Agung Ngurah Agung Redioka STIMIK Primakara

DOI:

https://doi.org/10.30656/jsmi.v3i1.1473

Keywords:

Bike-Sharing, Simulated Annealing, Static Repositioning Problem

Abstract

The public bike-sharing system has a problem where the number of bicycles at the docking station needs to be balanced to ensure system user satisfaction. The usual solution is to distribute bicycles so that system users can still park for locations that are usually full of bicycles or pick up bicycles at locations that normally lack bicycles. The purpose of solving this problem is to get a vehicle route with the total operating costs of the vehicle. The full vehicle operating costs are associated with the full time taken by the vehicle to distribute the bicycle. Besides, there are also penalty fees related to the lack of bikes or parking slots at the time of operation of the public bike-sharing facility. In this study, two variations of the simulated annealing (SA) algorithm were developed to solve the SBRP problem called SA_BF and SA_CF. The data used comes from a Velib bike-sharing system case study in Paris, France. The results of the experiment show that both the SA_BF and SA_CF algorithms succeeded in solving SBRP. This algorithm has an average difference of 2.21% and 0.36% of the Arc-Indexed algorithm (AI) from previous studies in the first dataset. As for the second dataset, Tabu Search algorithm, SA_BF and SA_CF obtained an average difference of 0.65%, 1.08% and 0.38% of the optimal results.

Downloads

Download data is not yet available.

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.

Downloads

Published

2019-07-31

How to Cite

[1]
A. A. N. P. Redi and A. A. N. A. Redioka, “Algoritma Simulated Annealing untuk Optimasi Rute Kendaraan dan Pemindahan Lokasi Sepeda pada Sistem Public Bike Sharing”, j. sist. manaj. ind., vol. 3, no. 1, pp. 50–58, Jul. 2019.

Issue

Vol. 3 No. 1 (2019)

Section

Articles

License

All articles in Jurnal Sistem dan Manajemen Industri can be disseminated provided they include the identity of the article and the source of the article Jurnal Sistem dan Manajemen Industri. The publisher is not responsible for the contents of the article. The content of the article is the sole responsibility of the author

Creative Commons License

Jurnal Sistem dan Manajemen Industri is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Crossref
Scopus
Google Scholar
Europe PMC

Most read articles by the same author(s)