随机交通网络中依赖信息的路径优化问题研究

针对交通网络中路径通行时间具有与时间相关的随机分布特性，将研究在此类交通网络上依赖信息的路径选择问题。在路径选择过程中引入交通信息，在随机交通网络上最优路径选择原则为下一节点的选择将依赖于已实现的路段时间及当前节点的出发时间，通过期望最小值方法，按照路径通行时间期望值最小原则，建立一种通过所获得交通信息来进行路径选择的优化模型，给出了模型的求解算法。并在简单交通网络上对模型进行实现。     

具有变需求的多模式随机动态同时的路径和出发时间问题研究

为了解决在多种交通模式条件下出行者的路径与出发时间选择问题,提出了一个变分不等式模型用于模拟具有变需求的多模式随机动态出行选择行为。推荐了一个改变的投影压缩算法求解相应的变分不等式问题,并给出了算法的迭代步骤。最后在一个相对真实的路网上进行了仿真试验,从两个OD对之间的一个路径上的路径入口流量率以及增补的路径旅行费用状况中可以看出,小汽车和卡车的路径入口流量率以及增补的路径旅行费用都可以达到一种平衡状态,表明了模型和算法的有效性和正确性。     

Carpooling problem: A new mathematical model,branch-and-bound,and heuristic beam search algorithm

Carpooling is an environmentally friendly transportation system. It can efficaciously help resolve a variety of societal concerns of the urban areas, ranging from traffic congestion to environmental pollution. In this paper, we propose a new mathematical model to solve the carpooling problem. The model simultaneously minimizes the costs of travel times, the vehicle use, and the vehicle delays. An exact solution method based on Branch-and-Bound (B&B) algorithm is proposed to efficiently obtain the optimal solution of the problem. In order to find the near-optimal solutions for large-scale problems, a heuristic beam search algorithm is introduced, which is based on the partial relaxation of some fathoming criteria applied in our proposed B&B. The computational experiments are conducted, based upon the transportation network of Isfahan city, Iran. The results demonstrate the great capability of the proposed exact solution method in terms of both computational solving time required and the number of the evaluated nodes, in comparison with CPLEX software package. The findings of this research can be applied to solve the carpooling problem compatible to the real-life situations.     

考虑驾驶策略的高速列车运行图节能优化方法

为了降低高速列车从始发站至终到站运行的牵引能耗, 研究了针对多列车区间运行时分同步分配的列车运行图节能优化方法。基于高速列车在站间采用的“四阶段”操纵策略构建最优驾驶策略集, 以牵引距离和巡航距离为变化因子, 以牵引能耗和区间运行时分为计算目标, 求解出最优驾驶策略集里牵引能耗与区间运行时分的线性关系。在此基础上构建多列车区间运行时分最优分配的节能运行图模型。模型以牵引能耗最低为目标, 考虑了列车总运行时间约束、变量取值范围约束以及安全间隔时分约束。在模型求解方面, 选取拉格朗日松弛算法, 将复杂约束松弛至目标函数当中, 从而把原问题分解为各区间可独立求解的子问题, 利用次梯度优化的方法得出精确解, 实现了多列车区间运行时分同步分配的目标。以宝兰高速铁路为背景进行算例验证, 结果表明: 通过重新分配区间运行时分, 10列车总共节约了595.958 kW·h牵引能耗, 平均节能率达到了1.2%;从运行图的层面分析, 该算例下通过调整区间运行时分的节能方法对其影响幅度较小, 具有较强的现实意义; 所提出的模型及算法的计算时间为10 s, 针对列车开行对数较多的高速铁路, 可有效提高求解效率。      

Robust traffic assignment model: Formulation,solution algorithms and empirical application

ABSTRACT

The deterministic traffic assignment problem based on Wardrop's first criterion of traffic network utilization has been widely studied in the literature. However, the assumption of deterministic travel times in these models is restrictive, given the large degree of uncertainty prevalent in urban transportation networks. In this context, this paper proposes a robust traffic assignment model that generalizes Wardrop's principle of traffic network equilibrium to networks with stochastic and correlated link travel times and incorporates the aversion of commuters to unreliable routes.

