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


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.


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 : 160 times| PDF : 69 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

web
analytics View My Stats