基于网络等级特征与VMS的交叉巢式Logit模型

基于等级特征与可变信息板(VMS)研究了交叉巢式Logit(CNL)模型及网络交通流分配。综合幂函数与指数函数表示方法给出新的信息效用衰减因子,结合道路等级特征表示VMS对车流的影响系数及CNL模型的分配系数;给出等级结构道路网络的随机用户均衡条件下的交叉巢式Logit路径选择模型及其等价数学规划,并设计网络流分配算法。通过实例网络的计算与分析,得到一些有意义的结论:等级结构越显著的路网总出行时间费用越低且其分散参数(θ)弹性绝对值越大;对具有较强随机性的实际路网,若增加一定的确定性则节省更多网络总出行时间;道路网络中设置了VMS时总出行时间受分散参数的影响更小。     

Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem

In urban areas, logistic transportation operations often run into problems because travel speeds change, depending on the current traffic situation. If not accounted for, time-dependent and stochastic travel speeds frequently lead to missed time windows and thus poorer service. Especially in the case of passenger transportation, it often leads to excessive passenger ride times as well. Therefore, time-dependent and stochastic influences on travel speeds are relevant for finding feasible and reliable solutions. This study considers the effect of exploiting statistical information available about historical accidents, using stochastic solution approaches for the dynamic dial-a-ride problem (dynamic DARP). The authors propose two pairs of metaheuristic solution approaches, each consisting of a deterministic method (average time-dependent travel speeds for planning) and its corresponding stochastic version (exploiting stochastic information while planning). The results, using test instances with up to 762 requests based on a real-world road network, show that in certain conditions, exploiting stochastic information about travel speeds leads to significant improvements over deterministic approaches.     

Reserve capacity of signal-controlled road network

For a signal control road network subject to equilibrium flows, the maximum possible increase in travel demands is considered in this paper. Using the concept of reserve capacity of signal-controlled junctions, the problem of finding the maximum increase in traffic demands can be formulated as a mathematical program with equilibrium constraints (MPEC). In this paper, we present a projected gradient approach to obtain the maximum increase in travel demands based on the TRANSYT traffic model. Numerical computations are made on a grid network where good results are obtained.     

Modelling Intra-City Time-Dependent Travel Speeds for Vehicle Scheduling Problems

Many research papers have presented mathematical models for vehicle scheduling. Several of these models have been embedded in commercial decision support systems for intra-city vehicle scheduling for launderies, grocery stores, banks, express mail customers, etc. Virtually all of these models ignore the important issue of time-dependent travel speeds for intra-city travel. Travel speeds (and times) in nearly all metropolitan areas change drastically during the day because of congestion in certain parts of the city road network. The assumption of constant (time-independent) travel speeds seriously affects the usefulness of these models. This is particularly true when time windows (earliest and latest stop time constraints) and other scheduling issues are important. This research proposes a parsimonious model for time-dependent travel speeds and several approaches for estimating the parameters for this model. An example is presented to illustrate the proposed modelling approach. The issue of developing algorithms to find near-optimal vehicle schedules with time-dependent travel speeds is also discussed. The modelling approach presented in this paper has been implemented in a commercial courier vehicle scheduling system and was judged to be ‘very useful’ by users in a number of different metropolitan areas in the United States.     

Vehicle routing problems with alternative paths: An application to on-demand transportation

The class of vehicle routing problems involves the optimization of freight or passenger transportation activities. These problems are generally treated via the representation of the road network as a weighted complete graph. Each arc of the graph represents the shortest route for a possible origin–destination connection. Several attributes can be defined for one arc (travel time, travel cost, etc.), but the shortest route modeled by this arc is computed according to a single criterion, generally travel time. Consequently, some alternative routes proposing a different compromise between the attributes of the arcs are discarded from the solution space. We propose to consider these alternative routes and to evaluate their impact on solution algorithms and solution values through a multigraph representation of the road network. We point out the difficulties brought by this representation for general vehicle routing problems, which drives us to introduce the so-called fixed sequence arc selection problem (FSASP). We propose a dynamic programming solution method for this problem. In the context of an on-demand transportation (ODT) problem, we then propose a simple insertion algorithm based on iterative FSASP solving and a branch-and-price exact method. Computational experiments on modified instances from the literature and on realistic data issued from an ODT system in the French Doubs Central area underline the cost savings brought by the proposed methods using the multigraph model.     

