Optimal Path Finding Method Study Based on Stochastic Travel Time

Finding optimal path in a given network is an important content of intelligent transportation information service. Static shortest path has been studied widely and many efficient searching methods have been developed, for example Dijkstra’s algorithm, Floyd-Warshall, Bellman-Ford, A* et al. However, practical travel time is not a constant value but a stochastic value. How to take full use of the stochastic character to find the shortest path is a significant problem. In this paper, GPS floating car is used to detect road section’s travel time. The probability distribution of travel time is estimated according to Bayes estimation method. The combined probability distribution of a feasible route is calculated according to probability operation. The objective function is to find the route that has the biggest probability to arrive for desired time thresholds. Improved Genetic Algorithm is used to calculate the optimal path. The efficiency of the proposed method is illustrated with a practical example.

汽车白车身点焊作业多机器人路径规划研究

针对白车身焊装生产线多机器人焊接工作量大、焊接工作复杂的问题,提出了一种自适应精英蚁群算法的多机器人焊接路径规划方法。在蚁群算法的基础上,对算法核心参数进行调整,再将自适应更新策略和精英蚂蚁系统加入到蚁群算法中,增强算法全局搜索能力,提高算法收敛速度,并通过TSP模型检验了算法的性能;最后,以白车身焊装生产线某车型主拼工位的焊接作业为例,对方法的有效性进行了验证。结果表明,改进后的蚁群算法具有较好的搜索效率和搜索能力,多机器人焊接路径间不相交,符合焊接的工艺要求,为多机器人焊接路径规划问题提供了一种新的方法。

全并联AT牵引供电系统雷击故障测距多路径行波算法研究

针对AT变压器和并联结构导致行波传播路径复杂,行波波头性质难以有效识别和行波色散现象,线路频变参数特性导致波速不稳定的问题,提出一种基于多路径行波测距方法。基于上下行电流行波传播的差异性,利用电流相似度识别故障区段。探讨全并联AT牵引网结构对行波传播特性的影响,并对电流、电压行波传播路径进行标定。基于多路径电流、电压行波极性分析,筛选出用于故障测距的多路径行波,以推导出消去波速的测距方程。仿真表明:所提测距方法可以有效识别波头性质,且计算故障距离基本与波速无关,不受牵引网区段长度、结构影响。

Complete Coverage Path Planning Based on Improved Area Division

It is difficult to solve complete coverage path planning directly in the obstructed area. Therefore, in this paper, we propose a method of complete coverage path planning with improved area division. Firstly, the boustrophedon cell decomposition method is used to partition the map into sub-regions. The complete coverage paths within each sub-region are obtained by the Boustrophedon back-and-forth motions, and the order of traversal of the sub-regions is then described as a generalised traveling salesman problem with pickup and delivery based on the relative positions of the vertices of each sub-region. An adaptive large neighbourhood algorithm is proposed to quickly obtain solution results in traversal order. The effectiveness of the improved algorithm on traversal cost reduction is verified in this paper through multiple sets of experiments. .

基于驾驶习惯的综合评分法识别车辆出行路径

大数据背景下,为交通规划分析提供OD数据的关键技术是基于电子警察识别城区车辆的出行路径。首先,获取车辆在路网中的过车信息和互联网平台提供的实时路况信息,进行多次迭代计算获取路径接近真实的旅行时间,从而确定车辆的最优行驶路径集;然后,分析设计了路径旅行时间、路径转弯数量和路径节点周期长度作为影响驾驶习惯三因素的归一化计算方法;最后,采用综合评分法确定车辆相邻检测点间最大可能行驶路径。采用模拟验证方法,获取车辆的最优路径集,采用问卷调查获取路径影响因素权重,归一化处理得出不同路径的评分矩阵,综合评分选择出相邻检测点间最大可能路径与车辆实际行驶路径一致。结果表明了该方法的可用性。

研学旅行课程开发质量评价体系研究

