出租车数据的城市道路网路段通行时间估计方法

城市路段通行时间估计能够更好地运营和管理城市交通。针对包含起点-终点位置,行程时间和距离信息的GPS行程数据,提出了一种城市道路网短时通行时间的估计模型。首先将城市道路网按照交叉路口分解为多个路段,并基于k-最短路径搜索方法分析司机行进路线。然后针对每一个路段,提出了双车道通行时间多项式关联关系模型,既能提升道路网通行时间精细度,又能避免因训练数据不足导致的路网通行时间过拟合问题。最后以最小化行程期望时间和实际行程时间之间的均方误差为优化目标,拟合道路网通行时间。在纽约出租车数据集上的实验结果表明,所提模型及方法相对于传统单车道估计方法能够更准确地估计城市道路网路段的通行时间。     

SMashQ: spatial mashup framework for k-NN queries in time-dependent road networks

The k-nearest-neighbor (k-NN) query is one of the most popular spatial query types for location-based services (LBS). In this paper, we focus on k-NN queries in time-dependent road networks, where the travel time between two locations may vary significantly at different time of the day. In practice, it is costly for a LBS provider to collect real-time traffic data from vehicles or roadside sensors to compute the best route from a user to a spatial object of interest in terms of the travel time. Thus, we design SMashQ, a server-side spatial mashup framework that enables a database server to efficiently evaluate k-NN queries using the route information and travel time accessed from an external Web mapping service, e.g., Microsoft Bing Maps. Due to the expensive cost and limitations of retrieving such external information, we propose three shared execution optimizations for SMashQ, namely, object grouping, direction sharing, and user grouping, to reduce the number of external Web mapping requests and provide highly accurate query answers. We evaluate SMashQ using Microsoft Bing Maps, a real road network, real data sets, and a synthetic data set. Experimental results show that SMashQ is efficient and capable of producing highly accurate query answers.     

Enjoy the most beautiful scene now: a memetic algorithm to solve two-fold time-dependent arc orienteering problem

Traditional route planners commonly focus on finding the shortest path between two points in terms of travel distance or time over road networks.However,in real cases,especially in the era of smart cities where many kinds of transportation-related data become easily available,recent years have witnessed an increasing demand of route planners that need to optimize for multiple criteria,e.g.,finding the route with the highest accumulated scenic score along(utility)while not exceeding the given travel time budget(cost).Such problem can be viewed as a variant of arc orienteering problem(AOP),which is well-known as an NP-hard problem.In this paper,targeting a more realistic AOP,we allow both scenic score(utility)and travel time(cost)values on each arc of the road network are time-dependent(2TD-AOP),and propose a memetic algorithm to solve it.To be more specific,within the given travel time budget,in the phase of initiation,for each population,we iteratively add suitable arcs with high scenic score and build a path from the origin to the destination via a complicate procedure consisting of search region narrowing,chromosome encoding and decoding.In the phase of the local search,each path is improved via chromosome selection,local-improvement-based mutation and crossover operations.Finally,we evaluate the proposed memetic algorithm in both synthetic and real-life datasets extensively,and the experimental results demonstrate that it outperforms the baselines.     

基于候客点规划的空闲出租车路线推荐算法

为空闲出租车司机推荐有效的闲逛路线在提高出租车司机工作效率、减少乘客等待时间以及缓解交通压力方面具有重要作用。现有的研究工作主要集中于为空闲司机推荐完整的驾驶路线,没有考虑到真实路网环境下某些路段的可等待因素,使得推荐的路线因载客概率较低、行驶距离较长而花费成本较高。提出一种基于候客点规划的路线推荐算法,对出租车轨迹数据进行处理,并设计路径匹配算法将每个轨迹点与真实路段一一匹配。通过统计每个路段历史接载信息,并利用一种改进的多层感知机建立可预测时序接载概率的模型,结合路段的可等待因素设计一种最小花费成本的路线推荐算法。在真实数据集上的实验结果表明,与MNP、InExperence、Random算法相比,所提算法花费成本、巡航时间以及巡航路程均明显减少。     

Cognition-based hierarchical en route planning for multi-agent traffic simulation

