求解带时间窗的装-卸载问题的概率式禁忌搜索算法

本文介绍一个求解有时间窗的装载—卸载问题的概率式禁忌搜索算法。论文首先回顾了求解VRP、PDP问题的主要方法,介绍了搜索算法的基本概念,给出了基于概率式禁忌搜索的详细算法。初步实验表明新算法优于传统禁忌搜索算法。     

时间依赖型多配送中心带时间窗的开放式车辆路径问题研究

本文研究了时间依赖型多配送中心带时间窗的开放式车辆路径问题,基于道路通行情况,建立车辆行驶速度时间函数;考虑车辆载重、里程限制与客户点服务时间窗的约束,建立混合整数规划模型,目标函数为最小化车辆总成本,具体包括车辆行驶时间成本和车辆固定发车成本;提出了一种二维编码方式的混合遗传算法,针对混合遗传算法设计了多分区段单点交叉策略、动态插入算子及局部搜索策略;最后,基于Solomon VRPTW基准数据集生成27个测试算例,使用混合遗传算法进行求解。数值实验结果表明,考虑道路通行情况,选择合理的出发时间,避免拥堵时段进行配送服务,能明显减少车辆的总行驶时间,且验证了混合遗传算法能够获得问题的满意解。     

多车场带时间窗车辆路径问题的变邻域搜索算法

多车场带时间窗车辆路径问题是车辆路径问题集合中的一个极为复杂、且仍未得到较好解决的问题。针对这一问题,建立了它的整数规划数学模型,提出了一种改进型变邻域搜索算法。该算法在初始解的构造阶段采用聚类方法完成客户的分配,运用混合算子进行局部搜索,通过后优化过程增强寻优效果,引入模拟退火模型对新解的接受进行控制。最后,在Cordeau提出的标准用例上对改进型变邻域算法进行了实验,实验结果更新了大部分目前该问题的最优解,并在算法的稳定性和求解时间上体现出一定优势。实验表明,该算法是一种求解多车场带时间窗车辆路径问题的有效方法。     

基于改进小生境GA的有时间窗物流配送路径优化问题研究

有时间窗的物流配送车辆路径优化问题是一个NP难题,较难得到满意解.本文在基于隔离机制的小生境遗传算法的基础上,引入迁徙操作和模拟退火方法,用来解决有时间窗的车辆路径优化问题.这种方法不仅能够保证群体的多样性,而且具有良好的全局收敛性.实例也证明了该方法的有效性和实用性.     

有时间窗车辆路径问题的模型及其改进模拟退火算法研究

论文在对有时间窗车辆路径问题进行描述的基础上,建立了该问题的基于直观描述的数学模型.论文还根据有时间窗车辆路径问题的特点构造了求解该问题的改进模拟退火算法,并进行了实验计算.计算结果表明,用本文设计的改进模拟退火算法求解有时间窗车辆路径问题,不仅可以取得很好的计算结果,而且算法的计算效率较高,收敛速度较快,计算结果也较稳定.     

带模糊工作时间窗的多配送中心同时集散货物车辆路径问题

在线资源的特性使得配送车辆采用分时租赁的模式为客户进行服务,配送车辆路径问题呈现多模糊时间窗特性。本文构建了带有模糊工作时间窗的多配送中心同时集散货物车辆路径模型,以最小化配送成本、车辆使用数,最大化服务质量为优化目标。根据客户期望时间窗、硬时间窗、软时间窗,改进了线性梯形隶属度函数表示客户模糊满意度。模型的求解采用自适应大规模邻域搜索算法,通过引入多种群搜索机制和非支配排序操作,加快算法收敛速度、增强算法全局寻优能力。最后,通过算例求解验证模型和改进算法的有效性和优越性。     

求解带时间窗的客户需求可分条件下的车辆路径问题

物流运输中的车辆路径问题历来是一个重要的理论和实际问题,在同时考虑客户需求可分以及客户方和配送中心时间窗限制的前提下,重新构造了问题模型,并结合蚂蚁算法中转移概率的改进和最大-最小蚂蚁系统,设计了问题求解过程和分割点选取规则,计算结果显示出算法的可行性。另外还与客户需求不可分的情况进行了对比,从而说明在大规模物流运输需求下,可分能带来更好的效果。     

有顾客时间窗和发货量变化的车辆调度干扰管理研究

为解决由顾客需求变化引发的物流配送干扰问题,提出基于干扰管理思想构建扰动恢复策略和方案.应用虚拟多车场实现车辆调度扰动恢复问题转化.提出车辆调度扰动恢复策略和扰动度量方法,以作为车辆调度干扰管理建模的基础;分析顾客时间窗和发货量变化造成的扰动并进行辨识.建立相应的干扰管理模型,提出归一化处理办法对VRPTW、MD-VRPTW和MDVRPTW干扰管理问题进行有效兼容;结合干扰管理模型的特点,改进基于顾客的编码表示方法,可以反映出车辆调度扰动恢复策略;根据干扰管理思想,设计遗传算法对干扰管理模型进行求解.给出了一个具有代表性的算例试验结果,算例结果及其分析表明干扰管理模型和遗传算法的有效性.     

草畜平衡约束下带时间窗的放牧路径规划研究

草地资源的自然特征决定了草场载畜量的有限性,一年内只有在特定的时间窗适合放牧,承受不了长期、持续地放牧。不合理的放牧路径规划不仅会导致牲畜采食时间与草场生长周期错配,还会导致草场出现超载、欠载及退化等一系列负面问题。本文在考虑草畜平衡的基础上,提出放牧时间惩罚函数,构建了线性时间窗和指数型时间窗放牧路径规划模型,并设计了改进的遗传算法对模型进行求解。最后以青海省海晏县的牧户为例对模型进行了验证。结果表明,带指数型时间窗的算法能够更快地逼近最优解,且综合考虑三种成本比只考虑单一成本为目标得到的放牧路径总成本更低。改进的遗传算法缩短了求解时间并提高了求解稳定性。本文构建的带时间窗路径规划模型充分考虑了草场的自然属性,优化了牧户放牧路径,提高了牧户对草地资源利用的科学性。     