The user response to travel time uncertainty is modeled using the robust cost (RC) measure (defined as a weighted combination of the mean and standard deviation of path travel time) and the corresponding robust user equilibrium (UE) conditions are defined. The robust traffic assignment problem (RTAP) is subsequently formulated as a Variational Inequality problem. To solve the RTAP, a Gradient Projection algorithm is proposed, which involves solving a series of minimum RC path sub-problems that are theoretically and practically harder than deterministic shortest path problems. In addition, an origin-based heuristic is proposed to enhance computational performance on large networks. Numerical experiments examine the computational performance and convergence characteristics of the exact algorithm and establish the accuracy and efficiency of the origin-based heuristic on various real-world networks. Finally, the proposed RTA model is applied to the Chennai road network using empirical data, and its benefits as a normative benchmark are quantified through comparisons against the standard UE and System Optimum (SO) models.     

混合交通网络设计的遗传免疫算法研究

为了研究混合交通网络设计的启发式求解算法,以路段建设费用和网络费用最小化为目标,建立了混合交通网络设计的双层规划模型。鉴于标准遗传算法的局限性,基于人工免疫思想,将免疫系统仿生机理中的免疫调节、克隆选择、免疫记忆引入到遗传算法中,给出了求解混合交通网络设计的遗传免疫算法。通过算例验证了算法的有效性,并和标准遗传算法进行了比较。结果表明,在混合交通网络的设计中遗传免疫算法比标准遗传算法具有更好的求解效果。     

一类随机库存/运输联合优化问题求解过程分析

研究了由一个仓库和n个客户(如零售商、批发商等,而非产品最终的消费者)组成的物流配送系统,中央仓库的库存如何经济合理地分配给每个客户,使这个系统整体的性能最优的随机库存/运输联合优化问题。这个分配过程需要同时考虑每个客户的货物量以及最佳的配送路线,库存/运输联合优化问题比单纯的库存问题或单纯的运输问题要复杂得多。研究在随机条件下如何基于FPP思想来求解ITIO问题更具有实用价值。描述了所研究问题的特点,讨论了对随机需求量的近似确定化处理过程,建立了刻画问题特征的数学模型。同时重点论述如何将研究的问题转化为CCLP问题及相应的求解过程,并给出具体的算法步骤。     

考虑多目标的城市停车换乘选址优化模型及算法

停车换乘选址问题是城市交通网络设计研究的重点领域,已有研究的优化目标多集中在系统总费用方面,而对交通可持续发展方面考虑不足。为此,提出综合考虑多方面目标的停车换乘设施选址优化模型及其求解算法。首先,基于超网络理论,提出多方式城市交通系统的超网络模型并定义O-D (Origin-destination)间的超路径、有效超路径及子路径,结合出行者出行过程及交通网络拥挤特征,给出超路径费用的数学表达;其次,基于多方式交通网络随机均衡配流结果,构建交通总阻抗、污染物排放量以及交通系统公平性等系统优化指标的计算模型,并建立用以描述停车换乘设施选址问题的多目标优化模型;进而,以多目标系统优化模型为上层问题,以超网络下满足Logit分配的多方式交通网络配流模型为下层问题,构建描述城市多方式交通系统停车换乘设施选址问题的双层规划模型,并基于模型特征,结合“记录-搜索”思想设计非支配排序遗传算法进行求解;最后,基于Sioux Falls网络设计算例。研究结果表明：算法能够在有限的步骤内搜索到90%以上的Pareto最优解;平均而言,停车换乘措施使得交通总阻抗减小了0.31%,污染物排放量减少了7.32%...     

公交区域调度的最大同步换乘模型

研究了用多目标优化模型来解决基于最大同步换乘的公交区域调度优化问题,并将该调度优化模型描述为混合整数规划问题。建立了以车辆相遇总次数最大为第1目标,以多辆车同时相遇的机会最大为第2目标的双目标优化模型。采用启发式算法对模型进行求解,得出具有最大同步性的发车时刻表。结果表明:该模型实现了同时到达网络中换乘点的公交车的数量最大,从而使乘客可以在最短的等待时间内在换乘点从一条线路转到另一条线路上。     

用单亲遗传算法求解配送车辆调度问题的研究

建立了配送车辆调度问题的数学模型，针对传统遗传算法对复杂问题搜索效率低，易陷入“早熟收敛”的缺点，构建了求解配送车辆调度问题的单亲遗传算法，并进行了实验计算。计算结果表明，用单亲遗传算法求解配送车辆调度问题，可以取得比传统遗传算法更优的结果。     

