基于极小代数赋权有向图最短路径求解算法

应用极小代数给出了求解简单有向赋权图最短路径问题的代数算法.该算法基于赋权有向图的直接距离矩阵A,在极小代数意义下计算k步最短路径距离矩阵Ak和最短路径距离矩阵A+,并依此确定出赋权有向图的最短路径以及最少步数最短路径.与Dijkstra算法相比较,所提出的代数算法求解路径规划问题能够较快地得到特定的最短路径及其长度.     

基于蚁群算法的最短路径搜索方法研究

最短路径问题是在给定的网络图中寻找出一条从起始点到目标点之间的最短路径。蚁群算法是一种用于求解优化问题的新型模拟进化算法,该算法在许多相当困难的优化问题的求解中体现了极强的寻优能力和较好的性质。提出了一种利用蚁群算法来解决网络最短路径问题的新方法,并用Matlab语言编程进行算法的实现和仿真。结果表明,蚁群算法在寻求网络最短路方面的应用是可行的。     

综合运输网络中合理路径优化模型

为了提高多式联运经营人运输决策的科学性和可行性,建立了一个含路径合理性约束的联合运输路径优化模型.从货运生产实践角度出发,提出了联合运输合理路径概念.基于联合运输的实现流程,指出除了运输效益最大化外,合理的换装序列和换装次数限制是联合运输路径选择和优化必须要考虑的另外2个重要特性.对于一般联合运输问题,研究了运输总费用的构成,即直线运输费用、节点中转费用和超期惩罚费用.通过构建直观的联合运输网络图,以总运输成本最少为优化目标,将多方式联合运输合理路径的选择和优化问题转化为含有超期惩罚因子的广义最短路模型,对模型的假设和数学形式做了详细的描述,并提供了简要的求解思路和参考算法.     

数控加工中心任务与刀具集成调度模型及改进自适应遗传算法

为解决数控加工中心任务与刀具的集成优化调度问题,以生产总成本最小为优化目标,建立了考虑任务交货期和工步并行加工的数控加工中心任务与刀具集成调度模型,产生面向数控加工中心任务与刀具的协同优化调度结果。为实现对该调度模型的优化求解,提出了一种改进自适应遗传算法,设计了合理的编码方式和自适应进化操作,并通过任务-刀具关联矩阵保证搜索过程中解的可行性,从而显著提高了算法的收敛性能和求解效率。算例结果表明,该模型能够最大限度地降低加工成本和拖期率,同时算法的收敛速度和稳定性也得到了明显提高,大大降低了问题求解的迭代次数。     

K-Means聚类下的改进蚁群算法优化TSP问题

