导　　师： 郭嵩山

学科专业： H1202

授予学位： 硕士

作　　者： ;

机构地区： 中山大学

摘　　要： 　　本文研究的是车辆调度类问题(VRP)的一个新的分支有车辆数限制的开放式车辆调度问题(M-OVRP)。在本文中，作者采用改进的禁忌搜索算法来解决M-OVRP问题，提出了多初始解选优、平滑动态的禁忌长度等改进方法，并引入了遗传算法中变异的思想来增加算法的活力。实验结果表明，本文提出的算法不仅能很好地解决M-OVRP问题，对OVRP问题也能得到稳定的结果。在研究的过程中作者还发现，M-OVRP问题的解和以所有客户(包括仓库)所在点的DELAUNAY三角剖分有紧密联系。因此，猜想M-OVRP问题解的大多数边会落在相应的DELAUNAY三角剖分的边上。本文尝试用该猜想去加速算法，取得不错的结果。事实上，本文所提出的一些方法可以很方便地应用到其他的一些启发式搜索问题的求解中。

关 键 词： 开放式车辆调度 车辆数限制 禁忌搜索算法 三角剖分

分 类 号： [F253.9 U492.22 TP301.6]

领　　域： [经济管理] [交通运输工程] [交通运输工程] [自动化与计算机技术] [自动化与计算机技术]