A Voronoi neighborhood-based search heuristic for distance/capacity constrained very large vehicle routing problems

Local search heuristics for very large-scale vehicle routing problems (VRPs) have made remarkable advances in recent years. However, few local search heuristics have focused on the use of the spatial neighborhood in Voronoi diagrams to improve local searches. Based on the concept of a k-ring shaped Voronoi neighbor, we propose a Voronoi spatial neighborhood-based search heuristic and algorithm to solve very large-scale VRPs. In this algorithm, k-ring Voronoi neighbors of a customer are limited to building and updating local routings, and rearranging local routings with improper links. This algorithm was evaluated using four sets of benchmark tests for 200–8683 customers. Solutions were compared with specific examples in the literature, such as the one-depot VRP. This algorithm produced better solutions than some of the best-known benchmark VRP solutions and requires less computational time. The algorithm outperformed previous methods used to solve very large-scale, real-world distance constrained capacitated VRP.     

禁忌搜索算法在图像匹配中的应用研究

搜索策略是图像匹配研究的主要问题之一,对匹配算法的执行速度和最终的匹配精度都有很大的影响。该文将禁忌搜索算法的思想用于图像匹配的搜索过程,并进行了改进,构造了永久禁忌和暂时禁忌两种禁忌表,每次搜索都将候选解中的点分别放入不同的禁忌表中,再利用基于灰度的匹配方法,以归一化积相关为相似性度量准则,克服了传统的归一化积相关图像匹配算法耗时过长的缺点,可以在不失匹配精度的条件下,大大减少匹配所用的时间,实现了准确而快速的图像匹配。     

Improving the throughput of transportation networks with a time-optimization routing strategy

Traffic congestion, a common and complicated phenomenon in urban transportation systems, is attracting increasing attention from researchers in Geographical Information Science (GIS) and other fields. In this study, we illustrate a general mechanism that reveals the relationship between travel time and dynamic traffic conditions. We measure a vehicle’s travel time to its destination along any path, where the travel time is calculated based on the path length and on the real-time traffic volume and transport capacity of each road segment on the path. On the basis of this measurement, we present a simple dynamic routing strategy that allows each vehicle to dynamically choose the path to its destination while imposing the minimum travel time. The application of our routing algorithm to the Chengdu street network, Barabási–Albert scale-free network and Erdös–Rényi random network shows that the proposed strategy remarkably improves network throughput and balances traffic load distribution. Our findings suggest that mining the time mechanism of network transport is important to explore efficient time-optimization routing algorithms to enhance the transport capacity of urban street networks and other kinds of networks.     

A shortest path algorithm with novel heuristics for dynamic transportation networks

Finding an optimal route in dynamic real‐time transportation networks is a critical problem for vehicle navigation. Existing approaches are either too complex or incapable of managing complex circumstances where both the location of a mobile object and traffic conditions change over time. In this paper, we propose an incremental search approach with novel heuristics based on a variation of the A* algorithm–Lifelong Planning A*. In addition, we suggest using an ellipse to prune the unnecessary nodes to be scanned in order to speed up the dynamic search process. The proposed algorithm determines the shortest‐cost path between a moving object and its destination by continually adapting to the dynamic traffic conditions, while making use of the previous search results. Experimental results evince that the proposed algorithm performs significantly better than the well‐known A* algorithm.     

A bidirectional path-finding algorithm and data structure for maritime routing

Route planning is an important problem for many real-time applications in open and complex environments. The maritime domain is a relevant example of such environments where dynamic phenomena and navigation constraints generate difficult route finding problems. This paper develops a spatial data structure that supports the search for an optimal route between two locations while minimizing a cost function. Although various search algorithms have been proposed so far (e.g. breadth-first search, bidirectional breadth-first search, Dijkstra’s algorithm, A^*, etc.), this approach provides a bidirectional dynamic routing algorithm which is based on hexagonal meshes and an iterative deepening A^* (IDA^*) algorithm, and a front to front strategy using a dynamic graph that facilitates data accessibility. The whole approach is applied to the context of maritime navigation, taking into account navigation hazards and restricted areas. The algorithm developed searches for optimal routes while minimizing distance and computational time.     

