一类半开放式车辆路径问题及其禁忌算法研究

对半开放式车辆路径问题进行了描述,提出了核心路径的概念和理论,并根据问题的特点设计了基于核心路径的禁忌算法.算法分为初始优化、核心路径的提取和连接以及后期优化三部分,采用自然数编码,用GENI插入法构造初始路径和进行邻域操作,设计了三种邻域以扩大搜索空间,用能力约束控制单条路径的配送点数,以增加惩罚的方式加入配送距离约束.算法利用核心路径的特点阻碍不良路径的生成,并在后期优化的第二阶段拆开核心路径,进行优化路径的调整.最后采用多组数据进行计算并对结果进行了分析,证明了基于核心路径禁忌算法对优化有能力和距离约束半开放式车辆路径问题的有效性.     

求解模糊需求车辆路径问题的两阶段变邻域禁忌搜索算法

模糊需求车辆路径问题(CVRPFD)是对带容量约束车辆路径问题(CVRP)的扩展,属于经典的NP难题,其求解与需求确定CVRP区别较大,较为复杂,具有很强的理论和现实意义.基于先预优化后重调度的思想,提出一种新的两阶段变邻域禁忌搜索算法(VNTS)对其求解:在预优化阶段,基于可信性理论构建模糊机会约束优化模型处理客户点模糊需求,设计VNTS求解预优化方案;在重调度阶段,设计随机模拟算法模拟客户点实际需求,提出一种新的点重调度策略对预优化方案进行调整.算例实验表明两阶段变邻域禁忌搜索算法是一种求解CVRPFD的有力工具,点重调度策略调整效果较佳.     

最小-最大车辆路径问题的禁忌搜索算法

在对最小-最大车辆路径问题进行描述的基础上,建立了该问题的基本数学模型。针对最小-最大车辆路径问题的目标是最小化整个线路的最长子线路,本文提出了改进的禁忌搜索算法,并用一些典型算例进行了验证。计算结果表明,用该算法求解最小-最大车辆路径问题,不仅可以取得较好的计算结果,而且算法的计算效率较高,收敛速度较快。     

带装载能力约束的开放式车辆路径问题及其禁忌搜索算法研究

对另一种类型的车辆路径问题——开放式车辆路径问题进行了研究 .提出了一种用于求解带装载能力约束的开放式车辆路径问题的禁忌搜索算法 .给出了算法对测试算例的运算结果 ,并与文献中目前最好的结果进行比较 .比较结果表明 ,在绝大多数情况下 ,该算法能求出更好的解 .     

不确定车辆数的车辆路径问题模型和混合算法

提出用遗传算法(Genetic Algorithms,GA)和禁忌搜索算法(Tabu Search Algorithm,TSA)结合求解不确定车辆数的车辆路径问题.首先描述了带有能力约束的VRP的数学模型,由于车辆数不确定,因此提出另一目标函数,即最小化车辆数,与最小化距离同为目标函数建立了双目标数学规划模型.在车辆数不确定的情况下,把聚类和排序有机地结合起来,并用GA和TSA相结合的混合算法对问题进行求解,即以GA为主,把TSA用在GA的变异操作中,增强算法的爬山能力.实验结果表明,混合算法获得的最好解、平均装载率和计算成本都比较令人满意.     

模糊需求信息条件下的车辆路径问题研究

在对模糊需求信息条件下的车辆路径问题进行简单描述的基础上，通过引入决策者主观偏好的概念，提出了解决该问题的一种基于模糊可能性的混合遗传算法．同时，在最小化车辆使用数与车辆行驶距离的目标下，通过随机模拟方法研究了决策者的主观偏好对最终决策目标的影响作用，并通过与其它计算方法的比较证明了基于模糊可能性的混合遗传算法的优越性．     

车辆路径问题的粒子群算法研究

车辆路径优化问题是一类具有重要实用价值的组合NP问题．粒子群算法(panicle swarm optimization)是一种新出现的群智能(swarm intellingece)优化方法，将其应用于车辆路径优化问题，构造车辆路径问题的粒子表达方法，建立了此问题的粒子群算法，并与遗传算法作了对比试验．结果表明，粒子群算法可以快速、有效求得车辆路径问题的优化解，是求解车辆路径问题的一个较好方案。     

