带硬时间窗车辆路线问题的模拟退火算法研究

Study on Vehicle Routing Problem with Hard Windows by Simulated Annealing Algorithm

本文在对带硬时间窗车辆路线问题进行描述的基础上，建立了该问题的数学模型。针对该模型的NP—hard属性，设计了相应的模拟退火算法；即利用改进节约法构造初始可行解，提高了求解速度；路线内和路线间同时进行邻域搜索，避免了算法陷入局部最优；通过恰当地选择技术参数，实现了快速有效地求得问题的满意解。实例仿真测算表明本文提出的算法求得的解质量较高，从而说明了模拟退火算法解决带硬时间窗的车辆路线问题具有一定的有效性和实用价值。

This paper describes the vehicle routing problem with hard time windows, and sets up the mathematical model of this problem. In view of this model＇ s NP - hard attribute, designs a kind of simulation annealing algorithm to solve this problem, the initial feasible solution is made up by improved saving algorithm. Neighbor searching between two routes and in two routes are used at the same time so the local optimum solution is avoided. By choosing proper technology parameter, it can be obtained satisfied solution quickly and effectively. It is indicated that the results of this paper is better by calculating the simulation example, and the simulation annealing algorithm has certain effective and practical value when solving this kind of problems.