最优有序路径关键词查询

为了实现最优有序路径关键词查询,提出了基于动态阈值的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)航路规划问题,引入惯性权重和自然选择对粒子群算法进行优化,以提高基本粒子群算法收敛速度,防止陷入局部最优.算法分析惯性权重对粒子群算法的影响,进而调整惯性因子,提高算法的搜索能力;利用自然选择的便利性和规律性等特点,更新粒子群算法的粒子;同时通过对无人机的可行航向进行限定,缩小搜索范围.仿真实验表明:基于粒子群优化算法的无人机航路规划不仅缩短了最优航路,而且提高了搜索速度.     

Exploring older women's confidence during route planning

In-car route guidance is automatic, requiring a minimum of time and thinking. This paper explores the use of personalised information when providing instructions for navigating a journey. We focus on older women with a lifetime of experience. Ten female participants were interviewed to elicit their comfort zone with respect to navigating in a car from their own home. Two routes were then devised for each participant, which extended beyond this comfort zone, and presented to them in two different formats. Participants then navigated the route of their least preferred format. Questionnaires and interviews were used to explore the effects of the formats on their confidence, cognitive effort and use of cognitive mapping facilities. The questionnaire data showed that the more detailed instructions supported cognitive mapping processes and the interviews suggested that this support was valued prior to executing the route.     

Dynamic route planning with real-time traffic predictions

Situation aware route planning gathers increasing interest as cities become crowded and jammed. We present a system for individual trip planning that incorporates future traffic hazards in routing. Future traffic conditions are computed by a Spatio-Temporal Random Field based on a stream of sensor readings. In addition, our approach estimates traffic flow in areas with low sensor coverage using a Gaussian Process Regression. The conditioning of spatial regression on intermediate predictions of a discrete probabilistic graphical model allows us to incorporate historical data, streamed online data and a rich dependency structure at the same time. We demonstrate the system with a real-world use-case from Dublin city, Ireland.     

Database support for mobile route planning systems

The impact of tele and mobile information technology will increase the need for fast access to geodata significantly in the next years. However, hitherto many problems concerning the wireless access to geodata e.g. to be used in route planning clients are not yet solved. Beside transaction management the requirements of route planning systems to GIS technology mainly concern the modelling and management of graph-based geodata. New challenges to meet are the efficient storage of routes and the supply of location-based database queries. However, today's first commercial database management systems for mobile devices do not support spatial database queries. In this article we collect requirements and present a first implementation prototype of a mobile route planning system focusing on the support of spatial database queries. First experiences with a mobile bicycle route planning client coupled with a database management system are presented. We show that at the server side the computation and storage of different route types as well as the generation of routes under consideration of semantic information like tourist information or roads with certain points of interest should make up the main functionality of such a system. The mobile client should supply database support for the location-based visualization of routes and an offline data management of route data.     

Exploiting domain geometry in analogical route planning

Abstract. Automated route planning consists of using real maps to automatically find good map routes. Two shortcomings to standard methods are (1) that domain information may be lacking, and (2) that a ‘good’ route can be hard to define. Most on-line map representations do not include information that may be relevant for the purpose of generating good realistic routes, such as traffic patterns, construction, and one-way streets. The notion of a good route is dependent not only on geometry (shortest path),but also on a variety of other factors, such as the day and time, weather conditions,and perhaps most importantly,user-dependent preferences. These features can be learned by evaluating real-world execution experience. These difficulties motivate our work on applying analogical reasoning to route planning. Analogical reasoning is a method of using past experience to improve problem solving performance in similar new situations.Our approach consists of the accumulation and reuse of previously traversed routes. We exploit the geometric characteristics of the map domain in the storage, retrieval, and reuse phases of the analogical reasoning process. Our route planning method retrieves and reuses multiple past routing cases that collectively form a good basis for generating a new routing plan. To find a good set of past routes, we have designed a similarity metric that takes into account the geometric and continuous-valued characteristics of a city map. The metric evaluates its own performance and uses execution experience to improve its prediction of case similarity, adaptability and executability. The planner uses a replay mechanism to produce a route plan based on analogy with past routes retrieved by the similarity metric. We use illustrative examples and show some empirical results from a detailed on-line map of the city of Pittsburgh, containing over 18,000 intersections and 25,000 street segments.     

基于多属性优先级的动态路径规划方法