不确定条件下的乡村中小学布局优化

学校的合理规划布局是实现教育资源优化配置、提高办学效益和推动教育均衡发展的重要途径。已有许多学者研究了学校的布局问题,但基本上都忽略了交通网络条件以及不确定因素对学校布局的影响。本研究将在前人研究基础上,重点考虑交通网络对乡村中小学选址的影响,并假设旅行时间具有不确定性,从而以最小化学生旅行成本、学校建设、道路修建和道路升级成本为目标,构建不确定条件下的设施区位设计模型。在算法求解方面提出混合模拟退火算法,用于确定新建学校的最佳位置,以及新道路的修建和原有道路的升级情况。最后,将提出的模型和算法应用到实际案例中。     

Vehicle routing and scheduling with time-varying data: A case study

A heuristic algorithm is described for vehicle routing and scheduling problems to minimise the total travel time, where the time required for a vehicle to travel along any road in the network varies according to the time of travel. The variation is caused by congestion that is typically greatest during morning and evening rush hours. The algorithm is used to schedule a fleet of delivery vehicles operating in the South West of the United Kingdom for a sample of days. The results demonstrate how conventional methods that do not take time-varying speeds into account when planning, except for an overall contingency allowance, may still lead to some routes taking too long. The results are analysed to show that in the case study using the proposed approach can lead to savings in CO₂ emissions of about 7%.     

带时空相关性分析的行车时间估计模型

基于流体动力学方程的行车时间估计模型不能很好地反映真实的行车时间,需要对其进行一定的改进.在对交通流进行流体动力学建模的基础之上,引入对高速公路路网中不同路段之间的行车时间相关性和同一路段不同季节、不同时段的行车时间相关性分析,建立了带时空相关性分析的时间估计模型,使用统计学的方法消除动力学模型的误差.     

Agent-based modelling and simulation of urban evacuation: relative effectiveness of simultaneous and staged evacuation strategies

This study investigates the effectiveness of simultaneous and staged evacuation strategies using agent-based simulation. In the simultaneous strategy, all residents are informed to evacuate simultaneously, whereas in the staged evacuation strategy, residents in different zones are organized to evacuate in an order based on different sequences of the zones within the affected area. This study uses an agent-based technique to model traffic flows at the level of individual vehicles and investigates the collective behaviours of evacuating vehicles. We conducted simulations using a microscopic simulation system called Paramics on three types of road network structures under different population densities. The three types of road network structures include a grid road structure, a ring road structure, and a real road structure from the City of San Marcos, Texas. Default rules in Paramics were used for trip generation, destination choice, and route choice. Simulation results indicate that (1) there is no evacuation strategy that can be considered as the best strategy across different road network structures, and the performance of the strategies depends on both road network structure and population density; (2) if the population density in the affected area is high and the underlying road network structure is a grid structure, then a staged evacuation strategy that alternates non-adjacent zones in the affected area is effective in reducing the overall evacuation time.     

A hybrid approach for optimal design of signalized road network

For a signalized road network with expansions of link capacity, the maximum possible increase in travel demands is considered while total delays for travelers are minimized. Using the concept of reserve capacity of signal-controlled junctions, the problem of finding the maximum possible increase in travel demand and determining optimal link capacity expansions can be formulated as optimization programs. In this paper, we present a new solution approach for simultaneously solving the maximum increase in travel demands and minimizing total delays of travelers. A projected Quasi-Newton method is proposed to effectively solve this problem to the KKT points. Numerical computations and comparisons are made on real data signal-controlled networks where obtained results outperform traditional methods.     

Modelling and optimization of average travel time for a metro line by simulation and response surface methodology

