Complexity analysis for run time of 2-OPT algorithm for constrained vehicle routing problem

The complexity of the 2-OPT algorithm for the capacitated vehicle routing problem (CVRP) was analyzed in this paper. Since the demand distribution is independent of location distribution, the vehicle routing problem (VRP) was transformed into a Multiple Traveling Salesman Problem (MTSP) to avoid demand constraints. The feasibility conditions for the use of 2-OPT with MTSP were used to determine the distribution of the iteration numbers and the upper bound of the expected algorithm run time. The algorithm provides a powerful method to evaluate the 2-OPT for the CVRP and a new way to analyze heuristic algorithms for VRP.