面向智能网联车辆碰撞风险规避的互动速度障碍算法

针对多智能车辆协同驾驶中的动态避碰问题,构建了一种面向智能网联车辆碰撞风险检测与协同避碰路径规划的互动速度障碍算法;基于人工势场理论构建了车辆碰撞风险势场,量化了车辆碰撞风险强度与碰撞风险区域;基于车辆驾驶行为交互作用构建了互动速度障碍算法,确定了冲突车辆碰撞风险的协同规避条件与规则;基于车辆动力学约束构建了动态窗口法,确定了碰撞风险规避可行速度解集;基于模型预测控制原理,应用最优化理论构建了车辆碰撞风险规避路径规划模型;通过构建智能网联环境下单冲突车辆、多冲突车辆、瓶颈区冲突车流避碰仿真场景,测试了提出的碰撞风险规避算法的有效性,并与其他避碰算法进行了控制效果对比。研究结果表明：相较于其他对比算法,互动速度障碍算法控制下的安全性能提升了8.6%以上,效率性能提升了9.6%以上,说明提出的互动速度障碍算法通过协同冲突车辆的避碰行为可有效降低冲突车辆避碰速度与轨迹波动,可有效规避非线性速度与轨迹冲突车辆间的碰撞冲突,并可避免瓶颈区多车辆碰撞事故与明显车流波动;在瓶颈区大范围车辆冲突中,相较于其他避碰算法,提出的避碰算法可使车辆的通行效率提升10.42%,使车辆的碰撞风险降低47.32%。由此可见,该算法在协同大规模冲突车辆的避碰行为、降低车辆碰撞风险与运行延误上具有良好性能。     

拉格朗日松弛启发式算法求解时空网络下的弧路径问题

为减少车辆调度成本,优化车辆运输路径,在时空网络中研究路段作业车辆的弧路径问题;考虑道路出行的时变性,利用车辆运行的时间、空间特征,构建时间-空间网络,建立弧路径问题的时空网络流模型;设计了拉格朗日松弛启发式算法,引入拉格朗日乘子松弛耦合约束,构建拉格朗日松弛问题;进一步通过拉格朗日分解,把松弛问题分解为单车最短路问题;用次梯度算法更新乘子,求解拉格朗日对偶问题,并更新原问题最优解的下界;使用启发式算法获得可行解,并更新原问题最优解的上界;用六结点运输网络和Sioux-Falls网络下的算例对算法进行实证分析。计算结果表明：六结点运输网络中6个算例的上下界间隙值等于0或接近0,Sioux-Falls网络中算例2的间隙值为0.02%,其余5个算例的间隙值等于0,均可以得到质量较高的近似最优解;在最复杂的算例(15辆车,70个任务)中,算法在可接受的时间内也得到了间隙值为0的解,找出了最优的车辆路径;随着迭代次数的增加,拉格朗日乘子会逐步收敛到固定值;当车辆容量从50增加到100时,最优解从52下降到42,说明在任务数和车辆数一定时,适当增加车容量可以降低运营成本。可见,与商业求解器相比,拉格朗日松弛启发式算法的间隙值更小,求解质量更高,可以更有效地求解弧路径问题。     

考虑均衡性的城市轨道交通线路负荷水平评估研究

线路负荷水平的评价工作是优化运输组织方案的重要前提。首先,本文分析了采用单一均值性指标表征负荷水平不能体现线路内负荷分布偏差的问题。为此,从城市轨道交通线路客流与运输能力匹配的角度出发,以列车负荷为评价单元,建立包括负荷均值和标准差率二维指标的线路负荷水平评估模型。负荷均值指标考虑了各评价单元加权计算,以反映每个评价单元对线路负荷水平的贡献程度,标准差率指标表征负荷均衡性。模型分析得出,线路所有区间的运力同等规模变化不影响标准差率指标,相对提高大客流区间或大客流方向上的输送能力能够改善线路负荷的均衡性。算例分析表明：客流方向不均衡系数超过 1.4 时,应考虑运力优化措施以提高运输能力利用的均衡;组织列车大小交路方案和不成对行车模式,能够提高线路负荷的均衡程度。     

Order-first split-second methods for vehicle routing problems: A review

Cluster-first route-second methods like the sweep heuristic (Gillett and Miller, 1974) are well known in vehicle routing. They determine clusters of customers compatible with vehicle capacity and solve a traveling salesman problem for each cluster. The opposite approach, called route-first cluster-second, builds a giant tour covering all customers and splits it into feasible trips. Cited as a curiosity for a long time but lacking numerical evaluation, this technique has nevertheless led to successful metaheuristics for various vehicle routing problems in the last decade. As many implementations consider an ordering of customers instead of building a giant tour, we propose in this paper the more general name of ordering-first split-second methods. This article shows how this approach can be declined for different vehicle routing problems and reviews the associated literature, with more than 70 references.     

Multi-objective optimization of train routing problem combined with train scheduling on a high-speed railway network

Based on train scheduling, this paper puts forward a multi-objective optimization model for train routing on high-speed railway network, which can offer an important reference for train plan to provide a better service. The model does not only consider the average travel time of trains, but also take the energy consumption and the user satisfaction into account. Based on this model, an improved GA is designed to solve the train routing problem. The simulation results demonstrate that the accurate algorithm is suitable for a small-scale network, while the improved genetic algorithm based on train control (GATC) applies to a large-scale network. Finally, a sensitivity analysis of the parameters is performed to obtain the ideal parameters; a perturbation analysis shows that the proposed method can quickly handle the train disturbance.     

Ant Colony Routing algorithm for freeway networks

