两级选址--路径问题的大规模邻域搜索模拟退火算法

针对目前越来越普遍的多级配送模式,建立以总成本最小为目标函数的两级选址-路径问题模型,并提出了大规模邻域搜索模拟退火算法进行求解.在模拟退火算法框架中,嵌入大规模邻域搜索过程,包含破坏、重组和局部搜索方法,从而进一步提高算法在解空间中构建邻域的范围.采用两级选址-路径问题标准算例对算法求解效果进行验证,并与标准模拟退火算法和国际已知最优解进行对比.结果显示,所建模型和算法正确有效,并且在求解大规模问题时算法能够取得相对更好的优化结果.     

基于改进分散搜索算法的无人机路径规划

针对在敌情信息不明环境中无人机侦查路径规划问题,建立了车辆路由问题模型(VRP),提出了基于分散搜索的改进混合搜索算法.基于Bayes方法计算出点到点之间的威胁概率,并生成了一个赋权图,将无人机路径规划问题转化为车辆路由寻优模型.采用混合路径规划算法求解.该算法将模拟退火嵌入到分散搜索算法的框架中,充分利用了分散搜索的全局搜索能力与模拟退火的局部搜索能力来优化无人机的侦查路径,混合算法在保证时效性的同时提升了求解的质量.仿真结果验证了算法的有效性.     

求解VRPBTW的变邻域搜索算法

以电子商务环境下物流配送为背景,建立了带有时间窗和回程载货约束的车辆路径问题优化模型,设计了改进的变邻域搜索求解算法.该算法采用改进的Braysy顺序插入法生成问题初始解,再根据变邻域搜索算法机制应用4种不同搜索范围的局域搜索算子对初始解进行改进.通过对多个算例的求解实验,并与采用一般流程的变邻域搜索算法进行比较,结果表明所提出的变邻域搜索算法的求解效果明显优于采用一般流程的变邻域搜索算法,是求解该类问题的有效算法.     

黄金正弦模拟退火算法求解低碳有能力约束的车辆路径问题

针对模拟退火算法局部搜索能力不强、收敛速度慢,以及接受准则的盲目性等弊端,提出一种基于黄金正弦的模拟退火算法。首先采用黄金正弦算法的遍历特点优化模拟退火算法的初始值,然后对模拟退火算法的邻域搜索进行扩充,增加基于概率的多种算子邻域搜索和记忆装置,适当提高退火温度等措施,很大程度上提高了算法的全局优化性能。通过物流运输实例对低碳和成本节约型的多目标有能力约束的车辆路径问题(capacitated vehicle routing problem,CVRP)模型求解,以寻找环境友好型绿色路径。实验仿真表明,该混合算法具有很好的优化性能,对于求解此类车辆路径问题具有很好的优化效果。     

考虑GIS的物流配送区域划分与路径规划算法

针对大规模VRP配送问题,提出一种配送区域划分的启发式-模拟退火混合搜索算法.针对GIS中实际路网建立路网数学模型,并在大规模VRP路径规划问题研究中与实际GIS路网相融合.对配送路径规划问题提出一种结合GIS模型约束的启发式路径搜索算法.对杭州市某配送区域实际问题求解并与另一种启发式算法对比,验证了算法的有效性.     

两级车辆路径问题的多起始点变邻域下降算法

两级车辆路径问题是指货物必须首先由中心仓库配送至中转站(第一级),再转运至需求点(第二级)的一种新型车辆路径问题.针对该问题特性,提出一种多起始点变邻域下降求解算法.首先由改进的Split算法循环分割由所有需求点组成的随机排列,直至出现可行的第二级配送方案,然后求解第一级问题,获得完整的初始可行解,再通过变邻域下降算法进一步改进.当变邻域下降算法无法改进时,采用多起始点技术重复上述过程,直至算法终止.实验结果表明,所提出的算法易于实现,且性能优于已有最好的两种启发式算法.     

面向移动机器人快速全局路径规划的改进跳点搜索算法

针对传统全局路径规划算法计算量大,寻路时间过长等问题,为了进一步提高移动机器人综合作业能力,本文提出了一种基于跳点搜索算法的快速全局路径规划算法,旨在减少时间成本,以满足移动机器人在实际复杂环境中对智能性、高效性、安全性和可靠性的要求。首先通过“块”操作方法,在一次搜索中快速扫描底层网格中的一个区域,将跳点搜索算法的修剪规则一次应用于多个节点,减少搜寻跳点时所涉及的大部分迭代计算,并在采取“对角优先”方式的前提下,剔除仅具有改变方向的中间转折点,大量减少Openlist和Closedlist的不必要节点,减少计算量,提高路径规划的实时性。为了验证改进算法的有效性与可行性,分别在规则的网格地图、测试库基准地图及移动机器人Turtlebot2进行仿真实验验证,结果表明在生成相同路径的基础上,改进跳点搜索算法与A*算法相比扩展节点数目缩减了68.9%,搜索耗费时间降低了71.9%;与传统跳点搜索算法相比,扩展节点数目缩减了41.3%,搜索耗费时间降低了33.4%,能够满足移动机器人快速全局路径规划的要求。     