基于GIS技术的物流配送线路优化与仿真模拟

以广州市海珠区连锁超市便利店物流配送为例,根据2012年广州市道路网络数据集,结合VRPTW模型（Vehicle Routing Problem with Time Windows）和ArcGIS网络分析模块进行路面顺畅和交通拥堵情况下的配送与仿真模拟。结果表明,在路面顺畅的情况下,3个配送中心只需用到5辆车,花费时间为29 h 10 min,行驶47 834.1 m,即可完成对26个配送点共4 450件货物的配送。而交通拥堵对物流的准时配送产生了显著的影响,随着拥堵时间的增加,整个物流配送过程受到的影响越来越大。在交通拥堵的情况下,选择避开拥堵路段,重新优化配送路线,路线优化后的整个配送过程所行使的总距离比路面通畅时多走了5 182 m,时间上多花了28 min。然而选择优化路线后所花的时间相对于在道路路段拥挤所花费的时间和在每个拥堵路口的等待时间而言,显然优化后的路线更加可取。通过优化路径可以节省费用,节约资源以及减少流通环节中的时间损耗,获得最佳的行驶路线,能有效提高物流配送服务质量和效率。     

A Balanced Route Design for Min-Max Multiple-Depot Rural Postman Problem (MMMDRPP): a police patrolling case

Providing distributed services on road networks is an essential concern for many applications, such as mail delivery, logistics and police patrolling. Designing effective and balanced routes for these applications is challenging, especially when involving multiple postmen from distinct depots. In this research, we formulate this routing problem as a Min-Max Multiple-Depot Rural Postman Problem (MMMDRPP). To solve this routing problem, we develop an efficient tabu-search-based algorithm and propose three novel lower bounds to evaluate the routes. To demonstrate its practical usefulness, we show how to formulate the route design for police patrolling in London as an MMMDRPP and generate balanced routes using the proposed algorithm. Furthermore, the algorithm is tested on multiple adapted benchmark problems. The results demonstrate the efficiency of the algorithm in generating balanced routes.     

Personalized sightseeing tours: a model for visits in art museums

This article describes a method to provide adapted visit tours in art museums according to the preferences expressed by the visitor and exhibits prestige. It is based on a dual approach with, on the one hand an automatic textual analysis of the official information available online (labels of exhibits) that allows to rank the exhibit attractiveness for a standard museum visitor. On the other hand, individual preferences are also taken into account to adapt the visit according to the personal cultural awareness of the visitor. We use operations research to solve a routing optimization problem, aiming at finding a visit tour with time constraints and maximization of the visitor satisfaction. Depending on the instance size and the problem scale, an integer linear programming (ILP) model and a greedy algorithm are proposed to recommend personalized visit tours and applied on two museums: ‘Musée de l’Orangerie’ in Paris and ‘National Gallery’ in London. The obtained results show that it is possible to recommend a good tour to visitors of an art museum by taking into account the common prestige of the exhibits and the individual interests, joining automatic text summarization and routing optimization in a limited geographical space.     

车辆GPS监控数据的自适应采集算法研究

在大规模GPS车辆监控中,当精度要求高时终端与中心端的通信负荷及中心端的数据处理负荷都很大,自适应采集技术可以有效解决这一问题。该文提出了车辆GPS监控数据的自适应采集算法,采用基于端点速度约束和里程约束的拟合多项式表达速度函数,综合考虑终端有地图和无地图的情况,采用偏差距离表示速度的方向偏差,并提出了数据的恢复算法、算法评价指标以及算法的应用模式。最后基于北京市的真实路网和实测GPS数据对算法进行了验证,恢复后的数据在速度和位置上都逼近真实数据,数据压缩率达3%,证明了算法的有效性。     

A modified particle swarm optimization algorithm for optimal allocation of earthquake emergency shelters

