最优有序路径关键词查询

为了实现最优有序路径关键词查询,提出了基于动态阈值的OSRK迭代算法,通过不断缩小阈值来过滤不可能出现在最优有序路径中的空间对象,同时在迭代添加路径时,删除不包含给定关键词的空间对象,能够有效地减少候选空间数据集的大小,提高查询响应性能。通过实验验证了算法的有效性。     

The optimal sequenced route query

Real-world road-planning applications often result in the formulation of new variations of the nearest neighbor (NN) problem requiring new solutions. In this paper, we study an unexplored form of NN queries named optimal sequenced route (OSR) query in both vector and metric spaces. OSR strives to find a route of minimum length starting from a given source location and passing through a number of typed locations in a particular order imposed on the types of the locations. We first transform the OSR problem into a shortest path problem on a large planar graph. We show that a classic shortest path algorithm such as Dijkstra’s is impractical for most real-world scenarios. Therefore, we propose LORD, a light threshold-based iterative algorithm, which utilizes various thresholds to prune the locations that cannot belong to the optimal route. Then we propose R-LORD, an extension of LORD which uses R-tree to examine the threshold values more efficiently. Finally, for applications that cannot tolerate the Euclidean distance as estimation and require exact distance measures in metric spaces (e.g., road networks) we propose PNE that progressively issues NN queries on different point types to construct the optimal route for the OSR query. Our extensive experiments on both real-world and synthetic datasets verify that our algorithms significantly outperform a disk-based variation of the Dijkstra approach in terms of processing time (up to two orders of magnitude) and required workspace (up to 90% reduction on average).     

The partial sequenced route query with traveling rules in road networks

In modern geographic information systems, route search represents an important class of queries. In route search related applications, users may want to define a number of traveling rules (traveling preferences) when they plan their trips. However, these traveling rules are not considered in most existing techniques. In this paper, we propose a novel spatial query type, the multi-rule partial sequenced route (MRPSR) query, which enables efficient trip planning with user defined traveling rules. The MRPSR query provides a unified framework that subsumes the well-known trip planning query (TPQ) and the optimal sequenced route (OSR) query. The difficulty in answering MRPSR queries lies in how to integrate multiple choices of points-of-interest (POI) with traveling rules when searching for satisfying routes. We prove that MRPSR query is NP-hard and then provide three algorithms by mapping traveling rules to an activity on vertex network. Afterwards, we extend all the proposed algorithms to road networks. By utilizing both real and synthetic POI datasets, we investigate the performance of our algorithms. The results of extensive simulations show that our algorithms are able to answer MRPSR queries effectively and efficiently with underlying road networks. Compared to the Light Optimal Route Discoverer (LORD) based brute-force solution, the response time of our algorithms is significantly reduced while the distances of the computed routes are only slightly longer than the shortest route.     

旅游路线规划研究综述

旅游业的快速发展和用户分享内容的激增使得旅游领域的信息过载问题日益突出，如何帮助游客在快速制定个性化游览路线的同时提升旅行体验，成为当前旅游路线规划问题研究的关键。首先，给出旅游路线规划问题的形式化定义；然后，将文献中的旅游路线规划求解方法分为基于精确数学建模的求解、基于用户生成内容的求解两大类，对各类方法的关键技术和存在的主要问题进行了较为详细的考察；最后，给出一个旅游路线规划系统整体架构，对其中存在的重点和难点问题进行了分析，为旅游路线规划问题的研究提供理论支持的同时指明了下一步的研究方向。     

Railway route planning in Australia

A software company and major travel agent have jointly developed an expert/information retrieval system. The system maps out itineries through Australia's complex rail network. Queries on this subject had previously always been passed to the human expert.     

User-adapted travel planning system for personalized schedule recommendation

Recently, the Internet has made a lot of services and products appear online provided by many tourism sectors. By this way, many information such as timetables, routes, accommodations, and restaurants are easily available to help travelers plan their travels. However, how to plan the most appropriate travel schedule under simultaneously considering several factors such as tourist attractions visiting, local hotels selecting, and travel budget calculation is a challenge. This gives rise to our interest in exploring the recommendation systems with relation to schedule recommendation. Additionally, the personalized concept is not implemented completely in most of travel recommendation systems. One notable problem is that they simply recommended the most popular travel routes or projects, and cannot plan the travel schedule. Moreover, the existing travel planning systems have limits in their capabilities to adapt to the changes based on users’ requirements and planning results. To tackle these problems, we develop a personalized travel planning system that simultaneously considers all categories of user requirements and provides users with a travel schedule planning service that approximates automation. A novel travel schedule planning algorithm is embedded to plan travel schedules based on users’ need. Through the user-adapted interface and adjustable results design, users can replace any unsatisfied travel unit to specific one. The feedback mechanism provides a better accuracy rate for next travel schedule to new users. An experiment was conducted to examine the satisfaction and use intention of the system. The results showed that participants who used the system with schedule planning have statistical significant on user satisfaction and use intention. We also analyzed the validity of applying the proposed algorithm to a user preference travel schedule through a number of practical system tests. In addition, comparing with other travel recommendation systems, our system had better performance on the schedule adjustment, personalization, and feedback giving.     

乘客运输的车辆路径规划策略

针对乘客运输问题,提出一种基于粒子群算法的乘客运输车辆路径规划策略。初始化阶段对n个站点、m辆车的乘客运输问题编码成一个（n+2m）维的粒子。迭代阶段对粒子进行解码,将一个（n+2m）维的粒子解码为m辆车的行走路径,对路径进行“移除－插入额外站点”优化。实验结果表明,该策略能有效地解决乘客运输车辆路径规划问题,达到总路程最短、车辆数目最少、服务的乘客数多,减少运输成本的目的。     

Automatic route planning for GPS art generation

Computational Visual Media - In this paper, we present a novel approach to automated route generation of global positioning system (GPS) artwork. The term GPS artwork describes the generation of...     

运钞车车辆路径规划策略

针对实际运钞网点数每天动态变化问题,提出一种先划分、再优化的动态运钞车路线规划策略。第一阶段先采用Dijkstra算法求出两点之间的最短路径,再利用最近邻算法和均衡工作量因子求出动态需求车辆的车辆数和每条路径上的网点;第二阶段利用前置交叉的改进遗传算法,分别优化每条路径并求出每条路径上的网点顺序,获得距离最短和时间最少的路径。实验结果表明,该策略能有效解决车辆数目和路径根据需求动态变化的问题,达到节约和合理利用资源的目的。     

基于优化粒子群算法的无人机航路规划

针对粒子群优化(PSO)算法的无人机(UAV)航路规划问题,引入惯性权重和自然选择对粒子群算法进行优化,以提高基本粒子群算法收敛速度,防止陷入局部最优.算法分析惯性权重对粒子群算法的影响,进而调整惯性因子,提高算法的搜索能力;利用自然选择的便利性和规律性等特点,更新粒子群算法的粒子;同时通过对无人机的可行航向进行限定,缩小搜索范围.仿真实验表明:基于粒子群优化算法的无人机航路规划不仅缩短了最优航路,而且提高了搜索速度.