Dijkstra算法在地理信息系统中的优化实现

分析介绍了Dijkstra最短路径搜索算法在地理信息系统中的优化实现。     

无容量约束单分配轴-辐式物流网络设计

针对无容量约束的单分配轴-辐式物流网络设计问题的特点,为其建立了单分配p-枢纽中位模型,并提出了一种基于蚁群算法的启发式求解算法. 该算法分两步实现：首先利用蚁群算法来确定网络中枢纽节点的位置,然后用另一种启发式算法将非枢纽节点分配给枢纽节点,同时,将一种基于6种邻域结构的变邻域搜索算法作为蚁群算法的局域搜索策略以提升算法的全局搜索能力,并加快收敛速度. 最后结合澳大利亚邮政数据进行了算例仿真实验,并对蚁群算法中参数的合理设置进行了测试分析,实验结果表明,该算法在求解此问题时有着良好的有效性和较快的求解效率.     

求解广义最小生成树问题的元启发式算法

针对广义最小生成树问题,设计了2种改进的元启发式算法来求解：单亲遗传模拟退火算法和改进的禁忌搜索算法。通过综合遗传算法和模拟退火算法的优点,提出了单亲遗传和模拟退火的混合算法,并设计了自适应选择法和自适应基因重组操作;在改进的禁忌搜索算法中,通过在2种邻域进行搜索来避免陷入局部最优。数值实验验证了算法的有效性。     

居住区共享停车泊位分配模型

为了提高停车泊位利用率,减少停车后步行距离,根据商业区和居住区停车需求时段的错峰特征,建立共享停车泊位利用率最大化和步行距离最小化的双目标泊位分配模型.模型考虑了停车泊位供需空间和时间冲突特征,界定了模型的边界约束条件,采用粒子群多目标搜索算法求解.以聊城市金鼎商圈为例,调研了商业区和居住区的停车泊位数量、高峰时段停车需求和平均步行距离等模型参数.通过算法仿真,实验结果验证了模型的可行性.研究结果表明,建立的停车共享分配模型可用于居住区共享停车泊位分配,有效地提高了泊位利用率,降低了停车后的平均步行距离.     

路径诱导问题中Dijkstra算法和矩阵迭代算法的比较研究

Dijkstra算法和矩阵迭代算法都是最短路径问题的经典算法,为了研究这2种算法的计算效率,介绍了2种算法的基本思路和程序流程;通过对时间复杂度、结果和时间的关系指标进行多次计算,表现2者之间的效率差异.比对结果显示:矩阵迭代算法较Dijkstra算法速度快;随着交叉口数的增加,前者较后者速度优势更加显著;前者计算思路较后者简洁,便于计算机程序的编写.     

基于填挖匹配与智能优化算法的土石方调配优化

土石方调配是工程项目建设中的重要组成部分,对降低工程成本、缩短施工工期有重要意义。土石方调配问题中的填挖匹配与运输路径规划是密切联系的两个阶段,传统的土石方调配问题主要聚焦于如何解决填-挖方间的土石方匹配问题,而对施工机械运输路径规划研究得较少。为此,以最小施工费用与最小机械转运距离为优化目标,对土石方调配中两阶段问题进行了模型构建与算法研发。针对填挖匹配问题,构建了土石方填挖匹配模型与线性规划求解算法,获取了最优填挖匹配方案;针对土石方运输路径规划问题,分别采用禁忌搜索算法、模拟退火算法获取了土石方运输路径方案。最后,以某土石方调运项目为例,采用土石方两阶段调配模型与两种求解算法进行求解,实验结果表明两阶段调配模型与算法可有效地对土石方调配问题进行求解,算法求解时间可控制在5 s以内。     

基于改进Dijkstra算法的路径优化仿真研究

文章针对传统Dijkstra算法在路径优化过程中存在的不足,从路网拓扑关系存储和快速搜索技术两方面对其进行了改进,得到了一种改进的Dijkstra算法,并通过实例仿真分析,验证了该算法的有效性。     

考虑时间窗的通勤定制公交线路优化

针对常规定制公交线路规划方法不能满足乘客高峰通勤需求等问题,在考虑乘客期望时间窗和最大容忍时间窗的基础上,引入柔性时间窗的概念,基于通勤者居住地与工作地时空分布差异性特点分别设置上下车站点罚函数,以车辆固定成本、车辆运行成本、车辆延误惩罚成本和未提供乘车服务惩罚成本之和最小为优化目标,以时间窗、运行距离和最大站点数量等为约束,建立考虑柔性时间窗的通勤定制公交线路优化模型。在兰州市通勤乘客数据基础上,选取两组大小不同规模的算例集,使用Gurobi和传统TS算法求解小规模算例与基于目标控制原则的动态禁忌长度TS算法求解大规模算例验证模型有效性。结果表明,在小规模算例中Gurobi求解可得到较优的目标值,但随着数据规模的增加其求解效率逐渐劣于TS算法,设置柔性时间窗车辆提供乘车服务的人数比硬时间窗背景下增加了276人,且有效规避了软时间窗背景下车辆到达末站点的时刻波动。本文所提方法在均衡乘客和运营方利益的同时,可通过调节柔性系数产生多元化的运行方案,能够为通勤定制公交运营及管理提供决策支持。     

人工智能在船舶航行数学建模中的应用

为保障船舶在海上安全航行,提出人工智能在船舶航行数学建模中的应用。使用Maklink图论方法描述海上作业点分布,建立作业点Maklink连接图,生成船舶在作业水域内可航行网络图。建立船舶在海上作业区域航线规划数学模型,并设置约束条件;利用Dijkstra算法求解船舶在海上作业危险区域航线规划模型,得到船舶航行初始航线;利用人工智能算法内的蚁群优化算法对船舶航行初始航线实时优化处理,得到船舶航行最终航线,为船舶穿越海上作业区域实时导航。实验结果表明,该方法可有效生成船舶在作业水域航行网络图,得到初始航线并对初始航线优化处理,应用效果较佳。     

Graph and hint based algorithm for machining feature automation recognition and mapping

Feature recognition is a process of extracting machining features which has engineering meaning from solid model, and it is a key technology of CAD/CAPP/CAM integration. This paper presents an effective and efficient methodology of recognizing machining feature. In this approach, features are classified into two categories: pocket feature and predefined feature. Different feature type adopts its special hint and heuristic rule, and is helpful to recognize intersection feature. Feature classification optimizes search algorithm and shortens search scope dramatically. Meanwhile, extension and split algorithm is used to handle intersecting feature. Moreover, feature mapping based on machining knowledge is introduced to support downstream application better. Finally, case studies with complex intersecting features prove that the developed approach has stronger recognizing ability.