Allocation for earthquake emergency shelters is a complicated geographic optimization problem because it involves multiple sites, strict constraints, and discrete feasible domain. Huge solution space makes the problem computationally intractable. Traditional brute-force methods can obtain exact optimal solutions. However, it is not sophisticated enough to solve the complex optimization problem with reasonable time especially in high-dimensional solution space. Artificial intelligent algorithms hold the promise of improving the effectiveness of location search. This article proposes a modified particle swarm optimization (PSO) algorithm to deal with the allocation problem of earthquake emergency shelter. A new discrete PSO and the feasibility-based rule are incorporated according to the discrete solution space and strict constraints. In addition, for enhancing search capability, simulated annealing (SA) algorithm is employed to escape from local optima. The modified algorithm has been applied to the allocation of earthquake emergency shelters in the Zhuguang Block of Guangzhou City, China. The experiments have shown that the algorithm can identify the number and locations of emergency shelters. The modified PSO algorithm shows a better performance than other hybrid algorithms presented in the article, and is an effective approach for the allocation problem of earthquake emergency shelters.     

基于出租车经验路径的城市可达性计算方法

可达性计算中,始发地-目的地(Origin-Destination, 简称OD)间的路径规划是一个很重要的问题。传统基于最短路径算法的路径规划存在与现实不符的可能,因此考虑出租车载客的经验路径,更符合现实的出行。本文基于潜能模型,综合考虑了人口分布、交通路网特征,兴趣点分布等因素,提出了城市可达性的计算方法,其中OD间行程时间采用出租车经验路径行程时间。然后以广州市中心城区为研究区域,进行网格划分,不同的网格分别作为OD;并采用一个月的广州出租车GPS数据,从中提取大量的载客经验路径,建立出租车经验路径数据库,将OD间的经验路径行程时间计算出来,最后完成了广州中心城区的可达性计算和分析。结果表明,广州中心城区可达性符合典型的势能分布,城市可达性在中心区最高,然后逐步向郊区递减。该结果验证了城市可达性计算方法具有较好的实用性和可计算性。     

面向高分卫星遥感共性产品真实性检验的无人机空港布局

针对高分卫星遥感共性产品真实性检验对无人机数据的需求,本文以已有野外台站为依托,开展无人机空港布局研究。首先,综合考虑影响卫星产品空间变异的因素,构建了地理背景覆盖率的物理模型;其次,基于地理背景覆盖率改进覆盖模型提出最大地理背景覆盖模型,并利用简单随机抽样中的样本容量确定方法确定合理的空港数量,分别利用本文提出的最大地理背景覆盖模型和已有最大面积覆盖模型进行空港布局的研究;最后,对两种模型下的空港布局结果进行对比,并利用MODIS EVI数据产品对布局结果进行验证。结果表明,在空港数有限的条件下（n = 60）,最大面积覆盖模型选择的空港,其服务范围内的地理背景覆盖率为26.66%,能代表70.37%的中国陆地区域,而最大地理背景覆盖模型选择的空港,其服务范围内的地理背景覆盖率为38.32%,能代表73.36%的中国陆地区域。最大地理背景覆盖模型比最大面积覆盖模型能获得更优的空港布局结果,可用于支撑中国区域面向高分卫星遥感共性产品真实性检验的无人机观测网络建设。     

一种基于DEM的河网快速提取算法

目前从DEM中提取河网应用最普遍的是径向水流算法,但DEM中存在平地会形成平行水流,存在洼地会造成平行水流形成断流。该文提出一种快速提取算法:首先在DEM中标注山顶、平地、洼地和盆地,以山顶区域周围的低洼点为起点,按照最陡坡降追踪谷地,当追踪到盆地区域或其他谷地区域则结束;连接谷地和盆地,建立初步的河流网络。然后计算出网络中连接点的汇水量,舍弃汇水量小的节点的上游谷地,得到需要提取的网络。该算法避免了平行水流和断流的产生,其仅追踪从山顶区域(而非所有格网点)发育的水流,汇水量计算中仅计算连接点(而非所有格网点)的汇水量,实现了河网的快速提取。     

基于城市公共交通的长春市医院可达性分析

