有车辆数限制的开放式车辆调度问题研究

Research on the Open Vehicle Routing Problem with Limited Number of Vehicles

有车辆数限制的开放式车辆调度问题(m-OVRP)是车辆调度类问题(VRP)的一个新的分支.本文通过多初始解选优、平滑动态的禁忌长度等改进手段,基于遗传算法中变异的思想,设计了改进的禁忌搜索算法来解决m-OVRP问题.实验结果表明,本文提出的算法不仅能很好地解决m-OVRP问题,对OVRP问题也能得到稳定的结果.本算法核心包括:提出一种全新的构造初始解的贪心算法,在禁忌搜索初始解的选取中采用多初始解选优的策略;提出在禁忌搜索中采用平滑动态的禁忌长度.本算法可以很方便地应用到其他的一些启发式搜索问题的求解中.

This paper studied a new useful extension of vehicle routing problem(VRP)-open vehicle routing problem with limited number of vehicles(m-OVRP).We propose an improved Tabu Search algorithm by adapting techniques of best-selection from multiple initializations,smooth dynamic Tabu tenure,and mutation improvement from gene algorithm.From the experimental results,the algorithm not only well solves the m-OVRP problem,but also obtains good solutions for the OVRP problem with stable performance.The search techniques proposed in this paper can be easily applied for other meta-heuristics for problem solving.