The goal of this study is to model drivers’ cognition-based en route planning behaviors in a large-scale road network via the Extended Belief-Desire-Intention (E-BDI) framework. E-BDI is a probabilistic behavior modeling framework based on agents’ own preferences of multiple attributes (e.g., travel time and its variance) and daily driving experiences. However, it is challenging to use the E-BDI framework for the demonstration of drivers’ en route planning behavior in a large-scale road network due to its high computational demand. To handle the computation issue, a hierarchical en route planning approach is proposed in this study. The proposed E-BDI-based en route planning approach consists of three major procedures: (1) network partitioning, (2) network aggregation, and (3) E-BDI-based en route planning. The Java-based E-BDI module integrated with DynusT^® traffic simulation software is developed to demonstrate the proposed en route planning approach in Phoenix, Arizona road network involving 11,546 nodes and 24,866 links. The demonstration results reveal that the proposed approach is computationally efficient and effective in representing various en route planning behaviors of drivers in a large-scale road network.     

Healthier routes planning: A new method and online implementation for minimizing air pollution exposure risk

Air pollution exposure during daily traveling is growing as an increasingly serious factor affecting public health with rapid incensement of travel distance in urban sprawl. Finding a healthier route with least exposure risk might be an alternative way to mitigate adverse health outcomes under the truth that worldwide air pollution in urban area cannot be eliminated within a short period of time. Integrating techniques of fine scale mapping of air pollutant concentration, risk weight estimation of road segment exposure to air pollutants, and dynamic Dijkstra algorithm capable of updating route, this study for the first time proposes a healthier route planning (HRP) method to minimize personal travel exposure risk to air pollution. Effectiveness of HRP in mitigating exposure risk was systematically tested based on hundred pairs of origins and destinations located in Beijing-Tianjin-Hebei (BTH) of China with necessarily dense air quality observations. Results show that the spatiotemporal variations of air pollutant concentrations were significant and these differences indeed occurred with time at hourly scale. Meanwhile, the grid-based estimation of exposure risk is time dependent with risk ranging from 5 to 109, which echoes the necessity of healthier route planning. Compared to routes with the shortest distance and least travel time, healthier route has the least exposure risk. And this risk mitigation effect is more significant in areas with wide exposure risk variations than those in areas without obvious risk difference over space (e.g., 21.38% vs. 0.86%). Results suggest that HRP method is promising to minimize personal exposure risk during daily travel based on the accurate exposure risk estimation of road segment at high spatiotemporal resolution. This role could be more important in areas with longer travel distance and greater heterogeneous distribution of air pollution in great metropolis.     

面向高速公路通行时间分布预测的时空混合密度神经网络

准确的通行时间分布预测可以全面地反映高速公路路网中各个路段在未来的通行状况,辅助实现高速公路中的路径规划,事故事件预警等精细化管理目标.为此,本文提出一种面向高速公路通行时间分布预测的时空混合密度神经网络.具体地,本文利用自适应图卷积通过数据驱动的方式提取路网中的空间特征,有效解决了基于预定义图难以捕获路网信息中完整空间相关性的问题.在时间维度上,不同时间的路网信息存在显著的相关性,因此,本文基于注意力机制自适应建模路网信息的时间相关性,并通过卷积层进一步聚合相邻时间步之间的信息.最后,基于自适应时空相关性建模得到的路段嵌入表示,通过混合密度网络建模通行时间的分布,以实现高速公路中各个路段的通行时间分布预测.     

基于非参数密度估计的不确定轨迹预测方法

随着大量移动设备的出现，准确和高效的轨迹预测有助于提高面向位置的应用和服务的质量和水平.针对现有方法对轨迹不确定性缺乏有效建模的问题，提出了基于非参数密度估计的不确定轨迹终点预测方法.在轨迹建模及模型训练阶段，利用非参数估计对起点与终点相同的轨迹构建基于密度分布的不确定轨迹模型；在轨迹预测阶段，将待预测轨迹视为轨迹数据流，并通过KS（Kolmogorov-Smirnov）检验方法与具有相同起点的不确定轨迹模型进行匹配，其中匹配程度最高的不确定轨迹即为预测轨迹.通过真实轨迹数据集上的实验表明，与现有各类主要轨迹预测方法相比，本方法在不同条件下的预测效率与准确性都有较明显优势.     

Real-time energy optimization of HEVs under-connected environment: a benchmark problem and receding horizon-based solution

In this paper, we propose a benchmark problem for the challengers aiming to energy efficiency control of hybrid electric vehicles (HEVs) on a road with slope. Moreover, it is assumed that the targeted HEVs are in the connected environment with the obtainment of real-time information of vehicle-to-everything (V2X), including geographic information, vehicle-toinfrastructure (V2I) information and vehicle-to-vehicle (V2V) information. The provided simulator consists of an industriallevel HEV model and a traffic scenario database obtained through a commercial traffic simulator, where the running route is generated based on real-world data with slope and intersection position. The benchmark problem to be solved is the HEVs powertrain control using traffic information to fulfill fuel economy improvement while satisfying the constraints of driving safety and travel time. To show the HEV powertrain characteristics, a case study is given with the speed planning and energy management strategy.     