This research presents a modelling and solution approach based on discrete-event simulation and response surface methodology for dealing with average passenger travel time optimization problem inherent to the metro planning process. The objective is to find the headways optimizing passenger average travel time with a satisfactory rate of carriage fullness. Due to some physical constraints, traffic safety and legal requirements, vehicle speeds cannot be raised any further to decrease travel time. But travel time can be optimized by arranging headways (i.e. the time period between the departure times of two consecutive transportation vehicles) in a timetable. In the presented approach, simulation metamodels that best fit the data collected from the simulated experiments are constructed to describe the relationship between the responses (average travel time and rate of carriage fullness) and input factors (headways). Then, the Derringer–Suich multi-response optimization procedure is used to determine the optimal settings of the input factors that produce the minimum value of the average travel time by providing a proper rate of carriage fullness. This methodology is applied for a real metro line, and good quality solutions are obtained with reduced number of experiments that needed to provide sufficient information for statistically acceptable results.     

ATIS和道路收费下混合SUE相对于SSO的效率损失

在ATIS和道路收费共同作用的异质性交通网络中,基于用户在信息接受程度与时间价值上的异质性,对用户进行合理分类,所有用户均按照随机方式进行择路.构建了多用户混合随机均衡等价的变分不等式模型,以及多用户随机社会最优模型.以用户感知的总出行成本作为系统性能评价的指标,当收费作为系统总成本的一部分时,分别在时间准则与费用准则下研究了多用户混合随机均衡相对于随机社会最优的绝对效率损失问题.研究结果表明,时间准则下的绝对效率损失上界与路段出行时间函数和混合随机均衡时系统的实际总出行时间有关,费用准则下的绝对效率损失上界还与出行者的社会经济特性和随机社会最优时系统的实际总出行时间有关.     

A hybrid optimization algorithm for area traffic control problem

For an area traffic control road network subject to equilibrium flows, the maximum possible increase in travel demands is considered while total delays for travellers are minimized with respect to the common cycle time, the starts and durations of green times and the offsets. Using the concept of reserve capacity of signal-controlled junctions, the problem of finding the maximum increase in traffic demands can be formulated as a mathematical program with equilibrium constraints. In this paper, we present a hybrid optimization algorithm to simultaneously solve the maximum increase in travel demands and minimizing total delays of travellers. Numerical computations are made for the values of performance index and the reserve capacity achieved at various sets of initial signal settings on a variety of signal-controlled networks. Encouraging results are obtained when compared with other alternatives.     

基于内生参考点的交通网络均衡模型

应用累积前景理论研究了随机交通网络中出行者有限理性的路径选择行为,选择期望 超额出行时间作为参考点,反映出行者同时考虑出行时间的可靠性和不可靠性,建立了基于累积前景理论的随机网络均衡及其等价的变分不等式模型,运用基于连续平均法的启发式算法求解,并给出算例验证了该模型和算法,最后分析了有限理性的假设和内生的参考点对出行者路径选择行为和随机网络均衡的影响．     

考虑路网可靠性和空间公平性的次优拥挤收费模型

根据随机路网环境下出行者规避风险的路径选择行为,提出了一种考虑路网可靠性和空间公平性的次优拥挤收费双层规划模型。其中,上层模型以具有空间公平性约束条件下最大化路网的社会福利为目标,下层模型是实施拥挤收费条件下考虑行程时间可靠性的弹性需求用户平衡模型。鉴于双层规划模型的复杂性,设计了基于遗传算法和FrankWolfe算法的组合式算法来求解提出的模型。算例结果表明:考虑行程时间可靠性的次优拥挤收费会产生不同于传统次优拥挤收费的平衡流量分布模式,表明出行者的路径选择行为对拥挤收费结果会产生直接影响;此外,算例结果还说明遗传算法对参数设置具有很强的鲁棒性。     

改进蚁群算法在智能交通中的应用

