论文部分内容阅读
车辆路径问题属于运筹学范畴,是运输线路规划、选取合理配送车辆的核心工作,在提高货物运输经济中起着至关重要的作用。随着市场竞争的剧烈化和顾客需求的多样化,带能力约束的VRP已经不能科学地指导企业完成其配送任务;从提高企业的市场竞争力和满足客户的多样性需求的角度研究VRP问题越来越受到大量学者的广泛关注,相比于只包含车辆载重约束的基本VRP,带时间窗的车辆路径问题(VRPTW)能更好地反应实际应用情况。本文结合实际的生产运作情况,运用改进的蚁群算法,有效的求解带时间窗的多车型车辆路径问题。研究结论主要有:(1)蚁群算法中,蚂蚁在初始寻优过程中,在选择下一节点时,根据状态转移概率确定备选客户点的概率值。通常情况下,蚂蚁选择概率较大的节点,这样就会导致蚁群算法在搜索过程中容易出现停滞现象。本文在选择下一节点时引入一个随机数,让部分蚂蚁有一定的犯错概率,也就是蚂蚁在选择下一节点时会有一定的探索性搜索,并在蚂蚁完成一次迭代后对结果进行遗传算子操作,这样可以有效扩大问题的解空间,从而提高算法的求解性能。(2)在对带时间窗的车辆路径问题求解时,客户的服务时间窗要求对目标函数有直接影响,因此在蚂蚁选择下一节点的转移概率中,仅考虑路径长度以及路径上的信息素浓度可能得不到问题的合理解。本文通过在蚂蚁的转移概率中加入了时间窗因素,使得问题的解更接近最优解,通过对蚁群算法改进前后的结果对比分析,发现改进蚁群算法在求解该问题时更具优势。(3)目前对于带时间窗的多车型车辆路径问题的研究较少,大容量货车有装载量大、行驶距离远的优点,但却不可避免的具有行驶速度慢、配送效率低的缺陷,而小容量货车则相反。因此,本文在综合考虑不同车型的特点,结合不同客户对服务时间窗要求的基础上,设计了改进的蚁群算法对带时间窗的多车型车辆路径问题进行求解,研究结果表明,对于同一配送任务,选用混合车型的配送方案在某种程度上会取得更好的效果。