道路转向延迟的动态对偶图模型

传统的道路转向延迟对偶图表达法缺乏对交通网络时间依赖特性的考虑,不适合动态路径规划问题的求解。本文将时间因素引入到对偶图中,发展了一种动态对偶图模型,将交通路网表达为动态对偶网络,并为之定义了FIFO(先进先出）条件,推导了满足FIFO条件的动态行程计算方法,设计了时间依赖的标号设定最短路径算法。实验结果表明,利用该对偶图模型和动态对偶网络,能有效表达路网转向延迟,在以出行时间为标准的动态路径规划中,基于动态对偶网络的路径规划结果可节省约16%的出行时间。     

Traveling time prediction in scheduled transportation with journey segments

Urban mobility impacts urban life to a great extent. To enhance urban mobility, much research was invested in traveling time prediction: given an origin and destination, provide a passenger with an accurate estimation of how long a journey lasts. In this work, we investigate a novel combination of methods from Queueing Theory and Machine Learning in the prediction process. We propose a prediction engine that, given a scheduled bus journey (route) and a ‘source/destination’ pair, provides an estimate for the traveling time, while considering both historical data and real-time streams of information that are transmitted by buses. We propose a model that uses natural segmentation of the data according to bus stops and a set of predictors, some use learning while others are learning-free, to compute traveling time. Our empirical evaluation, using bus data that comes from the bus network in the city of Dublin, demonstrates that the snapshot principle, taken from Queueing Theory, works well yet suffers from outliers. To overcome the outliers problem, we use Machine Learning techniques as a regulator that assists in identifying outliers and propose prediction based on historical data.     

Route planning model of multi-agent system for a supply chain management

Sometimes in travel planning, finding the best route to the road transportation network by considering the environmental conditions that are affecting the actual time travel of the travellers are vital especially in handling the logistic operations in supply chain management (SCM). Furthermore, the policy strategy is needed in order to influence the managers or drivers to find the optimum and the most effective route for a trip plan in supporting the logistic operations of SCM. In this paper we analyze the effectiveness of the coordination model of the environmental conditions that are affecting for the travelling time based on multi-agent system for a road transportation network for supply chain management. A number of experimental cases have been used to evaluate the proposed approach transportation network problems in some Malaysian cities. Finally, experimental results affirmed that the proposed approach is practical and efficient.     

隐私保护的网约出行的研究综述

为高效利用交通资源,在线网约出行(ORH)服务整合车辆供给和乘客请求信息,派遣符合条件的车辆提供非巡游的出行服务。人们在享受ORH服务带来的便利时,也面临着严重的隐私泄露风险。为此,许多研究利用密码学技术设计隐私保护的ORH服务。首先,本文介绍了隐私保护的ORH服务主要面临的城市动态场景下高效计算密态行程开销、实时动态规划密态行程、安全共享不同ORH服务的运力资源等挑战。然后,回顾了欧式距离、路网距离和行驶时间三类行程开销的安全计算方法,其中,欧式距离计算效率高,但误差大,现有路网距离和行驶时长的安全计算方法多数面向静态路网场景,针对城市动态路网场景的安全计算方法有待进一步研究。分析了面向司机、乘客、ORH平台的行程规划问题的求解方法,现有研究往往仅针对司机、乘客或ORH平台的单一目标进行行程规划,事实上行程规划不但要考虑ORH平台自身收益,更要同时兼顾乘客和司机的用户体验。综述了隐私感知的行程预处理方法,单车单客模式、单车多客模式的行程安全共享方法,并总结了其不足与启示。多车单客、多车多客动态模式的行程安全共享有待进一步研究。最后,从城市动态路网下高效的密态行程开销的安全计算与比较、...     

Modeling Business Land Use Equilibrium for Small Firms’ Relocation and Consumers’ Trip in a Transportation Network

This paper studies the integrated models for small and medium-sized enterprises’ distribution and consumers’ trip in an urban network based on the simultaneous equilibrium approach. In this paper, each firm aims at finding some business centers to set up shops to maximize his net profit while each consumer is a traveler who chooses his destination (business center) and travel route according to the minimization of individual net social cost, which is equal to the cost of travel time minus the destination attraction measure. The contribution of this paper can be divided into three parts. Firstly, a new deterministic equilibrium model is developed to capture consumers’ travel choice and firms’ location choice. The relocation cost between any two business centers is explicitly considered. Furthermore, the business center passenger/firm flow capacity constraint is incorporated into the previous model. Mathematically, we prove that this extension will derive the endogenous location transfer market in a business center for firms if the maximum firm flow capacity is reached at equilibrium. Finally, we extend the preceding deterministic models to the stochastic case.     

An Efficient Tree-Based Multicasting Algorithm on Wormhole-Routed Star Graph Interconnection Networks Embedded with Hamiltonian Path

Multicasting is an important issue for numerous applications in parallel and distributed computing. In multicasting, the same message is delivered from a source node to an arbitrary number of destination nodes. The star graph interconnection network has been recognized as an attractive alternative to the popular hypercube network. In this paper, we propose an efficient and deadlock-free tree-based multi-cast routing scheme for wormhole-routed star graph networks with hamiltonian path. In our proposed routing scheme, the router is with the input-buffer-based asynchronous replication mechanism that requires extra hardware cost. Meanwhile, the router simultaneously sends incoming flits on more than one outgoing channel. We perform simulation experiments with the network latency and the network traffic. Experimental results show that the proposed scheme reduces multicast latency more efficiently than other schemes.     

An efficient path computation model for hierarchically structured topographical road maps

In this paper, we have developed a HiTi (Hierarchical MulTi) graph model for structuring large topographical road maps to speed up the minimum cost route computation. The HiTi graph model provides a novel approach to abstracting and structuring a topographical road map in a hierarchical fashion. We propose a new shortest path algorithm named SPAH, which utilizes HiTi graph model of a topographical road map for its computation. We give the proof for the optimality of SPAH. Our performance analysis of SPAH on grid graphs showed that it significantly reduces the search space over existing methods. We also present an in-depth experimental analysis of HiTi graph method by comparing it with other similar works on grid graphs. Within the HiTi graph framework, we also propose a parallel shortest path algorithm named ISPAH. Experimental results show that inter query shortest path problem provides more opportunity for scalable parallelism than the intra query shortest path problem.     

Mining coterie patterns from Instagram photo trajectories for recommending popular travel routes

Instagram is a popular photo-sharing social application. It is widely used by tourists to record their journey information such as location, time and interest. Consequently, a huge volume of geo-tagged photos with spatio-temporal information are generated along tourist’s travel trajectories. Such Instagram photo trajectories consist of travel paths, travel density distributions, and traveller behaviors, preferences, and mobility patterns. Mining Instagram photo trajectories is thus very useful for many mobile and location-based social applications, including tour guide and recommender systems. However, we have not found any work that extracts interesting group-like travel trajectories from Instagram photos asynchronously taken by different tourists. Motivated by this, we propose a novel concept: coterie, which reveals representative travel trajectory patterns hidden in Instagram photos taken by users at shared locations and paths. Our work includes the discovery of (1) coteries, (2) closed coteries, and (3) the recommendation of popular travel routes based on closed coteries. For this, we first build a statistically reliable trajectory database from Instagram geo-tagged photos. These trajectories are then clustered by the DBSCAN method to find tourist density. Next, we transform each raw spatio-temporal trajectory into a sequence of clusters. All discriminative closed coteries are further identified by a Cluster-Growth algorithm. Finally, distance-aware and conformityaware recommendation strategies are applied on closed coteries to recommend popular tour routes. Visualized demos and extensive experimental results demonstrate the effectiveness and efficiency of our methods.     

基于服务质量的多媒体组通信目的节点加入与退出算法的研究

路由选择机制是分布多式媒体系统中的重要研究方向。其中,基于服务质量的多媒体通信目的节点加入与退出算法是关键组成部分。该文在基于服务质量的多媒体通信初始路由建立算法的基础上,基于资源共享原则,提出支持成员动态加入与退出多媒体组通信的目的节点加入与退出算法,以增加使用费用最小为目标在满足服务质量约束的条件下完成目的节点加入,在不影响多媒体组通信服务质量的前提下,在完成目的节点退出的同时最大限度地释放已占用资源。文中还探讨了这些算法的有效性。它们和基于服务质量的多媒体通信初始路由建立算法相结合,可以提供对分布式多毁体组应用服务质量保证的支持。     

一种车载自组织网络中交通拥塞自适应的出行计划方案

交通堵塞现象越来越威胁正常的城市交通,针对选择最短路径的出行方案往往不能取得最短的出行时间的现象,提出了一种交通拥塞自适应的出行计划方案.该方案克服了现有方案在规划出行路线时未能考虑行车过程中实际交通状况的缺点,根据车辆在各路段行驶的平均通过时间来判断路段当前的拥塞状况,并动态优化行车路线,从而提高交通效率.仿真实验表明该方案能够自适应路段的交通拥塞,根据当前拥塞状况重新优化行车路线,从而缩短平均行车时间.