A Hybrid Markov Chain and Simulated Annealing Algorithm for the Capacitated Vehicle Routing Problem

Abstract

In this study, a hybrid optimization algorithm integrating Markov Chains with Simulated Annealing is proposed for solving the Capacitated Vehicle Routing Problem (CVRP). The approach utilizes stochastic customer assignment and dynamic route generation guided by Markov transition probabilities, alongside adaptive temperature scheduling based on the Simulated Annealing framework. To enhance local search effectiveness, classical heuristics such as 2-opt and Or-opt are incorporated for neighborhood improvement, significantly refining solution quality. A comprehensive parameter study is conducted to assess the impact of key algorithmic components, including the β (beta) sensitivity parameter, initial temperature (T0), cooling rate (α), maximum iterations per temperature level (maxItPerTemp), and total iteration count. The performance metrics are systematically tabulated under the structure: β-To-α-maxItPerTemp - Iteration - Total Cost. Experimental results on realistic demand and capacity scenarios confirm that the hybrid method effectively balances exploration and exploitation, avoids local optima, and achieves competitive solution quality. The entire framework is implemented in MATLAB and supported with route visualizations and dynamic Markov transition graphs, providing a robust and scalable tool for large-scale logistics optimization. © 2025 IEEE.