车辆路线问题是物流运作与管理中的一项重要问题。在很多情况下,车辆运输成本是物流成本最主要的组成部分,因此通过优化车辆路线安排可以有效地降低物流成本,同时也是提高物流服务水平的主要手段之一。 在大部分车辆路线问题的研究中,都预先设定了一个条件,就是每个客户的需求(指小于车辆最大运载能力的需求)必须由一辆车在一次服务中完成。但实际的物流运作中,在能满足服务要求的前提下,有时通过需求的拆分可以更好地降低运输成本,特别是在需求量普遍较大的情况下。因此作者针对这一实际情况,选择需求可拆分的物流车辆路线问题作为本文的研究主题。 本文主要通过分析、建模、算法设计这一过程对需求可拆分的物流车辆路线问题进行了深入的研究,研究重点在于如何利用亚启发式算法求解需求可拆分的物流车辆路线问题。主要内容如下: 首先,在阅读大量文献的基础上对需求可拆分的物流车辆路线问题的研究现状进行了综述,同时对车辆路线问题进行了全面的概述,以此作为进一步研究的基础。 其次,通过对问题的分析,建立了需求可拆分的物流车辆路线问题的一般模型和整数规划模型,对可行解的特性进行了分析,证明了判断解是否可行的三个重要判据,并对需求拆分的意义进行了简单的分析。 然后,本文针对需求可拆分的物流车辆路线问题的整数规划模型,设计了利用禁忌搜索进行求解的算法,其中重点设计了符合需求可拆分的物流车辆路线问题特点的邻域搜索方法,以及通过引入邻域搜索范围的自适应策略对禁忌搜索算法进行了改进。并对算法进行了算例验证, 此后本文又根据需求可拆分物流车辆路线问题的整数规划模型的特点,将问题转化为单位需求客户的车辆路线问题,并设计了求解该问题的遗传算法。在设计过程中,本文引入可行化算子和可行化概率参数来抑制由于不良拆分而引起的群体质量恶化问题。最后利用算例对算法进行了验证。 最后对全文进行了总结,并对进一步的研究进行了展望。