城市公共交通的可达性体现了公共交通系统的发展水平,该研究为制定城市公共交通规划、优化社会服务设施空间布局等城市发展问题提供了有利的科学支撑。借助ArcGis 软件,采用网络分析法,生成了长春市公共交通网络图;以最短可达时间和公共交通的服务频次作为评价指标,将非高峰和高峰时段作为时态的划分依据,探讨了长春市各居住小区和医院之间的可达性的时空分布特征。结果表明：长春市居住小区的平均可达时间等级整体水平较高,且非高峰时段优于高峰时段;居住小区的平均可达时间等级在空间上分异显著,呈现出不连续的圈层式分布;可达时间等级越高的居住小区,周边的公共交通服务频次等级越高,但两个等级间并不存在完全的一致性,且高峰时段的公交服务频次明显高于非高峰时段;各医院在非高峰时段的时间可达性较好,而在高峰时段有了较为显著的下降,不同等级医院的平均可达时间各不相同,但其差异并不显著。在上述分析的基础上,进而探讨了长春市公共交通存在的问题及原因,并提出了优化建议。     

学校分区问题混合元启发算法研究

中国城市义务教育学校采用单校划片或多校划片的方式确定招生范围,落实就近入学的法律要求。针对多校划片这一新的学校分区问题,提出“先学校分组,再学生分派”的策略进行划片,并设计了学校分组线性规划模型和学校分区混合元启发算法。分区算法包括初始解构造、邻域搜索算子、破坏重建扰动、集合划分问题（SPP）建模与求解等基本模块,在多启动迭代局部搜索（ILS）算法框架中进行问题求解。通过多启动、随机搜索、破坏重建扰动等机制提升算法的多样性,并引入SPP模型提升算法的全局寻优能力。选择一个县级市和一个市辖区分别进行学校划片实验,结果表明：混合元启发算法优化性能优异且收敛性好,适用于求解单校划片和多校划片问题;SPP模型在单校划片问题中具有明显的优势。     

Solving land-use suitability analysis and planning problem by a hybrid meta-heuristic algorithm

The aim of Land-use Suitability Analysis and Planning Problem (LSAPP) is to identify the most suitable parcels of land for future land-uses considering several conflicting criteria. LSAPP can be modeled using a variant of a well-known combinatorial optimization problem called Quadratic Assignment Problem (QAP). In this paper, a multi-objective mathematical model is developed for LSAPP based on QAP modeling. The large-size instances of the proposed multi-objective mathematical model are difficult to solve in a reasonable CPU time using exact algorithms. So, an efficient three-phase hybrid solution procedure is proposed. In the first phase, the compensatory objectives are integrated using Analytic Hierarchy Process (AHP) and Decision-Making Trial and Evaluation Laboratory. Then, based on the aforementioned suitability objective function and other spatial objectives and constraints, a multi-objective LSAPP is constructed. Finally, a hybrid multiple objective meta-heuristic algorithm is proposed to solve the LSAPP. The core of the proposed algorithm is based on Scatter Search while Tabu Search and Variable Neighborhood Search are also utilized. The proposed algorithm is equipped with the concepts of Pareto optimality and Veto Threshold, which improve its efficacy. The proposed algorithm is applied on a real LSAPP case study, in ‘Persian Gulf Knowledge Village’, wherein its performance is compared with a well-known evolutionary computation algorithm called Vector Evaluated Genetic Algorithm (VEGA) using comprehensive statistical analysis. A survey on time complexity of the proposed algorithm is also accomplished. The results show that MOSVNS is significantly superior to VEGA both in single and in multi-objective modes. Furthermore, analysis of time complexity of the proposed algorithm shows that it is of polynomial time and can be applied to significantly larger problems with multiple compensatory and non-compensatory objectives.     

Car navigation – computing routes that avoid complicated crossings