研学旅行是中小学综合实践活动的重要形式,是发展学生核心素养的创新人才培养途径。研学旅行课程开发质量直接影响研学旅行的科学性、规范性和有效性。为优化研学旅行课程开发质量,先运用模糊德尔菲法构建包括课程开发者知识基础、课程开发内容和课程开发过程3个维度的研学旅行课程开发质量评价体系,再运用DEMATEL运算数据并绘制各个维度或指标之间的影响网络关系图。结果显示:课程开发过程最容易受到其他维度的影响,而课程开发者知识基础对其他维度的影响力最大。在此基础上确定了研学旅行课程开发质量改善路径。

Improved ant colony optimization algorithm for the traveling salesman problems

Ant colony optimization(ACO) is a new heuristic algorithm which has been proven a successful technique and applied to a number of combinatorial optimization problems.The traveling salesman problem(TSP) is among the most important combinatorial problems.An ACO algorithm based on scout characteristic is proposed for solving the stagnation behavior and premature convergence problem of the basic ACO algorithm on TSP.The main idea is to partition artificial ants into two groups:scout ants and common ants.The common ants work according to the search manner of basic ant colony algorithm,but scout ants have some differences from common ants,they calculate each route's mutation probability of the current optimal solution using path evaluation model and search around the optimal solution according to the mutation probability.Simulation on TSP shows that the improved algorithm has high efficiency and robustness.

Seismic ray-tracing calculation based on parabolic travel-time interpolation

A new seismic ray-tracing method is put forward based on parabolic travel-time interpolation(PTI) method, which is more accurate than the linear travel-time interpolation (LTI) method. Both PTI method and LTI method are used to compute seismic travel-time and ray-path in a 2-D grid cell model. Firstly, some basic concepts are introduced. The calculations of travel-time and ray-path are carried out only at cell boundaries. So, the ray-path is always straight in the same cells with uniform velocity. Two steps are applied in PTI and LTI method, step 1 computes travel-time and step 2 traces ray-path. Then, the derivation of LTI formulas is described. Because of the presence of refraction wave in shot cell, the formula aiming at shot cell is also derived. Finally, PTI method is presented. The calculation of PTI method is more complex than that of LTI method, but the error is limited. The results of numerical model show that PTI method can trace ray-path more accurately and efficiently than LTI method does.

Niche pseudo-parallel genetic algorithms for path optimization of autonomous mobile robot

A new genetic algorithm named niche pseudo-parallel genetic algorithm (NPPGA) is presented for path evolution and genetic optimization of autonomous mobile robot. The NPPGA is an effective improvement to maintain the population diversity as well for the sake of avoiding premature and strengthen parallelism of the population to accelerate the search process combined with niche genetic algorithms and pseudo-parallel genetic algorithms. The proposed approach is evaluated by robotic path optimization, which is a specific application of traveler salesman problem (TSP). Experimental results indicated that a shortest path could be obtained in the practical traveling salesman problem named “Robot tour around Pekin”, and the performance conducted by NPPGA is better than simple genetic algorithm (SGA) and distributed paralell genetic algorithms (DPGA).

Applying the Method for Solving Traveling Salesman Problem Based on Backtracking Algorithm to Order Picking

In the distribution center, the way of order picking personnel to pick goods has two kinds: single picking and batch picking. Based on the way of the single picking and assumed warehouse model, in order to reduce the walking path of order picking, the order picking problem is transformed into the traveling salesman problem in this paper. Based on backtracking algorithm, the order picking path gets optimized. Finally verifing the optimization method under the environment of VC++6.0, order picking path in the warehouse model get optimized, and compared with the traditional order picking walking paths. The results show that in small and medium-sized warehouse, the optimization method proposed in this paper can reduce order picking walking path and improve the work efficiency as well as reduce the time cost.

疫情背景下铁路旅客安全出行路径规划方法

