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

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

User equilibrium traffic network assignment with stochastic travel times and late arrival penalty

The classical Wardrop User Equilibrium (UE) assignment model assumes traveller choices are based on fixed, known travel times, yet these times are known to be rather variable between trips, both within and between days; typically, then, only mean travel times are represented. Classical Stochastic User Equilibrium (SUE) methods allow the mean travel times to be differentially perceived across the population, yet in a conventional application neither the UE or SUE approach recognises the travel times to be inherently variable. That is to say, there is no recognition that drivers risk arriving late at their destinations, and that this risk may vary across different paths of the network and according to the arrival time flexibility of the traveller. Recent work on incorporating risky elements into the choice process is seen either to neglect the link to the arrival constraints of the traveller, or to apply only to restricted problems with parallel alternatives and inflexible travel time distributions. In the paper, an alternative approach is described based on the ‘schedule delay’ paradigm, penalising late arrival under fixed departure times. The approach allows flexible travel time densities, which can be fitted to actual surveillance data, to be incorporated. A generalised formulation of UE is proposed, termed a Late Arrival Penalised UE (LAPUE). Conditions for the existence and uniqueness of LAPUE solutions are considered, as well as methods for their computation. Two specific travel time models are then considered, one based on multivariate Normal arc travel times, and an extended model to represent arc incidents, based on mixture distributions of multivariate Normals. Several illustrative examples are used to examine the sensitivity of LAPUE solutions to various input parameters, and in particular its comparison with UE predictions. Finally, paths for further research are discussed, including the extension of the model to include elements such as distributed arrival time constraints and penalties.     

ATIS和道路收费下的混合随机用户均衡的效率损失

在ATIS作用下的交通网络中,用户在交通信息的接受程度上是异质的;考虑到装有ATIS的用户并不总是遵循ATIS的建议,因此,引入信息遵从率这一参数,将所有用户分为三类:安装并遵从信息、安装但不遵从信息和不安装的用户;均按照随机用户均衡的方式进行择路,但对出行时间有不同的感知。同时考虑存在道路收费的情形下,用户在时间价值上是异质的。综合考虑交通信息与道路收费的影响,基于用户两方面的异质性,对其进行合理分类,构建了多用户多准则的混合随机均衡模型及其等价的变分不等式;当收费不作为系统总成本的一部分时,建立了时间准则与费用准则下的系统最优模型;在此基础之上,分别研究了两种准则下混合均衡相对于系统最优的效率损失,给出了效率损失上界,并进一步分析了效率损失上界与各参数间的关系;交通管理者可以从道路收费策略的实施、信息诱导系统的完善等角度进行路网的改造和优化设计。     

Applications of sensitivity analysis for probit stochastic network equilibrium

Network equilibrium models are widely used by traffic practitioners to aid them in making decisions concerning the operation and management of traffic networks. The common practice is to test a prescribed range of hypothetical changes or policy measures through adjustments to the input data, namely the trip demands, the arc performance (travel time) functions, and policy variables such as tolls or signal timings. Relatively little use is made, however, of the full implicit relationship between model inputs and outputs inherent in these models. By exploiting the representation of such models as an equivalent optimisation problem, classical results on the sensitivity analysis of non-linear programs may be applied, to produce linear relationships between input data perturbations and model outputs. We specifically focus on recent results relating to the probit Stochastic User Equilibrium (PSUE) model, which has the advantage of greater behavioural realism and flexibility relative to the conventional Wardrop user equilibrium and logit SUE models. The paper goes on to explore four applications of these sensitivity expressions in gaining insight into the operation of road traffic networks. These applications are namely: identification of sensitive, ‘critical’ parameters; computation of approximate, re-equilibrated solutions following a change (post-optimisation); robustness analysis of model forecasts to input data errors, in the form of confidence interval estimation; and the solution of problems of the bi-level, optimal network design variety. Finally, numerical experiments applying these methods are reported.     