Personalized navigation and way-finding are prominent research areas of location-based service (LBSs). This includes innovative concepts for car navigation. Within this paper, we investigate the idea of providing drivers a routing suggestion which avoids ‘complicated crossings’ in urban areas. Inexperienced drivers include persons who have a driver’s license but, for whatever reason, feel uncomfortable to drive in a city environment. Situations where the inexperienced driver has to depend on a navigation device and reach a destination in an unfamiliar territory may be difficult. Preferences of inexperienced drivers are investigated. ‘Fears’ include driving into ‘complicated crossings’. Therefore, the definition and spatial characteristics of ‘complicated crossings’ are investigated. We use OpenStreetMap as a road dataset for the routing network. Based on the topological characteristics of the dataset, measured by the number of nodes, we identify crossings that are ‘complicated’. The user can choose to compute an alternative route that avoids these complicated crossings. This methodology is one step in building a full ‘inexperienced drivers’ routing system, which includes additional preferences from the user group, for example, as avoiding left turns where no traffic light is present.     

Measuring inter-city connectivity in an urban agglomeration based on multi-source data

A comprehensive understanding of inter-city connectivity is important for regional planning. However, most studies adopted only one single data source for measurements, which is incomplete since each source has its own limitations. There are biases and uncertainties in the connectivity results when using different data sources. To address this problem, our study proposed a novel method that could combine the advantages of multi-source data. First, we measured inter-city connectivities using several datasets individually, and then analyzed each city’s node strength based on the connectivities. Next, the performance of each dataset was validated according to several correlation analyses between the node strength and various socio-economic metrics. Based on these validations, we used the genetic algorithm to search for the optimal weights for combination. Only those datasets with higher weights were retained for further calculation. The final connectivity result is more reasonable than any single result according to the validation. For the first time, this study compares different data sources related to inter-city connectivity, and combines their advantages based on selective weighted combination. The results are expected to provide strong support for large-scale regional planning. In addition, the proposed method could be further applied to other large areas for analyzing inter-city connectivities.     

Optimal routing for waste collection: a case study in Singapore

ABSTRACT

To collect and dispose growing amounts of municipal solid waste (MSW) changed to be a hot topic along with the rapid urbanization in past decades. Cities are more and more dependent on the incineration instead of landfilling due to the cost-efficiency and environmental concerns. Considering the limited number of incineration plants and complicated situation of transportation in both spatial and temporal dimensions in different cities, the optimal routing for waste collection turns to be meaningful research topic. In this research, the ant colony optimization (ACO)-based multi-objective routing model coupled with min-max model and Dijkstra’s algorithm is proposed to address the question of which route to take from these waste-generating points to the target incineration plant(s) considering travel time, accident probability (black spots), and population exposure, so as to support the routing decision-making. The model is successfully implemented in Singapore and the effectiveness of the model has also been justified. Besides, few limitations of this research have also been discussed, some of which would also be the future directions of our research, especially the design and integration of a web-based routing decision-making support system.     

Robust inferences of travel paths from GPS trajectories

Monitoring and predicting traffic conditions are of utmost importance in reacting to emergency events in time and for computing the real-time shortest travel-time path. Mobile sensors, such as GPS devices and smartphones, are useful for monitoring urban traffic due to their large coverage area and ease of deployment. Many researchers have employed such sensed data to model and predict traffic conditions. To do so, we first have to address the problem of associating GPS trajectories with the road network in a robust manner. Existing methods rely on point-by-point matching to map individual GPS points to a road segment. However, GPS data is imprecise due to noise in GPS signals. GPS coordinates can have errors of several meters and, therefore, direct mapping of individual points is error prone. Acknowledging that every GPS point is potentially noisy, we propose a radically different approach to overcome inaccuracy in GPS data. Instead of focusing on a point-by-point approach, our proposed method considers the set of relevant GPS points in a trajectory that can be mapped together to a road segment. This clustering approach gives us a macroscopic view of the GPS trajectories even under very noisy conditions. Our method clusters points based on the direction of movement as a spatial-linear cluster, ranks the possible route segments in the graph for each group, and searches for the best combination of segments as the overall path for the given set of GPS points. Through extensive experiments on both synthetic and real datasets, we demonstrate that, even with highly noisy GPS measurements, our proposed algorithm outperforms state-of-the-art methods in terms of both accuracy and computational cost.