Dynamic traffic routing refers to the process of (re)directing vehicles at junctions in a traffic network according to the evolving traffic conditions. The traffic management center can determine desired routes for drivers in order to optimize the performance of the traffic network by dynamic traffic routing. However, a traffic network may have thousands of links and nodes, resulting in a large-scale and computationally complex non-linear, non-convex optimization problem. To solve this problem, Ant Colony Optimization (ACO) is chosen as the optimization method in this paper because of its powerful optimization heuristic for combinatorial optimization problems. ACO is implemented online to determine the control signal – i.e., the splitting rates at each node. However, using standard ACO for traffic routing is characterized by four main disadvantages: 1. traffic flows for different origins and destinations cannot be distinguished; 2. all ants may converge to one route, causing congestion; 3. constraints cannot be taken into account; and 4. neither can dynamic link costs. These problems are addressed by adopting a novel ACO algorithm with stench pheromone and with colored ants, called Ant Colony Routing (ACR). Using the stench pheromone, the ACR algorithm can distribute the vehicles over the traffic network with less or no traffic congestion, as well as reduce the number of vehicles near some sensitive zones, such as hospitals and schools. With colored ants, the traffic flows for multiple origins and destinations can be represented. The proposed approach is also implemented in a simulation-based case study in the Walcheren area, the Netherlands, illustrating the effectiveness of the approach.     

Stability of transportation networks under adaptive routing policies

Growing concerns regarding urban congestion, and the recent explosion of mobile devices able to provide real-time information to traffic users have motivated increasing reliance on real-time route guidance for the online management of traffic networks. However, while the theory of traffic equilibria is very well-known, fewer results exist on the stability of such equilibria, especially in the context of adaptive routing policy. In this work, we consider the problem of characterizing the stability properties of traffic equilibria in the context of online adaptive route choice induced by GPS-based decision making. We first extend the recent framework of “Markovian Traffic Equilibria” (MTE), in which users update their route choice at each intersection of the road network based on traffic conditions, to the case of non-equilibrium conditions, while preserving consistency with known existence and uniqueness results on MTE. We then exhibit sufficient conditions on the network topology and the latency functions for those MTEs to be stable in the sense of Lyapunov for a single destination problem. For various more restricted classes of network topologies motivated by the observed properties of travel patterns in the Singapore network, under certain assumptions we prove local exponential stability of the MTE, and derive analytical results on the sensitivity of the characteristic time of convergence to network and traffic parameters. The results proposed in this work are illustrated and validated on synthetic toy problems as well as on the Singapore road network with real demand and traffic data.     

Extending Time to Collision for probabilistic reasoning in general traffic scenarios

Vehicle-to-vehicle communication systems allow vehicles to share state information with one another to improve safety and efficiency of transportation networks. One of the key applications of such a system is in the prediction and avoidance of collisions between vehicles. If a method to do this is to succeed it must be robust to measurement uncertainty and to loss of communication links. The method should also be general enough that it does not rely on constraints on vehicle motion for the accuracy of its predictions. It should work for all interactions between vehicles and not just a select subset. This paper presents a method to calculate Time to Collision for unconstrained vehicle motion. This metric is gated using a novel technique based on relative vehicle motion that we call “looming”. Finally, these ideas are integrated into a probabilistic framework that accounts for uncertainty in vehicle state and loss of vehicle-to-vehicle communication. Together this work represents a new way of considering vehicle collision estimation. These algorithms are validated on data collected from real world vehicle trials.     

Generalized Maximum Benefit Multiple Chinese Postman Problem

This research is focused on a generalization on the Max Benefit Chinese Postman Problem and the multiple vehicle variant of the Chinese Postman Problem. We call this generalization, the Generalized Maximum Benefit k-Chinese Postman Problem (GB k-CPP). We present a novel Mixed Integer Programming (MIP) formulation for the GB k-CPP. Four different cases of the model are discussed. The first case, performs arc-routing with profits and assumes that the origin and destination for each vehicle is the same for each cycle and is given by the user. The next case relaxes the assumption that the origin and destination for each vehicle should be the same and allows the users to select possible origins/destinations for vehicles. Case three gets the origin for each vehicle as input and produces a solution based on finding the best destination for each vehicle. The last case, that is very general, allows the optimization model to select possibly different locations for vehicle origin and destination, during each cycle. The different cases are applied to a security patrolling case conducted on the network of University of Maryland at College Park campus and the results are compared.     

Robust weekly aircraft maintenance routing problem and the extension to the tail assignment problem

In this paper, we study two closely related airline planning problems: the robust weekly aircraft maintenance routing problem (RWAMRP) and the tail assignment problem (TAP). In real life operations, the RWAMRP solution is used in tactical planning whereas the TAP solution is implemented in operational planning. The main objective of these two problems is to minimize the total expected propagated delay (EPD) of the aircraft routes. To formulate the RWAMRP, we propose a novel weekly line-of-flights (LOF) network model that can handle complex and nonlinear cost functions of EPD. Because the number of LOFs grows exponentially with the number of flights to be scheduled, we propose a two-stage column generation approach to efficiently solve large-scale real-life RWAMRPs. Because the EPD of an LOF is highly nonlinear and can be very time-consuming to accurately compute, we propose three lower bounds on the EPD to solve the pricing subproblem of the column generation. Our approach is tested on eight real-life test instances. The computational results show that the proposed approach provides very tight LP relaxation (within 0.6% of optimal solutions) and solves the test case with more than 6000 flights per week in less than three hours. We also investigate the solutions obtained by our approach over 500 simulated realizations. The simulation results demonstrate that, in all eight test instances, our solutions result in less EPDs than those obtained from traditional methods. We then extend our model and solution approach to solve realistically simulated TAP instances.