求解用户平衡与系统最优模型的新算法

近些年,国内外许多学者针对交通规划提出了诸如用户平衡(UE)、系统最优(SO)等模型,但由于交通网络的复杂性,这些模型的求解相对困难,考虑到在一般的UE、S0模型中,其约束条件为线性约束与非负约束,给出一种求解交通规划模型的新算法,算法不需使用任何线搜索,只要通过求解一个简单的二次规划问题得到下降方向即可,最后,将该算法应用到简单的交通网络中,并通过与相继平均法(MSA)进行比较,验证了该算法的收敛速度较快。     

OD估计双层规划扩展模型

利用双层规划模型进行OD估计,建立双层规划扩展模型.考虑OD估计问题中的随机误差,基于Bayes估计和多元正态分布建立上层目标函数;考虑用户路径选择行为的随机性,基于随机用户均衡建立需求可变动的下层目标函数,同时该扩展模型能适应我国混合交通的实际,既能适用于拥挤网络、也能适用于非拥挤网络,最后通过算例证明此模型的有效性.     

A turning restriction design problem in urban road networks

Turning restriction is one of the commonest traffic management techniques and an effective low cost traffic improvement strategy in urban road networks. However, the literature has not paid much attention to the turning restriction design problem (TRDP), which aims to determine a set of intersections where turning restrictions should be implemented. In this paper, a bi-level programming model is proposed to formulate the TRDP. The upper level problem is to minimize the total travel cost from the viewpoint of traffic managers, and the lower level problem is to depict travelers’ route choice behavior based on stochastic user equilibrium (SUE) theory. We propose a branch and bound method (BBM), based on the sensitivity analysis algorithm (SAA), to find the optimal turning restriction strategy. A branch strategy and a bound strategy are applied to accelerate the solution process of the TRDP. The computational experiments give promising results, showing that the optimal turning restriction strategy can obviously reduce system congestion and are robust to the variations of both the dispersion parameter of the SUE problem and the level of demand.     

Optimisation of timetable-based, stochastic transit assignment models based on MSA

Public transport assignment models have increased in complexity in order to describe passengers' route choices as detailed and correctly as possible. Important trends in the development are (1) timetable-based assignment, (2) inclusion of feeder modes, (3) use of stochastic components to describe differences in passengers' preferences within and between purposes and classes (random coefficients), as well as to describe non-explained variation within a utility theory framework, and (4) consideration of capacity problems at coach level, system level and terminal level. In the Copenhagen-Ringsted Model (CRM), such a large-scale transit assignment model was developed and estimated. The Stochastic User Equilibrium problem was solved by the Method of Successive Averages (MSA). However, the model suffered from very large calculation times. The paper focuses on how to optimise transit assignment models based on MSA combined with a generalised utility function. Comparable tests are carried out on a large-scale network. The conclusion is that there is potential of optimising MSA-based methods. Examples of different approaches for this is presented, tested and discussed in the paper.     

An MPCC approach for stochastic Stackelberg–Nash–Cournot equilibrium

In this article, we investigate a Stochastic Stackelberg–Nash–Cournot Equilibrium problem by reformulating it as a Mathematical Program with Complementarity Constraints (MPCC). The complementarity constraints are further reformulated as a system of nonsmooth equations. We characterize the followers’ Nash–Cournot equilibria by studying the implicit solution of a system of equations. We outline numerical methods for the solution of a stochastic Stackelberg–Nash–Cournot Equilibrium problem with finite distribution of market demand scenarios and propose a discretization approach based on implicit numerical integration to deal with stochastic Stackelberg–Nash–Cournot Equilibrium problem with continuous distribution of demand scenarios. Finally, we discuss the two-leader Stochastic Stackelberg–Nash–Cournot Equilibrium problem.     

基于结构方程模型的旅游网站使用者满意度量的比较研究

