A population based simulated annealing algorithm for capacitated vehicle routing problem

The Vehicle Routing Problem VRP is one of the most discussed and researched topics nowadays. The VRP is briefly defined as the problem of identifying the best route to reduce distribution costs and improve the quality of service provided to customers. The Capacitated VRP CVRP is one of the most commonly researched among the VRP types. Therefore, the CVRP was studied in this paper and a new population based simulated annealing algorithm was proposed. In the algorithm, three different route development operators were used, which are exchange, insertion and reversion operators. It was tested on 63 well-known benchmark instances in the literature. The results showed that the optimum routes could be determined for the 23 instances.

___

  • [1] Dantzig GB, Ramser JH. The truck dispatching problem. Management Science 1959; 6 (1): 80-91. doi: 10.1287/mnsc.6.1.80
  • [2] Toth P, Vigo D. Vehicle Routing: Problems, Methods, and Applications. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2015.
  • [3] Jourdan L, Basseur M, Talbi EG. Hybridizing exact methods and metaheuristics: a taxonomy. European Journal of Operational Research 2009; 199 (3): 620-629. doi: 10.1016/j.ejor2007.07.035
  • [4] Lawler EL, Wood DE. Branch-and-bound methods: a survey. Operations Research 1966; 14 (4): 699-719. doi: 10.1287/opre.14.4.699
  • [5] Gomory RE. Outline of an algorithm for integer solutions to linear programs. Bulletin of the American Mathematical Society 1958; 64 (5): 275-278.
  • [6] Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MW, Vance PH. Branch-and-price: column generation for solving huge integer programs. Operations Research 1998; 46 (3): 316-329. doi: 10.1287/opre.46.3.316
  • [7] Toth P, Vigo D. The Vehicle Routing Problem. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2002.
  • [8] Papadimitriou CH, Steiglitz K. Combinatorial Optimization: Algorithms and Complexity. USA: Prentice-Hall, 1982.
  • [9] Kirkpatrick S, Gelatt CD, Vecchi MP. Optimization by simulated annealing. Science 1983; 220 (4598): 671-680. doi: 10.1126/science.220.4598.671
  • [10] Glover F. Future paths for integer programming and links to artificial intelligence. Computers and Operations Research 1986; 13: 533-549. doi: 10.1016/0305-0548(86)90048-1
  • [11] Baghel M, Agrawal S, Silakari Sanjay. Survey of metaheuristic algorithms for combinatorial optimization. International Journal of Computer Applications 2012; 58 (19): 21-31. doi: 10.5120/9391-3813
  • [12] Yu B, Yang ZZ, Yao B. An improved ant colony optimization for vehicle routing problem. European Journal of Operational Research 2009; 196 (1): 171-176. doi:10.1016/j.ejor.2008.02.028
  • [13] Harmanani HM., Azar D, Helal N, Keirouz W. A simulated annealing algorithm for the capacitated vehicle routing problem. In: 26th International Conference on Computers and Their Applications; New Orleans, Louisiana, USA; 2011. pp. 96-101.
  • [14] Nazif H, Lee LS. Optimised crossover genetic algorithm for capacitated vehicle routing problem. Applied Mathematical Modelling 2012; 36 (5): 2110-2117. doi: 10.1016/j.apm.2011.08.010
  • [15] Zang SZ, Lee CKM. An improved artificial bee colony algorithm for the capacitated vehicle routing problem. In: 2015 IEEE International Conference on Systems, Man, and Cybernetics; Kowloon, China; 2015. pp. 2124-2128.
  • [16] Teoh BE, Ponnambalam SG, Kanagaraj G. Differential evolution algorithm with local search for capacitated vehicle routing problem. International Journal of Bio-Inspired Computation 2015; 7 (5): 321-342. doi: 10.1504/IJBIC.2015.072260
  • [17] Ewbank H, Wanke P, Hadi-Vencheh A. An unsupervised fuzzy clustering approach to the capacitated vehicle routing problem. Neural Computing and Applications 2016; 27 (4): 857-867. doi: 10.1007/s00521-015-1901-4
  • [18] Mohammed MA, Ghania MKA, Hamedc RI, Mostafad SA, Ibrahime DA et al. Solving vehicle routing problem by using improved K-nearest neighbor algorithm for best solution. Journal of Computational Science 2017; 21: 232-240. doi: 10.1016/j.jocs.2017.04.012
  • [19] Faiz A, Subiyanto S, Arief UM. An efficient meta-heuristic algorithm for solving capacitated vehicle routing problem. International Journal of Advances in Intelligent Informatics 2018; 4 (3): 212-225. doi: 10.1016/j.cor.2004.07.009
  • [20] Menger K. Das botenproblem. Ergebnisse Eines Mathematischen Kolloquiums 1932; 2 (4): 11-12 (in German).
  • [21] Ballou RH. Business logistics management: Planning, organizing and controlling the supply chain. USA: Prentice Hall, 1999.
  • [22] Toth P, Vigo D. Exact solution of the vehicle routing problem. In: Teodor GC, Gilbert L (Editors). Fleet Management and Logistics. New York, USA: Springer, 1998, pp. 1-31.
  • [23] Dell AM, Rignihi G, Salani M. A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection. Transportation Science 2006; 40 (2): 235-247. doi: 10.1287/trsc.l050.0118
  • [24] Chen A, Yang G, Wu Z. Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. Journal of Zhejiang University-Science A 2006; 7 (4): 607-614. doi: 10.1631/jzus.2006.A0607
  • [25] Askarzadeh A, Santos CL, Klein CE, Mariani VC. A population-based simulated annealing algorithm for global optimization. In: 2016 IEEE International Conference on Systems, Man, and Cybernetics (SMC); Budapest, Hungary; 2016. pp. 4626-4633.
  • [26] Coello C, Carlos A. Constraint-handling techniques used with evolutionary algorithms. In: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion; Denver, Colorado, USA; 2016. pp. 563-587.
  • [27] Yu VF, Lin SY. Solving the location-routing problem with simultaneous pickup and delivery by simulated annealing. International Journal of Production Research, 2016; 54 (2): 526-549. doi: 10.1080/00207543.2015.1085655
  • [28] Hentenryck P, Vergados Y. Population-based simulated annealing for traveling tournaments. In: Proceedings of the National Conference on Artificial Intelligence; Vancouver, British Columbia; 2007. pp. 1-20.
  • [29] Augerat PH, Belenguer JM, Benavent E, Corberan A, Naddef D et al. Computational results with a branch and cut code for the capacitated vehicle routing problem. Technical Report 949-M, Grenoble, France: 1995.
  • [30] Christofides N, Eilon S. An algorithm for the vehicle-dispatching problem. Journal of the Operational Research Society 1969; 20 (3): 309-318. doi: 10.1057/jors.1969.75
  • [31] Fisher ML. Optimal solution of vehicle routing problems using minimum K-trees. Operational Research 1994; 42: 626-642. doi: 10.1287/opre.42.4.626