论文部分内容阅读
随着市场竞争的加剧，物流已经成为企业提高市场竞争力和核心竞争力的重要手段，而运输通常是物流成本中最大的单项成本。所以，研究车辆路径问题(VehicleRoutingProblem,VRP)，通过设计合理的运输路线，使车辆在满足服务要求的同时，成本最小化，从而减少物流整体费用，具有重要意义。根据车辆容量、车型等限制的不同，有多种类型的VRP，本文针对两种问题进行了讨论：有时间窗的多车场车辆路径问题(theMulti-depotsVehicleRoutingProblemwithTimeWindows,MDVRPTW)和有时间窗的具有同时配送与回收的车辆路径问题(theVehicleRoutingProblemwithSimultaneousPick-upandDeliveryandTimeWindows，VRPSDPTW)。
VRP已被证明为NP难题，对其算法的研究大部分集中在启发式算法上，而蚁群算法是近年来新兴的启发式算法，本文采用蚁群算法对上述两个问题进行求解。本文主要工作有：
1、针对基本蚁群算法易陷入局部最优的缺陷，本文从调整起始搜索节点和交换信息素两个方面提出了改进，在基准问题上的实验表明该算法取得的目标值较优，而且取得目标值时所需的迭代次数较少。
2、给出MDVRPTW的数学模型，并采用蚁群算法对该模型求解。求解时采用整体法将多个车场虚拟为一个车场，每次搜索从虚拟车场中随机选择一个实际车场作为出发车场，采用SOLOMON的NearestNeighbour插入式算法，搜索一条可行路径，服务结束后回到出发车场。
3、给出了VRPSDPTW的数学模型，采用蚁群算法求解该模型时，引入一个变量解决了该问题中车辆的容量判断问题，并提出了同时考虑剩余容量符合度和时间窗的启发式函数，在此基础上给出了蚁群算法的实现过程。
4、对上述两个问题编写C++程序，选择VRPWeb提供的基准问题进行实验，结果表明本文给出的两个算法得到的结果较优，具有较强的实际意义，且所需计算时间也在合理范围内。