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


Iwan Aang Soenandi(1*), Joice Joice(2), Budi Marpaung(3),

(1) Krida Wacana Christian University
(2) Krida Wacana Christian University
(3) Krida Wacana Christian University
(*) Corresponding Author

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.


Keywords


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

Full Text:

PDF

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.


Article Metrics

Abstract view : 61 times| PDF : 27 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