论文部分内容阅读
国际上普遍认为,物流作为新兴的服务业,具有广阔的发展前景和增值功能。它对于有效提高整个社会的资源配置效率以及提升国家的经济运行质量、效益和动力有着举足轻重的作用。运输服务是国民经济的命脉,在物流体系的所有动态功能中,运输功能是核心。车辆路径问题(Vehicle Routing Problem,VRP)是运输服务优化中的核心问题。自1959年以来国际著名期刊以及业界的实际应用也纷纷展现了此领域丰富的研究成果。本文重点研究车辆路径问题的一个变种问题─带时间窗和组合拍卖的车辆路径问题(Vehicle Routing Problem with Time Windows and Combinatorial Auction,VRPTWCA)。本文首先简要介绍和归纳VRP的定义特征及其相应数学模型,详细阐述带时间窗的车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW)的研究成果,在此基础上对VRPTWCA进行具体的描述与分析,通过中石油的实际案例引出此问题,分析此问题与经典VRPTW的异同点,给出VRPTWCA的一般描述、建立数学模型,并分析它的研究现状。然后着重介绍自适应大邻域搜索算法(Adaptive Large Neighborhood Search,ALNS)、禁忌搜索算法(Tabu Search,TS)以及弹射池算法(Ejection Pool,EP)的基本原理和在本文的具体应用,介绍本文的研究重点和难点。针对此问题,本文设计了两个算法,分别命名为ALNS-Embedded TS和EP-Based Reactive TS,算法一在构造阶段通过三种选择机制选定初始投标后使用古典启发式获得初始解,改进阶段用TS算法搜索投标空间,用改进的EP算法(Modified Ejection Pool)为未被服务的顾客构建路径并进行改进,之后使用ALNS算法搜索路径空间,使用最好解优先策略在指定的迭代次数内输出较优解。算法二在构造阶段通过三种选择机制选定初始投标后使用RVN算法(Reduce Vehicle Number)获得初始解,然后使用TS算法搜索投标空间,使用Reactive TS算法搜索路径空间,本文在第四章和第五章分别详细阐述了以上两个算法的实现原理和运行逻辑。本文使用Java JDK 1.8实现了上述两种算法,输入算例,将两个算法的运行结果进行对比分析,并将本文的运行结果与文献中已存在的精确算法的运行结果进行比较,发现在运行时间方面,相较于精确算法设定的4小时,启发式算法具有突出优势,即最长不超过20分钟;其次对于小规模算例,算法一搜索到45个算例的最优解,随着算例规模的扩大,算法一的质量略有下降,但是对于其中23个算例,算法一找到了优于精确算法上界的解;最后算法二质量略逊于算法一,但是针对个别算例具有借鉴意义。本文最后对做出的贡献以及未来的研究方向进行辩证性总结。