一体化集货和配送车辆路径问题的混合遗传启发式算法

为满足电子商务客户多样化和个性化的需求,建立多约束条件的一体化集货和配送车辆调度模型.针对模型特点,采用混合遗传启发式算法求解.首先,采用自然数编码,可以使问题变得更简洁;用最佳保留选择法,以保证群体的多样性;用改进的顺序交叉算子避免优良基因片断在顺序交叉时被破坏,保证算法能够收敛到全局最优;其次,对混合遗传算法求得的精英种群进行禁忌搜索求解.通过实例计算表明,该算法好于单独使用遗传算法或是禁忌搜索算法.     

两阶段优化算法求解绿色装箱车辆路径问题

带二维装箱约束的绿色开放式车辆路径问题（green open vehicle routing problem with twodimensional loading constraints, 2L-GOVRP）是绿色开放式车辆路径问题和二维装箱问题的集成。以最小化燃油消耗量为优化目标建立了2L-GOVRP模型,并提出一种两阶段优化算法（two stage optimization algorithm, TSOA）进行求解。TSOA的第一阶段,针对车辆路径问题,设计自适应鲸鱼优化算法（adaptive whale optimization algorithm, AWOA）进行求解,从而确定车辆初步配送路径（即2L-GOVRP的初始解）,并采用4种变邻域局部操作进行局部搜索。TSOA的第二阶段,针对二维装箱问题,设计融入扰动机制的天际线填充算法（skyline filling algorithm combined with disturbance mechanism, SFA-DM）优化装箱过程,从而确保所有货物能够合理装箱。通过对不同客户规模测试数例的仿真实验和算法比较,验证了TSOA可...     

随机递归算法求解车辆路径问题

车辆路径问题(VRP)是组合优化中一个典型的NP难题,对于中等规模以上的问题,目前大多采用禁忌搜索、遗传算法和模拟退火等亚启发式算法,在吸取这些算法精髓的基础上,提出了一种新的并且简洁而高效的启发式算法.计算结果表明,在27个国际标准算例中应用该算法取得了2个解优于当前最优解,其余相当接近当前最优解.需要指出的是所有这些结果是在该算法应用同一组参数得到的.     

求解异车型同时集送问题的多属性标签算法

针对实际运输中顾客对不同车型、同时集送货物的多样化需求,文章建立了异车型同时集送车辆路径模型(vehicle routing problem with heterogeneous fleet,simultaneouspickup and delivery,VRPHSPD),并构建了基于多属性标签的蚁群系统算法(multi-label based ant colony system,MLACS)进行求解.该算法利用面向对象理念,分别对客户、车辆及其行驶路径构建多属性标签,首先用近邻法生成初始路径,再通过蚁群算法的搜索规则对客户和车辆标签进行匹配,从而得优化的结果.通过公开算例、实际应用案例的验证表明,MLACS算法能成功求解VRPHSPD问题,具有较高的求解质量、运算效率以及实际应用意义.     

分散搜索算法求解带货物权重的车辆路径问题

研究了由一个分销中心、多个零售商组成的分销网络中运输单产品考虑货物权重的车辆路径问题(weighted vehicle routing problem,WVRP).问题的目标是设计合理的路线最小化由于行驶距离,运输载重量及使用车辆而产生的总费用.针对问题的特点,设计了求解WVRP问题的分散搜索算法(scatter search algo-rithm,SS),该算法基于客户进行编码,以基于最优划分过程的随机初始化作为多样性产生方法,通过对不同解包括的弧组合来生成新解,并用最近邻法对解进行改进.分别采用了随机数据与标准数据对算法进行测试,并与其他求解该问题的算法进行了比较,说明了算法的有效性.     

油品配送车辆路径问题的交互式求解方法

油品配送车辆路径问题是一个多车场、多仓库、多商品、多舱位、多车型、有前序约束和时间窗,综合车辆分派、订单配载以及路径编排等决策的车辆路径问题.以两阶段启发式算法为基础,给出了求解该问题的人机交互式求解方法,即交互进行基于当前解的人工修改和启发式算法的寻优.其中包括了对初始解、搜索邻域和目标函数的人工修改,相应操作分别为修改解、局部固定解和调整惩罚乘子.     

