论文部分内容阅读
当今世界经济的迅猛发展大大促进了物流运输的发展,物流产业作为各国经济的重要组成部分,已经广泛的引起了人们的重视。目前物流的发展程度决定了一个国家的发展水平,它可以提高一个国家的国民生产总值,引导国家经济的发展方向。减少运输成本可以有效提高物流行业的效益,最常用的方法就是使运输路径最短。传统的车辆路径问题(Vehicle Routing Problem,VRP)就是研究运输路径最小化的问题。因为它要求每个顾客的需求必须由一辆运输车进行配送,所以当一些顾客的需求量大于车辆容量时,就会出现无法满足所有顾客需求的情况。为了解决这个问题,相关学者开始考虑对顾客的需求进行拆分,并提出了需求可拆分车辆路径问题(Split Delivery Vehicle Routing Problem,SDVRP)。本文在研究SDVRP问题的过程中发现它没有考虑到在运输途中消耗物资的情况,因此本文将路径消耗加入到SDVRP问题的约束条件中,提出了运输途中货物消耗的需求可拆分车辆路径问题(Split Delivery Vehicle Routing Problem with Goods Consumed during Transit,SDVRP-GCT)或者称为带有路径消耗的需求可拆分车辆路径问题。SDVRP-GCT问题不仅可以适用于物流配送问题,同时也可以应用于生活中其他问题的解决。本文是在SDVRP问题的基础上,分析了传统的SDVRP问题的研究现状与短板,并将SDVRP问题与真实世界中的物流场景相结合,提出一种更符合现实物流运输情形的SDVRP-GCT问题,随后基于蚁群算法设计了三种扩展算法进行问题求解。本文进行实验所用的数据集包括:SDVRPLIB数据集、VRP web中的大规模数据集和数学建模网站中收集的旅游规划数据集。首先本文将三种扩展算法应用于SDVRP问题中,并将得到的三种算法的结果与数据集提供的最优解进行对比,结果表明三种扩展算法能够改善目前存在的最优解,这说明在解决SDVRP问题上,本文提出的三种扩展算法表现出了很好的性能。随后本文假设车辆在运输途中的商品消耗与路径长度成比例,将SDVRP基准数据集转化为SDVRP-GCT数据集,然后将三种扩展的蚁群算法应用在转化后的SDVRP-GCT数据集上,得到的实验结果表明在不同类型的数据集上,三种扩展算法均有较好的表现。其次,本文将三种扩展的蚁群算法应用在VRP web中的四个大规模数据集上,实验结果表明本文扩展的算法在数据规模很大时仍然能有很好的解决问题。最后,本文将扩展的蚁群算法应用在自收集的旅游路线规划问题上,证明了SDVRP-GCT问题在现实生活场景中有更广泛的应用。综上所述,本文的主要研究工作包括:研究SDVRP问题的背景和模型,提出SDVRP-GCT问题并对其进行数学建模;扩展三种蚁群算法,可以同时求解SDVRP问题和SDVRP-GCT问题;设计实验,通过实验证明本文扩展的三种蚁群算法可以有效的求解SDVRP问题和SDVRP-GCT问题;最后将生活中的旅游规划问题建模成SDVRP-GCT问题,并用本文提出的三种扩展算法进行求解,从而证明本文工作在现实生活中有广泛的应用前景。