A hybrid subgradient method for solving the capacitated vehicle routing problem

ALPASLAN TAKAN M., Kasimbeyli R.

Journal of Nonlinear and Convex Analysis, cilt.21, sa.2, ss.413-423, 2020 (SCI-Expanded) identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 21 Sayı: 2
  • Basım Tarihi: 2020
  • Dergi Adı: Journal of Nonlinear and Convex Analysis
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, MathSciNet, zbMATH
  • Sayfa Sayıları: ss.413-423
  • Anahtar Kelimeler: Genetic algorithms, Subgradient methods, Vehicle routing
  • Bilecik Şeyh Edebali Üniversitesi Adresli: Evet

Özet

In this paper, a new hybrid subgradient method is proposed for solving the capacitated vehicle routing problem, which is nonconvex and nondifferentiable, due to integer variable constraints. This method is based on the Gasimov's modified subgradient algorithm, which was developed for solving general constrained optimization problems without convexity and differentiability conditions. Modified subgradient algorithm uses the sharp augmented Lagrangian dual construction, which provides zero duality gap condition under mild assumptions. The performance of this algorithm, is highly dependent on the quality of the solution, obtained for the subproblem at every iteration. In the proposed method, a genetic algorithm is utilized for solving the subproblems. By analyzing the solution found for the subproblem, the algorithm stops, updates dual variables, or updates upper or lower bounds for the problem. The performance of the method is demonstrated and analyzed on test problems.