基于模拟退火算法的曲面最短路径求解

通过对路径的节点序列内在关联性的分析，提出了适合曲面最短路径问题的邻域结构，使整段路径的优化问题能够通过局部得以实现，将模拟退火算法的框架引入路径寻优中，提出了解决曲面最短路径的随机搜索算法。最后给出了数值仿真实例。     

一种移动机器人三维路径规划优化算法

对移动机器人在三维工作环境中障碍物位置和形状已知条件下的全局路径规划问题进行研究.机器人的初始路径取为出发点到目标点的直线路径,引入人工神经网络结构和模拟退火温度定义路径能量函数;根据多面体形障碍物的形状特征设定各边界面不等的模拟退火初始温度,并且对路径点位于障碍物内、外的不同情况建立不同的运动方程;提出一种基于神经网络结构能量函数的路径规划算法及其优化算法,对所提路径规划算法进行仿真研究.研究结果表明,该算法是一种有效的移动机器人三维路径规划算法;算法计算简单,不存在组合爆炸问题;可避免路径规划的某些局部极小值问题;优化算法能够规划出移动机器人最短避障路径,并且可加快路径规划收敛速度.     

基于改进麻雀搜索算法及动态窗口法的路径规划

对于麻雀搜索算法收敛中期局部探索能力不足、在路径规划方面路径不平滑且动态避障能力差的缺点。首先针对麻雀搜索算法局部探索能力的不足,利用混沌映射初始化种群,并且利用上一代全局最优解与动态自适应权重优化发现者位置更新方式;然后,使用一种线性路径策略,减少折点与节点数量;最后,针对其路径不平滑,动态避障能力差的缺点,将优化后的麻雀搜索算法与动态窗口法融合。实验结果表明改进的麻雀搜索算法与动态窗口法融合算法平衡了全局与局部发掘能力,加快了寻路过程的收敛速度,优化了路径且避障能力显著提高。     

禁忌搜索算法求解带时间窗和多配送人员的车辆路径问题

【目的】为了求解带时间窗和多配送人员的车辆路径问题,建立了该车辆路径问题的数学模型,并采用禁忌搜索算法进行求解。【方法】首先松弛车辆载重和顾客时间窗约束,在目标函数里面引入相应的惩罚成本;接着,使用贪婪算法生成初始解;最后,设计禁忌搜索算法求解该问题。在禁忌搜索中,使用了插入、删除、移动、交换等算子搜索邻域解空间,并使用扰动算子进一步加大搜索范围。为了验证禁忌搜索算法的有效性,对修改的Solomon标准测试问题进行求解,并与CPLEX的优化结果进行比较。【结果】在小规模算例求解中证实了禁忌搜索算法的准确性,在标准规模算例求解中证实了该算法的高效性。【结论】所提出的禁忌搜索算法能够有效解决带时间窗和多配送人员的车辆路径问题。     

多策略蚁群算法求解机器人路径规划

针对基本蚁群算法的缺点,提出用多策略的蚁群算法求解机器人路径规划问题.采用栅格法建立机器人全局路径规划工作空间模型,进行两次凸化改进处理.提出惩罚策略,并配合使用保健算子策略、治病算子策略,同时引入遗传算子策略、精英蚂蚁策略和最大最小蚂蚁策略.介绍在Matlab环境下编程实现的方法及步骤,求解100个栅格点的路径规划问题,得到最优距离为15.070.仿真结果表明,即使在复杂的地形环境中用本算法也可迅速规划出令人满意的最优路径.     

改进邻域搜索算法的矩形件排样优化研究

针对矩形件排样问题,给出精确的数学优化模型,提出一种改进邻域搜索算法的求解方法.为了克服一般邻域搜索算法易陷入局部最优解和搜索效率低的缺点,挖掘矩形件排样的问题特征,提出反悔算子、距离受限邻域算子、以"满足容忍度"接受劣解等3种新的改进策略.以矩形件排放顺序为编码,利用"最下左填充算法"进行解码,优化矩形件排样方案.对...     

基于打破对称性的快速寻路算法

基于Java实现了跳点搜索算法,给出了算法实现的过程.实验结果表明:跳点搜索算法找到了一条从起始节点到目标节点的最优路径,且能够有效地识别和消除网格地图上的路径对称性,大幅度减少了节点扩展的数量.对比A*、宽度优先搜索、最佳优先搜索和Dijkstra可知,在所求解的路径长度一致的情况下,跳点搜索在平均搜索时间上显著快于其他算法.因此,跳点搜索是快速、高效的.     