基于电子商务系统成功(ECSS)模型和旅游网站使用者满意(TWUS)模型,本文构建了评价旅游网站使用者满意的概念模型,并通过结构方程模型(SEM)分析方法,对度量模型与在线调查获得的837份有效数据的拟合程度进行了比较,发现TWUS模型对旅游网站使用者满意问题具有更强的解释能力。最后,本文对造成两个模型解释能力差异的原因进行了讨论。     

Minimising the number of aircraft for a transportation network

A case is presented of a transportation problem involving eight locations. Known for each location is the quantity of goods to be shipped by air to the other seven locations and the travel time between locations. The transport can be directly to each destination or via other locations. The capacity of the aircraft is specified. The transportation has to be completed between 10 p.m. and 5 a.m.This problem was solved in three stages. First a lower bound for the number of aircraft was determined. Secondly a network was established by mixed integer programming which minimizes the total travel time to transport all the goods to their respective destinations without violating the capacity constraints. Thirdly, the individual aircraft were assigned to part of the network in such a way that the total travel time per aircraft is within the specified time period.     

A synthesis of assignment and heuristic solutions for vehicle routing with time windows

This paper proposes a three-stage method for the vehicle-routing problem with time window constraints (VRPTW). Using the Hungarian method the optimal customer matching for an assignment approximation of the VRPTW, which is a travel time-based relaxation that partially respects the time windows, is obtained. The assignment matching is transformed into feasible routes of the VRPTW via a simple decoupling heuristic. The best of these routes, in terms of travelling and vehicle waiting times, form part of the final solution, which is completed by the routes provided by heuristic methods applied to the remainder of the customers. The proposed approach is tested on a set of standard literature problems, and improves the results of the heuristic methods with respect to total travel time. Furthermore, it provides useful insights into the effect of employing optimal travel time solutions resulting from the assignment relaxation to derive partial route sets of the VRPTW.     

Reliability based assignment in stochastic-flow freight network

Based on the reliability of transportation time, a transportation assignment model of stochastic-flow freight network is designed in this paper. This transportation assignment model is built by mean of stochastic chance-constraint programming and solved with a hybrid intelligent algorithm (HIA) which integrates genetic algorithm (GA), stochastic simulation (SS) and neural network (NN). GA is employed to report the optimal solution as well as the optimal objective function values of the proposed model. SS is used to simulate the value of uncertain system reliability function. The uncertain function approximated via NN is embedded into GA to check the feasibility and to compute the fitness of the chromosomes. These conclusions have been drawn after a test of numerical case using the proposed formulations. System reliability, total system cost and flow on each path would finally reach at their own convergence points. Increase of the system reliability causes increase of the total time cost. The system reliability and the total time cost converge at a possible Nash Equilibrium point.     

Reliability-based user equilibrium in a transport network under the effects of speed limits and supply uncertainty

This study investigates the system-wide traffic flow re-allocation effect of speed limits in uncertain environments. Previous studies have only considered link capacity degradation, which is only one of the factors that lead to supply uncertainty. This study examines how imposing speed limits reallocates the traffic flows in a situation of general supply uncertainty with risk-averse travelers. The effects of imposing a link-specific speed limit on link driving speed and travel time are analyzed, given the link travel time distribution before imposing the speed limit. The expected travel time and travel time standard deviation of a link with a speed limit are derived from the link travel time distribution and are both continuous, monotone, and convex functions in terms of link flow. A distribution-free, reliability-based user equilibrium with speed limits is established, in which travelers are assumed to choose routes that minimize their own travel time budget. A variational inequality formulation for the equilibrium problem is proposed and the solution properties are provided. In this study, the inefficiency of a reliability-based user equilibrium flow pattern with speed limits is defined and found to be bounded above when supply uncertainty refers to capacity degradation. The upper bound depends on the level of risk aversion of travelers, a ratio related to the design and worst-case link capacities, and the highest power of all link performance functions.     

A two-pheromone trail ant colony system—tabu search approach for the heterogeneous vehicle routing problem with time windows and multiple products