顾客时间窗变化的多车场车辆调度干扰管理模型研究

为解决物流配送过程中某顾客时间窗变化而导致的物流配送难以按照原计划实现的难题,运用干扰管理方法,针对多车场带时间窗的物流配送车辆路径问题,提出包含顾客配送时间总偏离度、配送总成本、新路径方案与初始路径计划偏差量、最长行驶时间违反总量4个因素的扰动程度度量方法;以顾客时间窗变化这类干扰事件发生时的问题状态为基础,以系统整体扰动最小化为目标,建立问题的目标规划数学模型;针对这一复杂模型,提出基于特定邻域结构及其寻优概率的变邻域搜索算法;最后在标准算例上使用变邻域搜索算法与其他文献算法进行比较分析,结果表明该变邻域搜索算法对于干扰事件发生后的车辆路线重排结果在系统整体扰动程度方面明显优于其他文献的算法.     

供需未匹配的多车场多车型多货品可拆分取送货车辆路径问题

取送货车辆路径问题在多点调拨系统普遍存在,属于NP-hard问题。该问题研究通常需考虑车场数、车型种类、货品种类、客户服务次数等诸多因素,已有文献多假设客户间供需已匹配、单车场、单车型、单货品和取送货需求一次性满足,优化目标多设置为总路径最短。而从企业运营实践来看,运输方案不仅要规划客户间访问路径,还需进行客户间供需匹配;运输成本不仅与运距有关,还涉及运输货品的重量和派车成本;运输网络中多车场、多车型和多货品更加常见,且客户需求量往往大于车辆装载能力。因此,本文首次尝试基于"运距×运量"的车辆路径成本和基于额定吨位的固定派车成本之和最小为优化目标,建立同时考虑多车场、多车型、多货品、客户间供需未匹配和需求可拆分的取送货车辆路径问题模型,并设计基于大规模邻域搜索的迭代局部搜索求解算法。该算法采用基于运输效率提升的贪婪思想来快速构建高质量初始可行解,并通过引入四种移除算子、两种修复算子和车场车型调整优化策略形成大规模可行搜索邻域以增强全局寻优能力。基于18个文献算例和6个企业实例的数值实验结果表明：1）本文提出的算法在求解质量和求解效率方面均优于相关文献中的算法;2）相对人工调拨方案,本文设计的方案能够帮助企业节约33%的运输成本和21%的车次。本研究不仅可拓展取送货车辆路径问题现有理论,而且可为企业实际运营提供决策支持。     

一种考虑动态时间窗的满载问题模型及算法

针对时间约束在满载问题中的复杂性,建立了一个考虑装载时间和次序的具有动态时间窗的满载车辆调度模型,并给出了一个基于动态构造原理的启发式算法。该模型和算法改进了以往满载问题中对时间窗的考虑,使得求解更具有实际派车意义,并且该算法通过参数调整,经过少量迭代即可快速求得最小化总成本的满意解。     

有顾客时间窗和发货量变化的紧急车辆调度研究

对紧急车辆调度系统进行了研究,探讨了紧急车辆调度问题实现的关键技术.对有顾客时间窗和发货量变化的紧急车辆调度问题,运用了禁忌算法(TS)进行优化.算法基于实数编码,应用GENI插入法产生初始解和进行邻域操作,设计了三种邻域,利用容量约束控制单条路径配送点数,采用惩罚函数处理时间窗约束,通过设计虚拟车场等方法实现了车辆的紧急调度.本文给出了一个具有代表性的算例试验结果,算例结果及其分析表明了此方法对优化紧急车辆调度问题的有效性.     

最短时限运输问题及解法

提出了存在于实际中的最短时限运输问题,研究了其解的最优性充分条件,并给出了求解这一问题的具体步骤,最后用实例说明了解法的可操作性,该解法是解决这一类问题的一个好算法。     

GRASP with a New Local Search Scheme for Vehicle Routing Problems with Time Windows

The NP-Hard Vehicle Routing Problem with Time Windows (VRPTW) is one of the major transportation problems. In this paper, a Greedy Randomized Adaptive Search Procedure (GRASP) for VRPTW is discussed for minimizing the fleet size and the travel distance. There are two phases within each GRASP iteration: construction phase and local search phase. In the construction phase, the initial solution is computed by applying an adaptive randomized greedy function. In the local search phase, the search procedure is applied to the constructed initial solution obtained by the construction phase for an improvement. In this paper, we propose an improved solution technique by using new local search ideas and new lower bounding procedures. In addition, we report computational results and address some practical issues in this area.     

基于自感应蚁群算法的VRPSDP问题研究

同时供货和取货的车辆路径问题是车辆路径问题的重要组成部分之一,问题的复杂性使得目前的主要求解方法局限于各种插入式启发算法。本文引用了近年来出现的蚁群算法,并通过对蚂蚁行为的深入研究,首次提出了感应因子、期望程度因子、距离性比因子以及加速因子的概念,在信息素更新方面融入了当前路径的距离特征,构建了一种全新的自感应蚁群算法。该方法充分利用全局分布的信息素感应信息,并且根据车辆容量支配值以及节点间距和节点-中心点间距性比进行状态转移,利用信息素更新公式中加速因子的动态调节有效地解决了算法快速收敛与陷入局部最优的矛盾。仿真试验证明了自感应蚁群算法的有效性,同时,该算法也拓展了车辆路径问题的算法空间。