为降低疫情期间旅客出行感染风险,助力科学精准的疫情防控,提出考虑实时区域感染风险的铁路旅客安全出行路径动态规划方法。首先,基于概率风险理论,将区域感染风险定义为区域疫情爆发概率和疫情影响程度的函数,考虑旅客交流强度、区域人口及流动性,评估区域感染风险;其次,综合考虑区域感染风险、旅行时间与旅行费用,运用Logit模型得到广义出行成本,将路网相邻服务节点间的广义成本作为网络边的权值,进而构建考虑旅行感染风险的铁路出行服务网络;最后,基于疫情背景下旅客出行需求与出行路径决策原则,建立以广义出行成本最低为目标的铁路旅客安全出行路径规划模型,并运用Dijkstra算法求解。以衡水至北京的路径选择为案例,将所提方法与仅考虑旅行时间、旅行费用的路径规划方法进行对比,并分析各路径方案实际客流分担率的变化。研究结果表明:基于铁路服务网络的旅客出行数据,利用所提方法可以评估疫情感染风险,且风险评估结果与实际感染人数存在显著相关性;旅行感染风险是影响旅客选择出行路径的重要因素,造成了广义出行成本显著增加,所提方法的路径规划结果与疫情期间旅客实际出行特征基本相符。

Path planning for unmanned aerial vehicles in surveillance tasks under wind fields

The optimal path planning for fixed-wing unmanned aerial vehicles(UAVs) in multi-target surveillance tasks(MTST) in the presence of wind is concerned.To take into account the minimal turning radius of UAVs,the Dubins model is used to approximate the dynamics of UAVs.Based on the assumption,the path planning problem of UAVs in MTST can be formulated as a Dubins traveling salesman problem(DTSP).By considering its prohibitively high computational cost,the Dubins paths under terminal heading relaxation are introduced,which leads to significant reduction of the optimization scale and difficulty of the whole problem.Meanwhile,in view of the impact of wind on UAVs' paths,the notion of virtual target is proposed.The application of the idea successfully converts the Dubins path planning problem from an initial configuration to a target in wind into a problem of finding the minimal root of a transcendental equation.Then,the Dubins tour is derived by using differential evolution(DE) algorithm which employs random-key encoding technique to optimize the visiting sequence of waypoints.Finally,the effectiveness and efficiency of the proposed algorithm are demonstrated through computational experiments.Numerical results exhibit that the proposed algorithm can produce high quality solutions to the problem.

城市居住区位与出行行为对通勤者生活质量的影响研究--以上海市为例

城市交通规划的关注点正在从交通效率到生活质量转变,而居住地区位是影响出行行为的重要因素。文章基于POI数据,从一般建成环境、交通可达性和公交设施分布3个方面描述居住地区位。以上海为例,基于路径分析模型,研究城市居住区位和出行行为在通勤满意度和生活时间分配的中介效应下,对通勤者的生活质量影响。研究揭示了通勤者生活质量的多层次影响机制,并量化了通勤时长对生活时间分配的影响,可以为城市交通规划与土地利用决策提供参考。

基于二分法和控制信息素量的改进蚁群算法

为弥补蚁群算法易陷入局部最优、收敛速度较慢等不足,提出一种基于二分法和控制信息素量的改进蚁群算法。在每次迭代结束时,利用二分法放弃行走路程较远的半数蚁群的信息素,使收敛速度得到提高;利用3-opt局部优化方法提高解的精度;通过控制信息素量动态调整蚁群选择路径的概率,避免算法早熟;将改进的算法应用于旅行商问题。实验结果表明,该算法在寻优能力、可靠性、收敛速度以及稳定性方面均表现出明显的优越性。

基于路径拼接模型的路径行程时间估计方法

依托卡口检测数据,提出路径拼接模型以利用大量短路径行程时间对城市道路中的长路径行程时间进行估计。该模型提出子路径进行拼接时要满足的两个条件:存在公共结点及交通状态相近;在此基础上将目标路径按照整体方差最小的原则拆分为由多个子路径组成的拼接方案。基于提出的路径交通流基本图划分子路径的交通状态,使用Burr分布拟合不同交通状态下的子路径行程时间得到行程时间分布函数;将给定的目标行程时间分配至拼接方案中的子路径使得子路径行程时间之和等于目标行程时间,累加所有时间分配方案对应的概率得到目标路径的行程时间概率,计算多个目标行程时间对应的概率得到目标路径的行程时间概率分布。实验结果显示:本文提出的路径行程时间估计方法得到的路径行程时间均值与真实轨迹均值的误差为3.04%;得到的行程时间分布与真实行程时间分布的JS散度为0.05。路径行程时间估计值真实可靠,可为后续研究提供数据基础。

基于隐私计算的行程轨迹求交方案的性能研究