This paper considers a practical variant of the Vehicle Routing Problem (VRP) known as the Heterogeneous Vehicle Routing Problem with Time Windows and Multiple Products (HVRPTWMP). As the problem is NP-hard, the resolution approach proposed here is a sequential Ant Colony System (ACS)—Tabu Search algorithm. The approach introduces a two pheromone trail strategy to accelerate agents’ (ants) learning process. Its convergence to good solutions is given in terms of fleet size and travel time while completing tours and service to all customers. The proposed procedure uses regency and frequency memories form Tabu Search to further improve the quality of solutions. Experiments are carried out using instances from literature and show the effectiveness of this procedure.     

Position-specific information in social networks: Are you connected?

Individuals in social networks often imperfectly monitor others’ network relationships and have incomplete information about the value of forming new relationships. This paper introduces the Generalized Conjectural Equilibrium (GCE) concept for such settings and completely characterizes the set of GCE networks when players observe only local parts of the network. Incomplete information and imperfect monitoring generate different types of inefficiency. These inefficiencies increase in number and scope as network observation becomes more localized. These results suggest that actual social networks will be structured inefficiently in general.     

Minimizing total weighted completion time in a two-machine flow shop scheduling under simple linear deterioration

In this paper, we address a two-machine flow shop scheduling problem under simple linear deterioration. By a simple linear deterioration function, we mean that the processing time of a job is a simple linear function of its execution start time. The objective is to find a sequence that minimizes total weighted completion time. Optimal schedules are obtained for some special cases. For the general case, several dominance properties and two lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. A heuristic algorithm is also proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational analysis on randomly generated problems is conducted to evaluate the branch-and-bound algorithm and heuristic algorithm.     

Turning restriction design in traffic networks with a budget constraint

The restriction (prohibition) of certain turns at intersections is a very common task employed by the managers of urban traffic networks. Surprisingly, this approach has received little attention in the research literature. The turning restriction design problem (TRDP) involves finding a set of turning restrictions at intersections to promote flow in a congested urban traffic network. This article uses a successive linear approximation (SLA) method for identifying approximate solutions to a nonlinear model of the TRDP. It aims to adjust the current turning restriction regime in a given network in order to minimize total user travel cost when route choice is driven by user equilibrium principles. Novel features of the method include the facts that it is based on link capacity-based arc travel costs and there is a budget constraint on the total cost of all turning restriction alterations. It has been tested using standard network examples from the literature. One of the tests utilized a multi-start approach which improved the solutions produced by the SLA method. The method was also employed to identify turning restrictions for an actual medium-sized urban traffic network in Brazil. Computational experience with the proposed method is promising.     

Solving the logit-based stochastic user equilibrium problem with elastic demand based on the extended traffic network model

This paper proposes a novel extended traffic network model to solve the logit-based stochastic user equilibrium (SUE) problem with elastic demand. In this model, an extended traffic network is established by properly adding dummy nodes and links to the original traffic network. Based on the extended traffic network, the logit-based SUE problem with elastic demand is transformed to the SUE problem with fixed demand. Such problem is then further converted to a linearly constrained convex programming and addressed by a predictor–corrector interior point algorithm with polynomial complexity. A numerical example is provided to compare the proposed model with the method of successive averages (MSA). The numerical results indicate that the proposed model is more efficient and has a better convergence than the MSA.     

A bi-criteria two-machine flowshop scheduling problem with a learning effect

This paper addresses a bi-criteria two-machine flowshop scheduling problem when the learning effect is present. The objective is to find a sequence that minimizes a weighted sum of the total completion time and the maximum tardiness. In this article, a branch-and-bound method, incorporating several dominance properties and a lower bound, is presented to search for the exact solution for small job-size problems. In addition, two heuristic algorithms are proposed to overcome the inefficiency of the branch-and-bound algorithm for large job-size problems. Finally, computational results for this problem are provided to evaluate the performance of the proposed algorithms.