两阶段启发式算法求解带时间窗的多中心车辆路径问题

车辆路径问题(VRP)是物流研究领域中一个具有重要理论价值和现实意义的问题. 带时间窗的多中心车辆路径优化问题(MDVRPTW)是单中心带时间窗的VRP(VRPTW)的一个扩展, 其非常复杂, 难于求解. 本文提出一个两阶段的启发式算法来求解MDVRPTW. 该算法首先通过基于聚集度的启发式分类算法将MDVRPTW简化为多个VRPTW; 然后采用蚁群算法对每个VRPTW进行求解. 为了提高蚁群算法的效率, 提出了两个改进策略: 交叉算子和自适应的ant-weight信息素增量更新策略. 最后, 通过若干经典的MDVRPTW对该算法进行了验证, 结果显示结合基于聚集度的启发式分类算法和改进的蚁群算法是一个求解MDVRPTW的有力工具.     

成像卫星集成调度的变邻域禁忌搜索算法

探讨了一类涉及多星、多地面站的成像卫星系统集成调度问题,要求从可能过度订购的卫星观测需求中,选择一个能够无冲突完成的任务子集,并为相应的观测和数据下传活动安排资源和时间,以最大化对所有用户需求的总体满足程度.建立了该问题的变体形式车辆路线问题模型,设计了改进型和调整型两类邻域结构,并提出了一种变邻域禁忌搜索算法.通过交替使用两类邻域结构,增强了算法对解空间的探索能力和规避局部极值的能力.测试算例的计算结果和与其它算法的比较表明,该算法能够在相近的计算时间内显著改善求解质量.     

多车型电动汽车车辆路径问题的分支定价算法研究

随着环境意识的日益提升和电动汽车的逐渐普及,考虑到物流企业中不同类型的电动汽车的电池最大容量、电池充电率、电量单位消耗率、最大载重量、固定成本和可变成本不同,本文研究含时间窗的多车型电动汽车车辆路径问题,建立了一个混合整数规划模型,并利用分支定价算法求其最优解.为了加快算法的求解速度,本文提出生成下界值的方法以对车辆类型进行预处理操作,并制定了生成整数解上界的策略以压缩解空间.然后,通过用多组算例验证了模型和算法结果的准确性,同时也证明了本文提出的加速过程能有效地提高算法的求解速率.最后,通过不同规模的算例分析了车辆可变成本的变化对结果的影响.     

动态规划启发式算法求解时变车辆调度问题

时变网络中车辆在任意两节点间的行驶时间不仅与节点间的距离有关, 还与所处的时段有关. 对时变车辆调度问题提出一种满足先入先出准则的跨时段处理方法, 直接推导出跨时段对应的车辆行驶时间. 在此基础上建立了数学模型, 并构造动态规划启发式算法进行求解. 该算法能够通过设置参数H平衡求解质量和运行时间. 通过对10组随机产生的数据进行测试, 结果表明动态规划启发式算法能够在很短时间内改进最近邻算法. 当H=2时, 求解质量改进11%, 平均运算时间为1.34秒; 当H=3时, 在不到2秒的运算时间内求解质量改进17%.     

集货需求随机的同时配集货VRP及混合变邻域搜索算法

集货需求随机的同时配集货车辆路径问题(VRPSSPDD)是同时配集货车辆路径问题(VRPSPD)研究的进一步深化,由于该问题中集货需求的不确定性,使其较确定型VRPSPD问题更为复杂.基于预优化和重优化策略,构建了两阶段VRPSSPDD模型,预优化阶段基于随机机会约束机制以及车载量约束为客户点分配车辆,生成预优化方案;重优化阶段对失败点及其后续客户点进行线路调整.根据问题特征,结合变邻域深度搜索算法的深度搜索能力以及遗传算法的个体交流等优点,设计混合变邻域遗传算法,采用分离配送网络信息的编码方式,提出自适应种群搜索范围和自适应邻域搜索次数策略平衡算法迭代中的搜索深度和搜索广度的关系.通过多组算例以及企业配送实例验证了本文模型及算法的有效性.