Robust <Emphasis Type="Italic">H</Emphasis><Subscript>∞</Subscript> preview control of an active suspension system with norm-bounded uncertainties

A robust H _∞ preview control is investigated for an active suspension system with look-ahead sensors. The uncertain system is described by a state-space model with linear nominal parts and additional nonlinear time-varying norm-bounded uncertainties. Proof of robust stability and a feedback-type robust H _∞ preview controller are derived by augmenting the dynamics of the original system and previewed road input. As, however, the augmented previewed road input gives the system a much larger dimension than the original system, much more computation time is required for solving of Riccati equations. To resolve this problem, a decomposed robust H _∞ preview controller is proposed. Robust stability and performance variations for system uncertainties are shown using a numerical example of a quarter-car model.     

Asynchronous n-step Q-learning adaptive traffic signal control

Ensuring transportation systems are efficient is a priority for modern society. Intersection traffic signal control can be modeled as a sequential decision-making problem. To learn how to make the best decisions, we apply reinforcement learning techniques with function approximation to train an adaptive traffic signal controller. We use the asynchronous n-step Q-learning algorithm with a two hidden layer artificial neural network as our reinforcement learning agent. A dynamic, stochastic rush hour simulation is developed to test the agent’s performance. Compared against traditional loop detector actuated and linear Q-learning traffic signal control methods, our reinforcement learning model develops a superior control policy, reducing mean total delay by up 40% without compromising throughput. However, we find our proposed model slightly increases delay for left turning vehicles compared to the actuated controller, as a consequence of the reward function, highlighting the need for an appropriate reward function which truly develops the desired policy.     

Optimal synchronization and coordination of actual passenger-rail timetables

This study provides a novel solution for the synchronized and coordinated railway scheduling optimization (SCSO) problem by the determination of the departure times of a public transit network. Railway timetable optimization is dealt with maximizing the number of synchronized meetings to allow for smooth transfers at interchanges. The developed model uses binary variables to record the number of synchronized meetings considering the importance of transfer stations and rail lines without the need to apply the modeling of passenger assignments. The model allows for a permissible and flexible transfer waiting time for making a connection between rails instead of the commonly used and assumed values. The solution of the mixed-integer programing problem of larger-sized railway networks is based on a synchronized and coordinated scheduling optimization genetic algorithm (SCSO-GA) with a local search strategy (LSS). This solution method is proved to be more efficient and accurate than the CPLEX solver. In addition it is proven to be a periodic event-scheduling problem (PESP) solver. The model is tested computationally on the Beijing urban rail transit network. The results demonstrate the advantage of the novel approach over other methods.     

A linear complementarity method for the solution of vertical vehicle–track interaction

A new method is proposed for the solution of the vertical vehicle–track interaction including a separation between wheel and rail. The vehicle is modelled as a multi-body system using rigid bodies, and the track is treated as a three-layer beam model in which the rail is considered as an Euler-Bernoulli beam and both the sleepers and the ballast are represented by lumped masses. A linear complementarity formulation is directly established using a combination of the wheel–rail normal contact condition and the generalised-α method. This linear complementarity problem is solved using the Lemke algorithm, and the wheel–rail contact force can be obtained. Then the dynamic responses of the vehicle and the track are solved without iteration based on the generalised-α method. The same equations of motion for the vehicle and track are adopted at the different wheel–rail contact situations. This method can remove some restrictions, that is, time-dependent mass, damping and stiffness matrices of the coupled system, multiple equations of motion for the different contact situations and the effect of the contact stiffness. Numerical results demonstrate that the proposed method is effective for simulating the vehicle–track interaction including a separation between wheel and rail.     

基于免疫克隆算法的多枢纽选址与混合网络设计综合优化研究

为了描述多枢纽选址与混合网络设计综合优化问题,引入了双层规划模型建立数学模型.上层模型为多目标规划模型,以最小化网络总阻抗和最小化总投资为目标;下层模型为固定需求的用户平衡配流模型.然后,给出了基于免疫克隆算法的具体求解设计和步骤.接着,给出了算例,在不同决策权重条件下进行求解.算例结果验证了算法的可行性和模型的有效性,同时结果表明在建设枢纽后,当决策偏重于交通网络管理部门时,更倾向于建设新路段以降低网络费用和总费用.     

基于网络均衡的运输通道客流分配模型

