论文部分内容阅读
随着市场经济的迅猛发展和物流专业化水平的提高,物流配送的地位和作用越来越重要。车辆路径问题和车辆装载问题作为物流配送中的两个核心问题已经成了研究的热点。设计快速、高效的车辆路径问题和车辆装载问题的算法,对于降低配送成本、提高配送效率和服务质量,提高企业的利润具有重要的意义,同时达到节约能源,保护环境,减少废气污染和交通拥堵,保证交通安全的目的。车辆路径问题(Vehicle Routing Problem,简称VRP)是组合优化和运筹学领域中的一个典型的NP-hard问题。其研究的重点是在满足一定约束条件的情况下(例如货物的需求量,交货时间,载重量,行程和时限等),把货物从仓库送给客户,并实现特定的目标(例如缩短路程,降低费用,节省时间等)。车辆装载问题(Vehicle LoadingProblem)也是一个NP-hard问题,其主要目的是将货物合理的装载到车辆中,同时实现最大的车辆装载率,从而减少车辆的数目,在硬件上降低配送的成本,提高企业的利润。车辆路径问题和车辆装载问题是物流配送过程中的两个十分重要且紧密关联的问题。车辆装载是否合理影响着车辆路径安排方案,反之亦然。两者的相互作用直接影响着物流配送的成本和服务水平。本文主要是将这两个物流配送过程中相互联系、相互制约的问题作为一个新的组合优化问题,进行整体考虑,其目标是总的行驶距离最短和车辆装载率最大。本文研究的是二维装载问题和带载重量限制的VRP问题的组合优化,这里称之为二维载重量限制的车辆路径问题(two-dimensional loading capacitated vehicle routing problem)简称为2L-CVRP。本文主要做了如下工作:(1)对车辆路径问题、装载问题和二维装载限制的车辆路径问题的研究情况进行了详细的阐述和分析。(2)对已有的二维装载算法进行了研究,为适应本文研究的二维装载限制的CVRP的具体情况对其做了改进,给出了实验对比;(3)用改进的基于节约的蚁群优化算法解决二维载重量限制的车辆路径问题。首先蚂蚁根据融合节约值和信息素的概率规则构建车辆运行的初始路径。在构建初始路径的过程中,调用装载算法检查货物装载的可行性,并进行装载;然后用2-opt和Swap局部优化方法优化初始路径,最后根据精英蚂蚁和蚂蚁等级更新信息素。重复迭代直到迭代次数到达,输出最终解。