Optimasi Capacitated Vehicle Routing Problem with Time Windows dengan Menggunakan Ant Colony Optimization

Authors

  • Iwan Aang Soenandi Krida Wacana Christian University http://orcid.org/0000-0002-1492-4867
  • Joice Joice Krida Wacana Christian University
  • Budi Marpaung Krida Wacana Christian University

DOI:

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

Keywords:

Ant Colony Optimization, Capacitated Vehicle Routing with Time Windows, Optimization, Vehicle Routing Problem

Abstract

In recent years, minimization of logistics and transportation costs has become essential for manufacturing companies to increase profits. One thing is done to reduce logistics and transportation costs by optimizing the route of taking or transporting components from each supplier. Route optimization to minimize total transportation costs is a problem that often finds in Vehicle Routing Problems (VRP). Problem Capacitated Vehicle Routing with Time Windows (CVRPTW) is one variant of VRP that considers the vehicle capacity and the service period of each vehicle. CVRPTW is a Non-Polynomial Hard (NP-Hard) problem that requires an efficient and effective algorithm in solving problems that occur in this automotive company. This study uses the Ant Colony Optimization (ACO) algorithm by testing using several parameters to solve the CVRPTW problem. The test results using the ACO algorithm obtained a faster route compared to the method applied by the company.

Downloads

Download data is not yet available.

Author Biography

Iwan Aang Soenandi, Krida Wacana Christian University

Industrial Engineering Department

References

[1] A. Ahkamiraad and Y. Wang, “Capacitated and multiple cross-docked vehicle routing problem with pickup, delivery, and time windows,†Comput. Ind. Eng., vol. 119, pp. 76–84, May 2018, doi: 10.1016/j.cie.2018.03.007.

[2] J. Pekar, I. Brezina, and Z. Cickova, “Synchronization of Capacitated Vehicle Routing Problem among Periods 1,†Ekon. Cas., vol. 65, no. 1, pp. 66–78, 2017, available at: http://cejsh.icm.edu.pl/cejsh/element/bwmeta1.element.cejsh-8259290f-b6b0-43fd-9c72-6daf6781c60d.

[3] L. Guimarães, P. Amorim, F. Sperandio, F. Moreira, and B. Almada-Lobo, “Annual Distribution Budget in the Beverage Industry: A Case Study,†Interfaces (Providence)., vol. 44, no. 6, pp. 605–626, Dec. 2014, doi: 10.1287/inte.2014.0747.

[4] S. Rahman and Y.-C. Jim Wu, “Logistics outsourcing in China: the manufacturerâ€cumâ€supplier perspective,†Supply Chain Manag. An Int. J., vol. 16, no. 6, pp. 462–473, Sep. 2011, doi: 10.1108/13598541111171156.

[5] A. Hübl, H. Jodlbauer, and K. Altendorfer, “Influence of dispatching rules on average production lead time for multi-stage production systems,†Int. J. Prod. Econ., vol. 144, no. 2, pp. 479–484, Aug. 2013, doi: 10.1016/j.ijpe.2013.03.020.

[6] C.-K. Ting and X.-L. Liao, “The selective pickup and delivery problem: Formulation and a memetic algorithm,†Int. J. Prod. Econ., vol. 141, no. 1, pp. 199–211, Jan. 2013, doi: 10.1016/j.ijpe.2012.06.009.

[7] A. S. White and M. Censlive, “An alternative state-space representation for APVIOBPCS inventory systems,†J. Manuf. Technol. Manag., vol. 24, no. 4, pp. 588–614, Apr. 2013, doi: 10.1108/17410381311327413.

[8] G. Guizzi, R. Revetria, D. Chiocca, and E. Romano, “A dynamic milk run in WEEE reverse logistics,†Adv. Comput. Sci., pp. 478–484, 2012, available at: https://pdfs.semanticscholar.org/3768/d19f732fe04493df8ffcf7c5d550850da169.pdf.

[9] O. A. W. Riyanto and B. Santosa, “ACO-LS Algorithm for Solving No-wait Flow Shop Scheduling Problem,†in International Conference on Soft Computing, Intelligence Systems, and Information Technology, Springer, 2015, pp. 89–97, doi: 10.1007/978-3-662-46742-8_8.