根据各运输方式的经济技术特征,构建了运输通道的时空运营网络来描述各运输方式的竞争性。认为旅客的时间价值(VOT)服从某种分布,旅客的广义出行费用取决于票价和时间两个参数。运用城市交通分配网络均衡思想,提出基于网络的区域运输通道多交通模式客流分配模型,建立了用户最优和系统最优两个目标函数,并给出了模型的求解方法。用一数值示例验证了模型的有效性。     

A Variable Time-Discretization Strategies-Based,Time-Dependent Shortest Path Algorithm for Dynamic Traffic Assignment

Within the simulation-based dynamic traffic assignment (SBDTA) model, the time-dependent shortest path (TDSP) algorithm plays a crucial role in the path-set update procedure by solving for the current optimal auxiliary solution (shortest path). Common types of TDSP algorithms require temporal discretization of link/node time/cost data, and the discretization could affect the solution quality of TDSP and of the overall SBDTA as well. This article introduces two variable time-discretization strategies applicable to TDSP algorithms. The strategies are aimed at determining the optimal time discretization for time-dependent links/nodes travel time data. The first proposed strategy produces a specific discretization interval for each link. The second proposed strategy generates time-varying intervals for the same link over the analysis period. The proposed strategies are implemented in a link-based time-dependent A* algorithm in a SBDTA model DynusT and tested with two numerical experiments on two traffic networks. The results show that the proposed discretization methods achieve the research goal—to flexibly and scalably balance the memory usage and run time for SBDTA without degrading the convergence. This property is rather important when dealing with a large real-world network with a long analysis period.     

基于动态系统的交通分布优化预测方法

研究运输系统中动态交通分布的预测方法,即在运输系统中,当各交通小区的发生交通量及吸引交通量出现变化后,需根据当前交通OD分布表迅速确定下一阶段的交通OD分布表。确定OD分布是交通运输规划与管理的一项重要研究内容,目前已有的预测方法都需经反复多次迭代才能得到计算结果,计算速度不能满足动态交通系统的要求。论文通过建立预测动态交通分布的优化数学模型及严格的数学推导,得到了求最优交通分布的一个解析公式,应用闭回路法设计了满足非负约束并使误差增长最小的一种调整方法。由算例表明该模型计算速度快,计算效果好,适合动态系统的交通分布预测。     

面向交通枢纽的车辆三维真实感实时仿真

为分析和解决城市交通拥挤问题并提高城市道路利用率提供可行的途径,提出了一种面向交通枢纽的车辆运行仿真方法,通过场景、道路与车辆的三维动态建模,实现交通枢纽交通状况的实时真实感仿真.首先,提出了基于道路关键点连接网络模型表示交通枢纽的通行道路.其次,基于粒子系统实现车辆的动态运行实时仿真,并采用基于空间剖分的车辆碰撞检测方法对车辆运动控制算法进行了优化.最终,通过对路段的动态观测和反馈机制实现车辆行驶路线的规划和调度.实验结果表明,本文提出的方法可以生动直观地呈现实际路面的交通状况,并且能以较为流畅的帧速率实现交通场景的动态仿真.     

基于海铁联运的集装箱班列服务路径优化

虑考虑海铁联运过程中影响集装箱班列开行的不确定因素, 结合班列服务客户各自固定需求时间窗的实际需求, 引入不确定规划区间来表示集装箱在客户节点的装卸箱服务时间, 同时将具有时效性要求的需求时间窗设置为软约束, 运用惩罚函数将其作为惩罚项整合到运输成本目标函数中, 选择合理的惩罚系数, 构建以运输成本低、运输时间少为目标的班列服务路径非线性多目标优化模型, 针对不确定变量, 采用机会约束规划转换模型得到考虑模糊时间的多目标路径优化模型, 通过加权求和将多目标合并转化为单目标问题, 并设计人工蜂群算法求解所构建的班列服务路径优化模型, 并以盐田港海铁联运为实例进行了模型检验和对比分析。结果表明: (1)在硬时间窗约束下运输时间减少了88%, 但成本增加了97%, 充分表明了软时间窗设置的优势; (2)考虑不同的运输目标时, 只考虑运输费用时, 运输时间增加了5.3%;只考虑运输时间时, 运输费用增加了67.8%。所建模型和算法能够很好的满足不同客户不同运输时效性的需求, 在运输费用方面具有明显的优越性。