为了诱导车辆在出行时选择较高质量的路线,提出并建立了城市道路权值仿真模型.为求解该模型,从分析基本蚁群算法入手,通过在状态转移规则中加入扰动因子,改进全局更新规则,以及引入信息素更新算子改进了蚁群算法.然后利用道路权值模型对两种算法在路径寻优效果上做了比较和分析,实验结果表明改进后的蚁群算法能有效地避免停留在局部最优解,并提高计算效率,具有良好的寻优性和收敛性,能准确找出路网中满足综合要求的最优路径.     

Emergency path restoration problems

We consider the problem of optimally scheduling the restoration of edges of a transportation network destroyed/damaged by a disaster. The restoration is performed by service units (servers) which have fixed restoration speeds. If several servers work simultaneously at the same point of the network, their collective restoration speed is the sum of their individual restoration speeds. The servers are initially located at some nodes. Each server can travel within the already restored part of the network with infinite speed, that is, at any time can immediately relocate to another point of the same connected component of the already restored part of the network. It is required to minimize a scheduling objective that can be expressed as the maximum or the sum of nondecreasing functions of the recovery times of the nodes, where the recovery time of a node is the time when the node is reached for the first time by a server. We present polynomial-time algorithms on path networks for problems with fixed initial locations of the servers. For problems with flexible locations that should also be optimized, we present polynomial-time algorithms for the case of equal restoration speeds of the servers, and prove that the problems are strongly NP-hard if the restoration speeds of the servers can be different.     

A continuous whole-link travel time model with occupancy constraint

The continuous dynamic network loading problem (CDNLP) aims to compute link travel times and path travel times on a congested network, given time-dependent path flow rates for a given time period. A crucial element of CDNLP is a model of the link performance. Two main modeling frameworks have been used in link loading models: The so-called whole-link travel time (WTT) models and the kinematic wave model of Lighthill–Whitham–Richards (LWR) for traffic flow.In this paper, we reformulate a well-known whole-link model in which the link travel time, for traffic entering a time t, is a function of the number of vehicles on link. This formulation does not require the satisfying of the FIFO (first in, first out) condition. An extension of the basic WTT model is proposed in order to take explicitly into account the maximum number of vehicles that the link can accommodate (occupancy constraint). A solution scheme for the proposed WTT model is derived.Several numerical examples are given to illustrate that the FIFO condition is not respected for the WTT model and to compare the travel time predictions effected by LWR and WTT models.     

基于畅通可靠性的开放小区交通流分配及优化决策

开放小区内部道路可增加城市道路网的密度和可达性,从而达到缓解城市道路拥堵的目的。通过对出行者进行问卷调查,得知其路径选择行为主要考虑出行时间及时间波动性两方面因素,基于此对CONTRAM费用函数进行改进,得到适用于小区开放后的广义出行费用,该费用考虑了畅通可靠性对路径选择的影响;结合小区开放后出行者选择准则,建立考虑广义出行费用的随机用户最优模型(SUO),并采用逐次平均算法(MSA)进行求解,从而得到更为精确的路段交通流量;基于小区道路开放后需承担的交通量,结合城市道路规划相关规范,对横断面、出入口等方面提出开放小区内部道路规划的建议。     

A modified active set algorithm for transportation discrete network design bi-level problem

Transportation discrete network design problem (DNDP) is about how to modify an existing network of roads and highways in order to improve its total system travel time, and the candidate road building or expansion plan can only be added as a whole. DNDP can be formulated into a bi-level problem with binary variables. An active set algorithm has been proposed to solve the bi-level discrete network design problem, while it made an assumption that the capacity increase and construction cost of each road are based on the number of lanes. This paper considers a more general case when the capacity increase and construction cost are specified for each candidate plan. This paper also uses numerical methods instead of solvers to solve each step, so it provides a more direct understanding and control of the algorithm and running procedure. By analyzing the differences and getting corresponding solving methods, a modified active set algorithm is proposed in the paper. In the implementation of the algorithm and the validation, we use binary numeral system and ternary numeral system to avoid too many layers of loop and save storage space. Numerical experiments show the correctness and efficiency of the proposed modified active set algorithm.