在解决旅行商问题(Traveling Salesman Problem,TSP)上,提出了一种新的求解思路即基于K-means聚类思想下的改进型蚁群算法,目的 是优化TSP最短路径.先将整体TSP中分布的全部节点利用K-means聚类思想将其分成若干子TSP,再通过对基础蚁群算法(Ant Colony Algorith...     

交通拥堵情况下的多温共配车辆路径优化

针对实际配送过程中,经常会出现由于交通事故、上下班高峰期以及交通限流等因素导致的交通拥堵情况,为保证多温共配路径优化结果能更符合实际情况,提出了一种基于交通拥堵的多温共配优化模型,相较于传统的多温共配的路径优化模型,该模型更符合实际的运输情况.由于路径优化问题属于NP难问题,故采用随机自适应遗传算法进行求解,求出在总成本最优的情况下使路径最短、总成本最少的最佳配送路径.通过对比遗传算法和用Cplex求解,发现两者结果接近,且算法更为快速,更加适合大规模求解.算例分析结果表明:考虑了拥堵情况的路径优化,相较于没有考虑拥堵情况的路径优化,运输成本下降了16.74%.     

基于动态优化双钻头打孔机生产效能的研究

首先,对孔型加工及走刀方式进行分析,为提高打孔机效能,采用两钻头同时作业的方式。然后,根据相关的数据,应用动态优化的相关理论建立数学模型,并运用遗传算法进行求解,从而确立了双钻头作业时的最优作业线路、最佳行进时间和作业成本,并用MATLAB编写程序画出了相应图形,更加形象地显现出了各个路段的最优作业方案。     

基于k-臂分子求解最短路径的DNA计算模型

为有效求解最短路径问题, 避免传统算法计算量大、 求解时间长的问题, 充分发挥DNA(Deoxyribo Nuclec Acid)计算的并行性在求解复杂计算问题的优势, 提出一种基于k-臂分子和粘贴计算求解最短路径问题的DNA计算模型, 阐述了顶点、边及权值的编码方案, 描述了求解最短路径的DNA算法, 经验证, 该模型对求解最短路径问题是有效的。     

改进的基于关系数据库技术的公交查询算法

为满足公众对出行路径的多样性需求,针对目前公交查询算法的不足,提出改进的基于关系数据库技术的公交查询算法.该算法依据"最优路径的子路径都是最优路径"理论,通过换乘次数小的最优路径逐步求取换乘次数大的最优路径,并利用关系数据库技术进行最优路径集合的生成和优化,从而实现大规模公交网络的多目标路径搜索.以北京公汽网络作为算例,分别以最短出行时间、最小换乘次数、最少出行费用为评价标准编制程序搜索最优路径,结果表明最短出行时间算法的多目标搜索结果最优,查询速度快,具有推广价值.     

基于风险态度的紧急物资保障方案研究

从全局上考虑紧急物资保障的路径选择问题和保障点组合问题，建立了基于风险态度的紧急物资保障规划模型。在路径选择问题中，用区间数表示网络权值，用偏好结构因子来表示决策者的风险态度，群组决策确定网络权值，求取保障点到需求点的最短路径；在多保障点组合问题中，以最早保障时间为约束条件，最少保障点数目为目标函数，建立了保障方案优化模型，从而在全局上解决了紧急物资保障问题，最后给出了一个算例。     

求解最短路径问题的DNA动态规划算法

最短路径问题是一个组合优化问题,许多交通运输、工程、管理等实际问题可转化为最短路径问题进行求解。文中利用DNA计算的并行计算模式,给出一个求解最短路径问题的DNA动态规划算法,该算法最多需要7n-11个生物操作。     

求解MDVRP问题的混合蚊子追踪算法

针对现实生活中应用广泛的多车场车辆路径优化问题,建立相应的数学模型。根据"就近原则"将MDVRP问题分解为VRP问题,再根据约束条件的限制将VRP分解为TSP问题,提出一种蚊子追踪算法对TSP求解,详细介绍了蚊子追踪算法的理论基础和求解模型。仿真结果表明,该算法是有效可行的,并优于遗传算法、禁忌搜索和蚁群算法,且证明了该算法对求解这类NP完全问题有一定的指导意义。     

求最短路径问题的自适应路由遗传优化算法的设计与实现

从最短路径问题的研究背景、最短路径问题概述、求解最短路径问题的自适应路由遗传优化算法的设计及其实现等方面提出了一种新的求解最短路径问题的自适应路由遗传优化算法,实验仿真比较了该算法与Dijkstra算法的路由过程、算法的收敛性和执行的效率,结果初步证明该算法高效可行,尤其适合于大规模网络.     

基于最短路搜索的多路径公交客流分配模型研究靠

提出了一种首先采用最短路算法搜索有效路径集,再根据有效路径的广义费用,由改进的Logit模型确定每条有效路径的选择概率,进而计算每条线路客流量的公交客流分配模型.其中,任意两交通区之间的有效路径集是以换乘次数最少为准则,通过对不同选择情况下公交路网进行最短路搜索而获取.该模型既体现了乘客的费用最小的选择心理,又反映了出行线路多样性的实际情况,而且算法简单、有效.初步实践证明,具有较强的实用性.     

具有局部重复路径的多路旅行商问题的研究

首先对连通图上允许旅行商走回头路的TSP的问题进行了研究,证明了问题解的存在性,给出了利用连通图的顶点间最短路径构造完全图的求解方法.然后,对连通图上允许路径部分重复的MTSP问题进行了初步的研究;采取"分治"的方法并结合遗传算法,设计了求解路径部分重复的MTSP问题的有效算法.讨论了关于求解多个旅行商完成任务的最短时间和最短路径的问题;并给出了在限定时间内完成任务的条件下,求最小分组(人员配置)的问题的方法.可重复路径的MTSP问题的研究,在现实中有很大的使用价值.诸如:交通运输、管道铺设、路线的选择、计算机网络的拓扑设计、邮递员送信等,都可以抽象成TSP或MTSP问题来求解.     

基于改进K最短路算法的公交线网优化研究

文章研究了公交场站选址和线网设计组合优化问题,建立以站间直达为关键约束的线网优化模型并给出求解算法。在所构建的公交网络中,利用改进的K最短路算法和相应的路径筛选条件获得从节点出发的K最短路径树,找出符合条件的单个K最短路径树作为初始解;通过不同节点的K最短路径树的叠加、删除、替代的优化过程,获得最优的K最短路径树组合,得到最优的公交线路集、场站位置。算例结果表明:公交网络规模越大,所需场站越多;K值越大,所需场站越少;不同场站可相互配合进行布局,实现公交线网性能的提升。     

时变路网下VRP准时路径的选择

基于节约里程法求解多回路运输问题(VRP), 得到了在时变路网下要求准时性高的路径选择问题. 考虑时变路网中顺畅和拥堵概率, 路径最短不一定用时最少, 通过实例对距离、 时间、 费用等因素进行分析、 拟合, 对比了不同因素下路径选择和时限内的准时稳定性等情况. 结果表明, 优化后的配送路径可以保证配送的稳定性.     

基于最短路搜索的多路径公交客流分配模型研究

提出了一种首先采用最短路算法搜索有效路径集，再根据有效路径的广义费用，由改进的Logit模型确定每条有效路径的选择概率，进而计算每条线路客流量的公交客流分配模型。其中，任意两交通区之间的有效路径集是以换乘次数最少为准则，通过对不同选择情况下公交路网进行最短路搜索而获取。该模型既体现了乘客的费用最小的选择心理，又反映了出行线路多样性的实际情况，而且算法简单、有效。初步实践证明，具有较强的实用性。     

改进蚁群算法在小规模TSP问题中的参数问题

本文主要讨论改进蚁群算法在小规模的TSP问题上,各参数设置对算法性能的影响,并通过仿真实验,合理设置相关参数,把得到的最终求解模型引入到超市B2C客服配送中的车辆路径优化决策系统,通过算例比较,证明其优越性能.     

最大路径算法在原条量材优化中的应用及其优化

在分析求解最短路径问题与求解最大路径问题差异的基础上,给出了一种在有向图中采用动态规划策略求解最大路径的算法,将其应用到原条量材网络图中求解原条最优量材问题;并提出了采用量材三角形优化原条量材网络图的一种优化方法,降低了算法的复杂度.通过实验验证了算法与优化方法的正确性与可行性.