当前位置:问答库>论文摘要

题目:大规模配送的二阶段路径优化模型及其算法设计

关键词:大规模车辆调度;聚类;禁忌搜索

  摘要

物流配送中车辆路径问题(VRP, vehicle routing problem)在过去的几十年中由于很强的应用背景得到了学术界广泛的关注,成为运筹学领域最热门的研究问题之一。对于VRP问题的研究,设计高效且性能优良的算法,对于提高企业货物配送水平,增强客户满意度,节约物流运输成本有着重要的意义。然而由于VRP问题本身的复杂性,以往的研究一般建立在十分理想的小规模环境中,随着信息科技和计算机技术等工具科学的发展,进一步完善或解决过去没能解决的问题成为了可能。本文结合大规模配送问题和实际生活中配送的特点,建立了带时间窗和客户需求可分割的数学模型,并提出二阶段启发式算法。首先,根据实际情况中相距较近的客户往往由同一辆货车进行服务的特点,引入基于密度的聚类算法,将满足一定条件的客户划为一个区域。对区域内的客户点,应用Clark & Wright算法进行TSP计算最佳路径,将最佳路径行驶时间作为虚拟客户的服务时间。通过将聚类作为一个虚拟客户,有效降低问题的规模。其次,使用禁忌搜索算法对聚类后的问题进行求解,设计完善领域解的产生和禁忌表,为高效求解创造了必要的条件。为了验证算法的有效性,本文进行了大量的仿真实验。测试问题集采用常用的Solomon test sets问题集。首先对算法参数进行研究确定,之后选取较优的实验结果与目前已知的最优解进行比较,得到本算法与最优解之间各个方面的优劣,并对出现的问题进行说明。最后,对本文中提出的算法在未来研究应用进行了展望,并提出进一步的研究方向。