The Deterministic Annealing Algorithms for Vehicle Routing Problems

摘要

Two direction guided annealing modifications to the traditional simulated annealing algorithm for solving the Vehicle Routing Problems (VRP) are proposed in this paper. The aim is to avoid searching solution space where the optimal solutions are not likely to be in. The string model of the VRP is adopted in these algorithms. The first approach is called the probability-based guided annealing algorithm, in which guide coefficients are formulated as probabilities for breaking and establishing connections between nodes. Based on these coefficients, a formulation is proposed to decide whether a stochastically generated exchange request between nodes is accepted for further computation or not. A detailed description of the algorithm is given. The algorithm is then implemented to solve a 100 shops capacitated VRP(CVRP). Three commonly used exchange rules are used for testing the performance of the algorithm: 1 to 1, random-insert, and 2-opt. Both computation time and distribution of the optimization cost function are measured and compared among the three exchange rules. Comparisons are also made with the traditional simulated annealing algorithm to contrast the superior efficiency of the new algorithm. Another guided annealing algorithm introduced in the paper is the pair-wise competitive annealing algorithm. The top N distances measured from each customer to surrounding nodes are chosen for the purpose of generating new solution states by the 2-opt exchange rule. The effective search space is decreased by only examining a smaller array containing the distance relationships for potentially shorter routes, when compared to straight-forward implementation of the traditional simulated annealing. A detailed listing of the algorithm is given, which is then implemented to solve the CVRP computationally. Similar experimental setups to the probability-based guided annealing algorithm are used. The given results show that the algorithm yields better solutions than that of the traditional simulated annealing, and with a much reduced computation time. Considerations and justifications on choosing the parameter N are also given.