基于混沌优化算法的车辆路径规划问题研究

考虑节点连通关系约束和路段通行能力差异的车辆路径规划（Vehicle Routing Problem,VRP）问题比传统的路径规划问题更为复杂,有效的求解算法一直是研究的关键问题。本文分析了该类VRP问题的数学模型,提出了一种针对该问题的混沌优化算法,介绍了具体的编码方法和实现算子。最后通过仿真实验,验证了所提算法的有效性。     

A*算法与蚁群算法相结合的无人艇巡逻路径规划

针对无人艇海上巡逻路径规划问题,提出了一种A~*算法与蚁群算法相结合进行最短巡逻路径优化的方法.在传统A~*算法的八角度搜索基础上,设计了一种多角度A~*算法以获得更短的两点之间可行路径,并以A~*算法搜索结果构建任意两个巡逻点之间的最短路径网络.结合最短路径网络建立多点巡逻路径规划问题的目标函数,利用蚁群算法进行求解以获得全局最优的巡逻路径.针对巡逻路径转折角较大的问题,提出了一种平滑算法以获得更符合实际航行需求的平滑路径.仿真结果表明:该方法有效地去除了冗余节点,缩短了路径长度,提高了路径平滑度,规划出了一条更优的无人艇巡逻路径.     

改进的引导式邻域搜索算法求解周期性车辆路径问题

在引导式邻域搜索算法静态惩罚策略的基础上,提出动态惩罚策略,设计改进的引导式邻域搜索算法,将其用于求解周期性车辆路径问题,采用标准算例进行数据实验,对动态与静态的惩罚策略进行对比.结果表明,采用改进的引导式邻域搜索算法求解周期性车辆路径问题可行有效.     

改进人工人群搜索算法在基于LBS物流配送中的应用

以基于LBS物流系统的物流车辆路径规划为研究对象,将一种改进人工势场法与人群搜索算法相结合,对LBS系统中物流车辆的路径规划进行优化.该算法首先利用LBS系统获取环境信息,包括车辆、目标和障碍物的位置和速度信息,其次在基本人工势场法的基础上加入速度因子,使配送车辆初步形成能躲避障碍物并追踪动态物流对象的可行性路径,随后利用人群搜索算法,在可行性路径中搜索最短路径,进而生成物流车辆至动态物流对象的最优路径.该算法有效的将改进式人工势场法和人群搜索算法紧密结合在一起,通过仿真实验证明了该算法在基于LBS的物流系统中物流配送路径规划的有效性,同时将该算法与传统路径规划A*算法进行对比,证明该算法有效的提高了系统中的整体搜索效率.     

基于改进遗传算法的移动机器人路径规划研究

针对传统遗传算法在解决采样点模型下的路径规划问题中存在种群进化速度慢、最终得到的最优路径偏长的问题,提出一种改进遗传算法．为提高初始种群的质量,提出自适应调整步长来限制子节点的选择范围,在这个范围内随机选取两条父代路径,在对应两节点之间形成一个矩形的子代节点搜索范围,每个范围中选取一点并依次连接得到交叉后的子代个体,避免了采样点模型下交叉点不足导致交叉无效的问题;为解决变异效果不可控的问题,以变异父节点的前后两点连线为引导,越靠近该连线的节点被选为变异子节点的概率越大,使得在变异点的选择更具有方向性．对比实验结果表明：所提出的改进遗传算法当处理基于采样点路径规划问题时可以有效提高寻路效率,最优路径收敛速度比传统遗传算法提高约60%,最优路径长度最多减少了2.42 m,比其他文献算法的最优路径收敛速度最多提高56%.     

面向大型工业仓库的多AGV综合优化调度方法

针对大型工业仓库中自动引导车(AGV)集群执行大规模任务时效率低的问题,提出一种基于分层规划的综合优化调度方法,将调度问题分解为聚合的上层任务定序分配问题和下层路径规划问题。在上层问题中生成精英解集,将下层路径规划生成的禁忌列表作为碰撞冲突约束条件融入上层问题迭代寻优过程,并在迭代搜索中,将路径规划结果反馈给上层问题并更新约束条件,通过上下两层问题的综合计算得到整体性能最优的方案。进一步将路径搜索和禁忌列表融合,实现AGV调度中相互关联的多个问题的同步优化。通过大型工业仓库实例验证该方法的有效性。研究结果表明：相较于依次优化调度方法,基于分层规划的综合优化调度方法的平均任务完成时间减少10.56%,碰撞冲突造成的延迟时间减少74.53%;相较于混合自适应大邻域搜索算法和预先规划算法,基于混合离散状态转移算法的分层规划综合调度方法对于大规模问题任务完成时间分别减少9.73%和5.54%,计算时间分别减少84.19%和86.68%。