低碳环境下的车辆路径问题及禁忌搜索算法研究

基于节能减排的新视角,本文研究了低碳环境下由第三方提供运输服务的车辆路径问题,在安排车辆路径时,同时考虑了能耗、碳排放和租车费用,而这些费用不仅与距离有关,也与客户点的需求量和车辆速度有关。提出了考虑车辆运量和速度的能耗计算方法,建立了非满载运输方式下的低碳路径模型——LCRP。设计了基于路径划分的禁忌搜索算法RS-TS对问题进行求解,该算法引入了一种新颖的路径编码与解码算法WSS,采用了三种邻域搜索方法。通过基准测试实例验证了算法能有效地找到满意解,并揭示了距离、能耗、行驶时间等参数之间的关系,实验分析表明采用低碳路径安排更加经济环保且选择中低的交通速度更有利于节约能耗和降低碳排放。     

装卸一体化的车辆路径问题及基于插入法的新禁忌算法

在日益激烈的市场竞争中,如何在降低成本的同时,让各个顾客尽快收到货物成了现代交通运输物流中一个越来越重要的考虑因素。基于某快递公司的运输实例,本文提出了装卸一体化的车辆路径问题模型,最终优化目标是最小化车辆运输时间和货物到各个顾客的时间的加权和,并给出了一种基于插入法的新禁忌算法,实验结果表明新禁忌算法在显著提高传统禁忌算法计算时间的同时,还能得到理想的成本,并且对节约快递公司的运输成本方面有显著成效。     

基于模糊聚类与车辆协作策略的随机车辆路径问题

以多辆车协作的随机车辆路径问题为研究对象,设计了通用的随机车辆路径问题机会约束模型,提出了大规模随机车辆路径问题的车辆协作策略,并基于该策略与模型设计了求解天规模随机车辆路径问题的混合启发式算法,计算实验结果说明了该算法与策略的有效性与实用性.     

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

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

考虑区域限制的卡车搭载无人机车辆路径问题研究

无人机参与配送是解决末端物流难题的重要途径之一。卡车搭载无人机协同配送模式,克服了无人机载重量小、续航时间短的弊端,成为无人机参与末端物流配送的重要形式之一。在疫区、灾区进行应急配送时,经常遇到由于道路毁坏或封锁、区域污染,导致部分路段车辆或无人机无法通行的情况。在非应急配送中,也可能存在车辆限行和空域禁飞等区域限制措施。区域限制给卡车搭载无人机物流配送路径优化问题带来了很大挑战。论文构建了区域限制条件下卡车搭载无人机车辆路径问题的混合整数线性规划模型,提出了一种结合最短路算法和禁忌搜索算法的混合算法,基于标准算例库设计测试集并进行测试实验,实验结果表明混合算法具有较好的计算性能。     

动态需求下车辆路径问题的周期性优化模型及求解

针对客户点不断更新的动态需求车辆路径问题,依据滚动时域对配送中心工作时间进行划分,提出基于延迟服务的周期性客户点实时重置策略,策略中延迟服务机制能结合车辆启动延迟系数对照当前时域的时间进行检验,满足所有客户点的服务需求,保证车辆满足中心时间窗约束。设计多阶段求解的混合变邻域人工蜂群算法对各时间片内子问题进行连续迭代优化,算法中子路径动态转变的设计能较好平衡原有客户点和新客户点对路径更新和车辆实时信息匹配的要求。算例验证及对比分析表明本文策略和算法在求解动态问题时的有效性和可行性。     

大规模邻域搜索算法求解时变车辆调度问题

对时变网络车辆调度问题提出一种满足先入先出准则的时变处理方法,并建立相应的数学模型,提出一种基于大规模邻域搜索技术的智能优化算法进行求解,算法顶层采用动态规划算法搜索环状交换邻域以得到每辆车的最佳服务顾客集合;底层设计动态搜索算法用以安排每辆车的最佳服务路线.在此基础上提出顶层加入虚拟顾客和底层嵌入insert两类改进策略.通过实验仿真比较,验证了所提算法的有效性.     

基于免疫遗传算法的物流配送车辆路径优化问题研究