[10] M. Dorigo and T. Stützle, “Ant Colony Optimization: Overview and Recent Advances,†in Handbook of metaheuristics, Springer, 2019, pp. 311–351, doi: 10.1007/978-3-319-91086-4_10.

[11] G. Fuellerer, K. F. Doerner, R. F. Hartl, and M. Iori, “Ant colony optimization for the two-dimensional loading vehicle routing problem,†Comput. Oper. Res., vol. 36, no. 3, pp. 655–673, Mar. 2009, doi: 10.1016/j.cor.2007.10.021.

[12] B. Yu and Z. Z. Yang, “An ant colony optimization model: The period vehicle routing problem with time windows,†Transp. Res. Part E Logist. Transp. Rev., vol. 47, no. 2, pp. 166–181, Mar. 2011, doi: 10.1016/j.tre.2010.09.010.

[13] A. E. Rizzoli, R. Montemanni, E. Lucibello, and L. M. Gambardella, “Ant colony optimization for real-world vehicle routing problems,†Swarm Intell., vol. 1, no. 2, pp. 135–151, Nov. 2007, doi: 10.1007/s11721-007-0005-x.

[14] S.-H. Xu, J.-P. Liu, F.-H. Zhang, L. Wang, and L.-J. Sun, “A Combination of Genetic Algorithm and Particle Swarm Optimization for Vehicle Routing Problem with Time Windows,†Sensors, vol. 15, no. 9, pp. 21033–21053, Aug. 2015, doi: 10.3390/s150921033.

[15] S. N. Kumar and R. Panneerselvam, “A survey on the vehicle routing problem and its variants,†Intell. Inf. Manag., vol. 4, no. 03, pp. 66–74, 2012, available at: https://pdfs.semanticscholar.org/ea41/6f29b6aa4bb17abddfbb82272e2cb30d6af3.pdf.

[16] M. Dorigo and C. Blum, “Ant colony optimization theory: A survey,†Theor. Comput. Sci., vol. 344, no. 2–3, pp. 243–278, Nov. 2005, doi: 10.1016/j.tcs.2005.05.020.

[17] U. Teschemacher and G. Reinhart, “Ant Colony Optimization Algorithms to Enable Dynamic Milkrun Logistics,†Procedia CIRP, vol. 63, pp. 762–767, 2017, doi: 10.1016/j.procir.2017.03.125.

[18] S. Gao, Y. Wang, J. Cheng, Y. Inazumi, and Z. Tang, “Ant colony optimization with clustering for solving the dynamic location routing problem,†Appl. Math. Comput., vol. 285, pp. 149–173, Jul. 2016, doi: 10.1016/j.amc.2016.03.035.

[19] B. Yao, Q. Yan, M. Zhang, and Y. Yang, “Improved artificial bee colony algorithm for vehicle routing problem with time windows,†PLoS One, vol. 12, no. 9, pp. 1–18, Sep. 2017, doi: 10.1371/journal.pone.0181275.

[20] S.-H. Huang, Y.-H. Huang, C. A. Blazquez, and G. Paredes-Belmar, “Application of the ant colony optimization in the resolution of the bridge inspection routing problem,†Appl. Soft Comput., vol. 65, pp. 443–461, Apr. 2018, doi: 10.1016/j.asoc.2018.01.034.

[21] S. Mazzeo and I. Loiseau, “An Ant Colony Algorithm for the Capacitated Vehicle Routing,†Electron. Notes Discret. Math., vol. 18, pp. 181–186, Dec. 2004, doi: 10.1016/j.endm.2004.06.029.

[22] N. Rouky, J. Boukachour, D. Boudebous, and A. E. H. Alaoui, “A Robust Metaheuristic for the Rail Shuttle Routing Problem with Uncertainty: A Real Case Study in the Le Havre Port,†Asian J. Shipp. Logist., vol. 34, no. 2, pp. 171–187, Jun. 2018, doi: 10.1016/j.ajsl.2018.06.014.

Downloads

Published

2019-07-31

How to Cite

[1]
I. A. Soenandi, J. Joice, and B. Marpaung, “Optimasi Capacitated Vehicle Routing Problem with Time Windows dengan Menggunakan Ant Colony Optimization”, j. sist. manaj. ind., vol. 3, no. 1, pp. 59–66, 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)