针对现存大多数动态路径规划算法目标单一问题进行研究,提出基于理想点的多属性决策方法解决该问题,属性的选取融合时间、路程及现代最为重视的安全因素,使得动态路径规划的结果更加均衡。同时在多属性决策过程中引入优先级这一概念,使得驾驶员可以根据自身的需求及驾驶技术对交通信息的重要度进行排序,得到匹配度最高的驾驶方案。仿真结果表明,基于多属性优先级的动态路径规划算法既能够起到多目标均衡的路径规划效果,同时又能够实现个性化驾驶。     

Time-optimal and privacy preserving route planning for carpool policy

To alleviate the traffic congestion caused by the sharp increase in the number of private cars and save commuting costs, taxi carpooling service has become the choice of many people. Current research on taxi carpooling services has focused on shortening the detour distances. While with the development of intelligent cities, efficiently match passengers and vehicles and planning routes become urgent. And the privacy between passengers in the taxi carpooling service also needs to be considered. In this paper, we propose a time-optimal and privacy-preserving carpool route planning system via deep reinforcement learning. This system uses the traffic information around the carpooling vehicle to optimize passengers’ travel time, not only to efficiently match passengers and vehicles but also to generate detailed route planning for carpooling vehicles. We conducted experiments on an Internet of Vehicles simulator CARLA, and the results demonstrate that our method is better than other advanced methods and has better performance in complex environments.

     

用户优化选线模型及其收敛性研究

从交通规划及结构优化的角度出发,将交通流均衡和拓扑优化算法引入道路选线问题,提出用户优化模型及其收敛算法。通过连续交通流均衡分配模型,描述通勤者的出行行为;有限元方法与渐进结构优化算法相结合,找到城市区域内流量密度最集中且均匀分布的地区,并将其作为初始设计阶段的城市主干道位置。最后给出数值算例,其结果证明了模型和算法的有效性。     

Improved route planning and scheduling of waste collection and transport

The collection of waste is a highly visible and important municipal service that involves large expenditures. Waste collection problems are, however, one of the most difficult operational problems to solve. This paper describes the optimization of vehicle routes and schedules for collecting municipal solid waste in Eastern Finland. The solutions are generated by a recently developed guided variable neighborhood thresholding metaheuristic that is adapted to solve real-life waste collection problems. Several implementation approaches to speed up the method and cut down the memory usage are discussed. A case study on the waste collection in two regions of Eastern Finland demonstrates that significant cost reductions can be obtained compared with the current practice.     

A personalized route recommendation service for theme parks using RFID information and tourist behavior

Like any other industry, theme parks are now facing severe challenges from other entertainment competitors. To survive in a rapidly changing environment, creating high quality products/services in terms of consumer preference has become a critical issue for theme park managers. To fulfill these needs, this paper develops a route recommendation system that supplies theme park tourists with the facilities they should visit and in what order. In the proposed system, tourist behaviors (i.e. visiting sequences and corresponding timestamps) are persistently collected through a Radio-Frequency Identification (RFID) system and stored in a route database. The database is then segmented into sub-groups based on the similarity among tourists’ visiting sequences and time lengths. Whenever a visitor requests a route recommendation service, the system identifies the sub-group most similar to that visitor's personal preferences and intended visitation time. Based on the retrieved visiting behavior data and current facility queuing situation identified by the RFID system, the proposed system generates a proper route suggestion for the visitor. A simulation case is implemented to show the feasibility of the proposed system. Based on the experimental results, it is clear that the recommended route satisfies visitor requirements using previous tourists’ favorite experiences.     

A metaheuristic approach to fisheries survey route planning

Every autumn, a research vessel carries out a sampling survey tour to estimate the abundance of groundfish species of the Portuguese continental waters. The sampling operations are carried out at predefined geographical locations, the fishing stations, within predefined multiple time windows. The vessel route starts and ends at the port of Lisbon, and must visit all fishing stations. According to a predefined periodicity, the vessel must enter a port to supply food, refuel, and/or change crew. Given the geographical locations of the fishing stations/ports and current weather conditions, the objective is to minimize the total traveled distance and completion time. We present a mixed integer linear program to describe the problem and propose two sequential heuristic approaches that combine genetic algorithms and adaptive large neighborhood search to solve it. Computational experience with real data shows that the proposed heuristics are suitable tools to solve the problem.