物流配送车辆的优化调度问题是近年来物流研究中的一个热点也是一个难点,传统的优化方法往往难以解决这类问题.本文提出一种新型免疫遗传算法进行物流配送车辆路径问题的优化规划.在遗传进化过程中,借鉴生物免疫机制对每个种群的染色体进行免疫算子操作,这些算子包括接种疫苗、各基因座多样性调整以及免疫选择.以运输费用最小为优化目标建立了物流配送车辆路径优化问题的数学模型,利用免疫遗传算法求得优化解,并通过具体实例以及免疫遗传算法与标准遗传算法运算结果的比较,验证了本文免疫遗传算法的有效性和优越性.     

物流配送系统中车辆路径问题仿真优化及其进展

物流配送系统中车辆路径问题的仿真研究是用系统仿真与优化的方法解决车辆路径问题,将车辆路径问题与物流系统仿真优化这两个研究领域相融合.综述了车辆路径问题模型与算法及物流系统仿真与优化国内外的研究成果,分析了这些研究领域存在的主要问题,在此基础上提出了用仿真优化方法求解物流配送系统的车辆路径问题的原理与方法,并通过实例验证了该方法的有效性,为进一步的研究奠定了基础.     

车辆路径问题的模型及算法研究综述

本文在文献[1,2,3,4]的基础上,首先,介绍了车辆路径问题的分类和限制条件;然后,全面综述了国内外关于车辆路径问题的模型及算法研究现状,重点探讨了车辆路径问题的模型构造、求解算法及其适用范围;最后,展望了其研究的前景。     

基于需求预测的两级动态配送路径优化研究

针对传统响应式配送难以应对海量动态客户需求的困境,在此提出基于需求预测的两级动态配送路径优化方法。利用历史数据从需求预测、需求聚类和需求配额三个维度,处理电商物流配送过程中的动态需求;建立基于需求预测的单阶段和多阶段两级车辆配送路径优化模型,并针对问题特性利用分支定界算法与CW-禁忌搜索算法生成两个阶段的最优配送路径。最后结合实验案例对模型与算法的有效性进行验证,试验结果表明本文设计方法具有较好的动态场景适应度和客户响应能力。     

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

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

基于改进模糊遗传算法的混合车辆路径问题

本文建立了多配送中心、多车型、多产品的车辆路径问题的混合数学模型,提出了一种新的模糊遗传算法求解混合车辆路径问题,通过改进的模糊逻辑控制器实现交叉概率和变异概率的动态调整,以加快算法收敛速度并避免算法陷入局部最优解。采用标准算例进行对比,证明模糊遗传算法有较好的计算结果和计算效率,并用模糊遗传算法对混合车辆路径模型进行仿真测试,取得了理想的结果。     

运力受扰的多车场车辆调度干扰管理问题研究

为解决物流配送系统中因运输车辆毁坏而产生的干扰问题,基于干扰管理思想提出了解决问题的扰动恢复策略与实施方案。在扰动度量的基础上,设计了多车场车辆调度扰动恢复策略,建立相应的干扰管理模型。针对多车场车辆调度干扰管理问题的特有属性,设计了一系列求解简化策略,有效简化了问题的求解空间。结合干扰管理模型的特点,使用改进的遗传算法进行求解。最后给出了一个算例,其结果证明了干扰管理模型与算法的有效性。     

多车型车辆路径问题的量子遗传算法研究

本文在分析现有文献中多车型车辆路径问题中车辆使用优先原则的基础上,将车辆使用费用分为固定费用和油耗费用,并建立以配送总费用最小为优化目标的数学模型。设计量子遗传算法对模型进行求解,采用量子比特位设计染色体结构,改进遗传算法中交叉与变异算子,避免优秀基因不被破坏,设计快速寻优机制与最优保留机制,增强的求解效率。最后,结合算例对模型和算法进行了检验与分析。     

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

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

A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree

This paper presents a new approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot. Customers are located on vertices of the tree, and each customer has a positive demand. Demands of customers are served by a fleet of identical vehicles with limited capacity. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. Each tour begins at the depot, visits a subset of the customers and returns to the depot without violating the capacity constraint. We propose a 1.35078-approximation algorithm for the problem (exactly, ), which is an improvement over the existing 1.5-approximation.