Main Article Content

Farhanna Mari Wayan Firdaus Mahmudy Purnomo Budi Santoso


In the industrial sector, in order to increase the company's competitive profit and ratio, must be able to suppress as much expenditure as possible. Product distribution is one of the logistics processes in the industry which consumes the most costs. Products must be distributed to customers in different locations and also with varying requests. The problem belongs to Capacitated Vehicle Routing Problem (CVRP) that is considered as one of the complex combinatorial optimization problems included in the NP-Hard Problem category, which is a problem that requires difficult computation and a lot of time along with the increasing size of the problem data. So, in this study improvisation will be carried out in the form of modifying the simulated annealing method to solve the combinatorial problem so that the optimal distance in the case of distribution will be obtained. In addition, in this study a comparison will be made between basic simulated annealing and also improved simulated annealing. Based on the results of the research it is proven that Improved Simulated Annealing can provide a better solution.


Download data is not yet available.

Article Details

How to Cite
MARI, Farhanna; MAHMUDY, Wayan Firdaus; SANTOSO, Purnomo Budi. AN IMPROVED SIMULATED ANNEALING FOR THE CAPACITATED VEHICLE ROUTING PROBLEM (CVRP). Jurnal Ilmiah Kursor, [S.l.], v. 9, n. 3, p. 117-126, feb. 2019. ISSN 2301-6914. Available at: <>. Date accessed: 24 mar. 2019. doi:


[1] A. Yeboah, A. Owusu, S. Boakye, and S. Owusu-Mensah, “Effective Distribution Management, a Pre-Requisite for Retail Operations: A Case of Poku Trading,” Eur. J. Bus. Innov. Res., vol. 1, no. 3, pp. 28–44, 2013.
[2] X. Yang, “A Review of Distribution Related Problems in Logistics and Supply Chain Research,” Int. J. Supply Chain Manag., vol. 2, no. 4, pp. 1–8, 2013.
[3] S. Ketola, “Developing a Distribution Pricing Model for the Case Company,” Int. J. Supply Chain Manag., 2017.
[4] A. Holzapfel, A. Hübner, H. Kuhn, and M. G. Sternbeck, “Delivery Pattern and Transportation Planning in Grocery Retailing,” Eur. J. Oper. Res., vol. 252, no. 1, pp. 54–68, 2016.
[5] B. Alexander and S. Sergey, “A Metaheuristic Approach for the Problem of Motor Fuel Distribution,” Procedia Comput. Sci., vol. 31, pp. 143–150, 2014.
[6] P. Campelo, F. Neves-Moreira, P. Amorim, and B. Almada-Lobo, “Consistent Vehicle Routing Problem with Service Level Agreements: A Case Study in the Pharmaceutical Distribution Sector,” Eur. J. Oper. Res., vol. 273, no. 1, pp. 131–145, 2019.
[7] E. Uchoa, D. Pecin, A. Pessoa, M. Poggi, T. Vidal, and A. Subramanian, “New Benchmark Instances for the Capacitated
Vehicle Routing Problem,” Eur. J. Oper. Res., vol. 257, no. 3, pp. 845–858, 2017.
[8] H. Awad, R. Elshaer, A. AbdElmo’ez, and G. Nawara, “An Effective Genetic Algorithm for Capacitated Vehicle Routing Problem,” p. 11, 2018.
[9] C. Pornsing, “A Particle Swarm Optimization for the Vehicle Routing Problem,” Thesis, University of Rhode Island, 2014.
[10]R. Baldacci, A. Mingozzi, and R. Roberti, “Recent Exact Algorithms for Solving the Vehicle Routing Problem Under Capacity and Time Window Constraints,” Eur. J. Oper. Res., vol. 218, no. 1, pp. 1–6, 2012.
[11]F. Y. Vincent, A. 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.
[12]F. Y. Vincent and S.-Y. Lin, “A Simulated Annealing Heuristic for the Open LocationRouting Problem,” Comput. Oper. Res., vol. 62, pp. 184–196, 2015.
[13]Y. P. Anggodo, A. K. Ariyani, M. K. Ardi, and W. F. Mahmudy, “Optimization of Multi-Trip Vehicle Routing Problem with Time Windows Using Genetic Algorithm,” J. Environ. Eng. Sustain. Technol., vol. 3, no. 2, pp. 92–97, 2017.
[14]L. Wei, Z. Zhang, D. Zhang, and S. C. Leung, “A Simulated Annealing Algorithm for the Capacitated Vehicle Routing Problem with two-dimensional loading constraints,” Eur. J. Oper. Res., vol. 265, no. 3, pp. 843–859, 2018.
[15]W. F. Mahmudy, “Improved Simulated Annealing for Optimization of Vehicle Routing Problem with Time Windows (VRPTW),” Kursor, vol. 7, no. 3, 2016.
[16]G. B. Dantzig and J. H. Ramser, “The Truck Dispatching Problem,” Manag. Sci., vol. 6, no. 1, pp. 80–91, 1959.
[17]P. Augerat, J. M. Belenguer, E. Benavent, A. Corberán, D. Naddef, and G. Rinaldi, “Computational Results with a Branch-andCut Code for the Capacitated Vehicle Routing Problem,” Available at:
3161. May 2014. pp. 1–24, 1995.
[18]S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by Simulated Annealing,” science, vol. 220, no. 4598, pp. 671–680, 1983.
[19]S. Johnson, J. Han, Y. Liu, L. Chen, and X. Wu, “Hybrid Approach with Improved Genetic Algorithm and Simulated Annealing for Thesis Sampling,” Future Internet, vol. 10, no. 8, p. 71, 2018.