有限车辆调度问题的模型和改进遗传算法

Model and Improved Genetic Algorithm for Vehicle Dispatching Problem with Limited Vehicle Number

考虑到对带时间窗的有限车辆调度问题研究不足的事实,在建立了数学模型的基础上对传统的遗传算法(GA)进行改进:提出采用Bellman-Ford求最短路算法找出染色体所表示路径的最优组合形式;变异操作应用禁忌搜索算法(TS),并采用TS的动态摆动策略,对邻域结构的可行及不可行解进行有效的搜索。最后用Solo-mon中的Rc1数据验证了算法的有效性,其结果比较理想。

This paper considers the fact that there has been little research work on the vehicle dispatching problem with windows and a limited number of vehicles. To solve the problem, on the basis of establishing the optimizing model, it improves the standard genetic algorithm. Firstly, the Bellman-Ford algorithm is adopted to find the best solution that the chromosome string can represent. Secondly, in the process of mutation the tabu search is used and its dynamic oscillation strategies is applied to search the infeasible and feasible neighbor＇ space. The effectiveness of algorithm is confirmed by using Solomon＇ s test set Rcl, and the results are all more satisfying.