云计算、大数据、物联网及人工智能等技术的快速发展在给人们生活带来便利的同时,也造成隐私泄露和信息滥用等问题,因此在不泄露行程轨迹的情况下对行程轨迹求交问题具有重要的现实意义。提出两种多维行程轨迹数据集隐私集合求交方案,并进行了性能分析实验验证。实验结果表明,基于Rivest-Shamir-Adleman(RSA)公钥密码体制的隐私集合求交方法具有较高的运算效率,而基于Ben-Or-Goldwasser-Wigderson(BGW)秘密共享的隐私集合求交方法支持更复杂的运算,从而可实现近似求交。由此提出结合两方法特点、取长补短的综合方案。

空铁复合超网络中旅客快速组合出行路径规划

针对中长途旅客组合出行规划困难、规划路径个性化不足等问题,以航空网络、高铁网络以及空铁换乘网络三者构成的空铁复合超网络作为网络基础,综合考虑出行时间、出行费用、方便性、舒适性和可靠性5个影响因素,并借助旅客时间价值进行量纲一致化处理,构建出以旅客效用最大化为目标的组合出行路径选择模型。从旅客角度出发,将旅客细分为时间敏感型和价格敏感型,采用深度优先遍历算法求解出网络中的有效及最优组合出行路径,以期为异质性旅客提供更加精细化的出行方案,同时为相关部门合理配置空铁运力资源、提升空铁运输效能提供理论参考。通过“北京-广州”的算例分析,证明了模型和算法的可行性和有效性,能够实现组合出行路径的有效识别,而旅客类型影响最优出行路径的结果。

数据驱动的城轨列车延误下乘客出行时空路径选择模型

研究列车延误下乘客的出行路径选择有助于地铁客流预测与客流组织。为此构建一个利用自动售检票(AFC)数据和列车实际运行时刻驱动的列车延误下乘客出行时空路径选择模型,基于贝叶斯定理估计乘客各出行时空路径的选择概率,并采用蒙特卡洛仿真方法得到乘客出行时空路径选择结果,从而获取不同路径的选择比例。最后使用北京地铁实际列车延误场景进行实验,选取典型OD对比分析了正常情况与列车延误下的乘客出行时空路径选择。实验结果表明,提出的模型可以计算得到列车延误下乘客出行物理路径和乘车方案的选择概率;概率模型在多次仿真中产生的路径选择比例呈现出稳定趋势;并且乘车方案概率统计反映出延误会给乘客带来更多滞留等待。同时实验结果证明,乘客会因列车延误增加的时间成本而更倾向于绕行选择受延误影响较小换乘次数较多的路径。

基于出行者偏好特征的路径诱导方法研究

针对存在出行者偏好的最优路径选择问题,提出了一种基于出行者偏好特征的路径诱导方法。建立了以行驶距离、行驶时间、拥挤程度、出行费用、转弯次数、沿途景观、信号灯数量、出行经验、车辆组成成分、道路等级为指标的路径诱导体系。首先,利用灰色关联分析法,建立出行者主观偏好和路径属性贴合度最大的优化模型,并采用基于偏好的遗传算法进行求解,得到路径指标的权重值,由此求得路径综合属性值。其次,建立各个路径间的可能度矩阵及排序向量,据此选出符合出行者偏好的最优路径。最后,以桂林交通网络进行算例验证,结果表明该方法具有很好的普适性。

农业机器人底盘关键技术研究现状分析

底盘总成是自走式农业机器人的重要组成部分,其性能优劣直接影响机器人的作业质量和效率。随着我国精准农业、智慧农业的迅猛发展,机器人技术在现代农业生产中的应用日益广泛,尤其是机器人底盘技术,集中在底盘技术的定位建图、路径规划和自主避障等方面,承载了机器人整体的定位、导航及避障等基本功能。本文基于现阶段国内外农业机器人底盘技术的发展概况,主要对我国农业机器人底盘定位建图、路径规划以及自主避障等关键技术的研究现状进行分析,并针对目前我国农业机器人底盘技术存在的不足,提出了未来农业机器人底盘技术的研究方向与展望,为智慧化现代农业生产中机器人技术深入研究和持续发展提供参考。