一种改进的公交配流模型与算法

对两种经典的公交配流模型进行了对比分析,指出了在考虑拥挤影响时两种模型进行公交配流各自存在的缺点．随后对两种模型存在的不足进行了原因分析,并在此基础上对Spiess和Florian提出的线性规划模型及算法进行了改进．改进的模型运用了“最优策略”和“有效频率”的思想, 考虑了拥挤对站点乘客等车时间的影响．模型用MSA（相继平均法）算法进行求解,最后在一个简单网络上进行对比分析,表明改进后的模型能够较合理地求解考虑站点拥挤的公交配流问题．     

多方式弹性需求下公交定价双层规划模型

为描述多方式城市交通网络下公交定价与出行选择行为的相互作用与影响,将出行方式选择与路径选择涵盖于同一网络,建立了上层模型分别以企业利润最大化、乘客出行成本最小化和社会福利最大化为目标函数,下层模型为多方式弹性需求随机用户配流模型的公交定价双层规划模型。运用改进遗传算法对模型整体进行求解,下层模型采用综合对角化算法和MSA算法的组合求解算法。最后,设计了一个算例以说明模型应用。结果表明:运用双层规划模型所确定的公交票价较传统静态票价可使政府、企业及出行者三方都获得更高收益,且上层模型以社会福利最大化为目标函数能代表社会群体中多数人利益,优化效果最为理想。     

Estimation of Transit Origin–Destination Matrices from Passenger Counts Using a Frequency-Based Approach

This paper investigates the transit passenger origin–destination (O–D) estimation problem in congested transit networks where updated passenger counts and outdated O–D matrices are available. The bi-level programming approach is used for the transit passenger O–D estimation problem. The upper level minimizes the sum of error measurements in passenger counts and O–D matrices, and the lower level is a new frequency-based stochastic user equilibrium (SUE) assignment model that can determine simultaneously the passenger overload delays and passenger route choices in congested transit network together with the resultant transit line frequencies. The lower-level problem can be formulated as either a logit-type or probit-type SUE transit assignment problem. A heuristic solution algorithm is developed for solving the proposed bi-level programming model which is applicable to congested transit networks. Finally, a case study on a simplified transit network connecting Kowloon urban area and the Hong Kong International Airport is provided to illustrate the applications of the proposed bi-level programming model and solution algorithm. This revised version was published online in July 2006 with corrections to the Cover Date.     

Transit passenger origin-destination estimation in congested transit networks with elastic line frequencies

This paper deals with the transit passenger origin-destination (O-D) estimation problem by using updated passenger counts in congested transit networks and outdated prior O-D matrix. A bilevel programming approach is extended for the transit passenger O-D updating problem where the upper-level problem seeks to minimize the sum of error measurements in passenger counts and O-D matrices, while the lower level is the stochastic user equilibrium assignment problem for congested transit networks. The transit assignment framework is based on a frequency-adaptive transit network model in this paper, which can help determine transit line frequencies and the network flow pattern simultaneously in congested transit networks. A heuristic solution algorithm is adapted for solving the transit passenger O-D estimation problem. Finally, a numerical example is used to illustrate the applications of the proposed model and solution algorithm. The work described in this paper was mainly supported by two research grants from the Research Grants Council of the Hong Kong Special Administrative Region (Project No. PolyU 5143/03E and PolyU 5040/02E).     

Optimization of transit route network,vehicle headways and timetables for large-scale transit networks

This paper presents a metaheuristic method for optimizing transit networks, including route network design, vehicle headway, and timetable assignment. Given information on transit demand, the street network of the transit service area, and total fleet size, the goal is to identify a transit network that minimizes a passenger cost function. Transit network optimization is a complex combinatorial problem due to huge search spaces of route network, vehicle headways, and timetables. The methodology described in this paper includes a representation of transit network variable search spaces (route network, headway, and timetable); a user cost function based on passenger random arrival times, route network, vehicle headways, and timetables; and a metaheuristic search scheme that combines simulated annealing, tabu, and greedy search methods. This methodology has been tested with problems reported in the existing literature, and applied to a large-scale realistic network optimization problem. The results show that the methodology is capable of producing improved solutions to large-scale transit network design problems in reasonable amounts of time and computing resources.     

The dynamic multilevel assignment problem as a stochastic extremal process

This paper considers the multilevel assignment problem (i.e. the assignment problem where the supply alternatives are ranked in hierarchical levels) under the assumption that the utility components for each pairwise matching are stochastic. A dynamic version of the multilevel stochastic assignment model is developed, where both demand and supply evaluate alternatives according to a stochastic extremal process, i.e. a process where the maximum of a sequence of random variables is taken into account. The probability distributions of the random variables which describe the joint dynamic behaviour of demand and supply are found. It is also shown that the assignment probabilities assume the structure of a nested-logit model.     

Carrier assignment models in transportation procurement

This paper extends carrier assignment models used in winner determination auctions for transportation procurement to include shipper non-price objectives and carrier transit point costs. The models are unlike traditional carrier assignment models which incorporate only carrier lane bids, and different from combinatorial auction models which focus on packets of lanes without considering transit point costs. We develop solutions, including metaheuristics, for the new models and through computational experimentation show that the algorithms work well and can be easily implemented.     

Application of a simulation-based dynamic traffic assignment model

The evaluation of on-line intelligent transportation system (ITS) measures, such as adaptive route-guidance and traffic management systems, depends heavily on the use of faster than real time traffic simulation models. Off-line applications, such as the testing of ITS strategies and planning studies, are also best served by fast-running traffic models due to the repetitive or iterative nature of such investigations. This paper describes a simulation-based, iterative dynamic equilibrium traffic assignment model. The determination of time-dependent path flows is modeled as a master problem that is solved using the method of successive averages (MSA). The determination of path travel times for a given set of path flows is the network-loading sub-problem, which is solved using the space-time queuing approach of Mahut. This loading method has been shown to provide reasonably accurate results with very little computational effort. The model was applied to the Stockholm road network, which consists of 2100 links, 1191 nodes, 228 zones, representing and 4964 turns. The results show that this model is applicable to medium-size networks with a very reasonable computation time.     

Handling uncertainty in route choice models: From probabilistic to possibilistic approaches

In order to design effective advanced traffic information systems (ATIS) suitable mathematical models have to be defined to simulate the effects of information on users route choice behaviour and then to incorporate it into traffic assignment models to estimate how traffic demand loads the roads network.To face this problem it is necessary to deal with uncertainty that plays a crucial role in the users decision-making processes.To this purpose this paper first analyses how uncertainty affects users’ route choice process and how traffic assignment models may take it into account.In literature route choice behaviour modelling is widely solved within the random utility theory framework but, we show in this paper that such an approach only considers one type of uncertainty. More precisely, the consideration of randomness of traffic by drivers is, for example, hardly ever represented in classical models in spite of its importance in the management of information by drivers.Starting from the presented analysis a new route choice model is also proposed to represent explicitly the uncertainty lying in users’ route choice behaviour. It is based on recent developments in possibility theory which is an alternate way to probability theory in order to represent or measure uncertainty.     

A demand model with departure time choice for within-day dynamic traffic assignment

A within-day dynamic demand model is formulated, embodying, in addition to the classic generation, distribution and modal split stages, an actual demand model taking into account departure time choice. The work focuses on this last stage, represented through an extension of the discrete choice framework to a continuous choice set. The dynamic multimodal supply and equilibrium model based on implicit path enumeration, which have been developed in previous work are outlined here, to define within-day dynamic elastic demand stochastic multimodal equilibrium as a fixed point problem on users flows and transit line frequencies. A MSA algorithm capable, in the case of Logit route choice models, of supplying equilibrium flows and frequencies on real dimension networks, is presented, as well as the specific procedures implementing the departure time choice and actual demand models. Finally, the results obtained on a test network are presented and conclusions are drawn.     

System optimal and user equilibrium time-dependent traffic assignment in congested networks

This paper formulates two dynamic network traffic assignment models in which O-D desires for the planning horizon are assumed known a priori: the system optimal (SO) and the user equilibrium (UE) time-dependent traffic assignment formulations. Solution algorithms developed and implemented for these models incorporate a traffic simulation model within an overall iterative search framework. Experiments conducted on a test network provide the basis for a comparative analysis of system performance under the SO and UE models.     

Airline crew scheduling from planning to operations

Crew scheduling problems at the planning level are typically solved in two steps: first, creating working patterns, and then assigning these to individual crew. The first step is solved with a set covering model, and the second with a set-partitioning model. At the operational level, the (re) planning period is considerably smaller than during the strategic planning phase. We integrate both models to solve time critical crew recovery problems arising on the day of operations. We describe how pairing construction and pairing assignment are done in a single step, and provide solution techniques based on simple tree search and more sophisticated column generation and shortest-path algorithms.     

Increasing the operational efficiency of container terminals in Australia

This paper discusses the major factors influencing the transfer efficiency of rail container terminals, as measured by the throughput time of containers. An analytically based simulation model is designed to describe container progress in the system. Cyclic heuristic rules for equipment assignment are applied and a new heuristic rule is developed to dispatch trains to tracks. The simulation model combined with the heuristic rules is used to address a number of specific objectives of the study. Different performance measures are applied and the impact that the train-to-track despatching and the handling equipment assignment can have on the measures is established. Validation and testing of models make use of data from Acacia Ridge Terminal, Brisbane, Australia.     

Comprehensive optimization of urban rail transit timetable by minimizing total travel times under time-dependent passenger demand and congested conditions

The comprehensive optimization of the timetables of urban rail transit systems under more realistic conditions is essential for their practical operation. Currently, most time-dependent timetabling models do not adequately consider train capacity and variable operation parameters. To bridge this gap, this study mainly investigates the timetable design problem of the urban rail transit system so as to adapt to time-dependent passenger demand under congested conditions by considering the variable number of trains, train running time, and train dwell time. Two nonlinear non-convex programming models are formulated to design timetables with the objective of minimizing the total passenger travel time (TTT) under the constraints of train operations, and passenger boarding and alighting processes. The difference between the two models is that one is a train-capacity unconstrained model and the other is a train-capacity constrained model. The proposed models are examined through real-world cases solved by the adaptive large neighborhood search algorithm. The results show that the first model can minimize passenger TTT under dynamic passenger demand, whereas the second can comprehensively optimize passenger TTT and meantime keep the train load factor within a reasonable level. Accordingly, it is concluded that the proposed models are more realistic.     

Uncertain agency models with multi-dimensional incomplete information based on confidence level

This paper discusses a principal–agent problem with multi-dimensional incomplete information between a principal and an agent. Firstly, how to describe the incomplete information in such agency problem is a challenging issue. This paper characterizes the incomplete information by uncertain variable, because it has been an appropriate tool to depict subjective assessment and model human uncertainty. Secondly, the relevant literature often used expected-utility-maximization to measure the two participators’ goals. However, Ellsberg paradox indicates that expected utility criterion is not always appropriate to be regarded as decision rule. For this reason, this paper presents another decision rule based on confidence level. Instead of expected-utility-maximization, the principal’s aim is to maximize his potential income under the acceptable confidence level, and the agent’s aim depends on whether he has private information about his efforts. According to the agent’s different decision rules, three classes of uncertain agency (UA) models and their respective optimal contracts are presented. Finally, a portfolio selection problem is studied to demonstrate the modeling idea and the viability of the proposed UA models.     

Dynamic job assignment: A column generation approach with an application to surgery allocation

We consider the assignment of jobs to heterogeneous agents in a dynamic system with a rolling time horizon. An example is a hospital operating theatre where the jobs are surgeries and the agents are the surgeons. The paper is presented in the context of surgery allocation and the system is characterized as follows: Patients are grouped into categories and they arrive continually following a stochastic process. Patients in each group have specific time limits within which they need treatment and if it cannot be accommodated then the patients are outsourced. The service level is the percentage of patients in each group treated within the time limit. Surgery durations are stochastic and depend on the surgeon conducting the surgeries. Each surgeon has limited time available and expected overtime is penalized by a non-decreasing convex function. We develop a column generation approach for the assignment of already arrived patients and tentative future patients to surgeons on specific days. It balances the conflicting objectives of including as many arrived patients as possible within their time limits, maximizing the service level of future patients, and minimizing the expected overtime of surgeons. A computational study is conducted with the model embedded in a rolling time horizon frame. The study indicates that the assignment of patients based on our model increases system performance in terms of service level and reduced overtime compared to a First-Come-First-Served (FCFS) policy when the arrival rates of patients are medium to high compared to the capacity of the system.     

On the maximum small-world subgraph problem

A clique (or a complete subgraph) is a popular model for an “ideal” cluster in a network. However, in many practical applications this notion turns out to be overly restrictive as it requires the existence of all pairwise links within the cluster. Thus, the researchers and practitioners often rely on various clique relaxation ideas for more flexible models of highly connected clusters. In this paper, we propose a new clique relaxation model referred to as a small-world subgraph, which represents a network cluster with “small-world” properties: low average distance and high clustering coefficient. In particular, we demonstrate that the proposed small-world subgraph model has better “cohesiveness” characteristics than other existing clique relaxation models in some worst-case scenarios. The main focus of the paper is on the problem of finding a small-world subgraph of maximum cardinality in a given graph. We describe a mixed integer programming (MIP) formulation of the problem along with several algorithmic enhancements. For solving large-scale instances of the problem we propose a greedy-type heuristic referred to as the iterative depth-first search (IDF) algorithm. Furthermore, we show that the small-world subgraphs identified by the IDF algorithm have an additional property that may be attractive from the practical perspective, namely, 2-connectivity. Finally, we perform extensive computational experiments on real-world and randomly generated networks to demonstrate the performance of the developed computational approaches that also reveal interesting insights about the proposed clique relaxation model.     

Decentralized controllers design for open-channel hydraulic systems via eigenstructure assignment

In this paper, we propose the design of both a proportional (P) and a proportional integral (PI) decentralized controller for open-channel hydraulic systems by assigning the closed-loop eigenstructure. The system dynamic is described by a linear, time-invariant model deduced from the Saint-Venant equations. A constant-volume control law is designed, satisfying the requirement of decentralization, typical of large-scale systems like the hydraulic one herein examined. The synthesis procedure followed in this paper allows us to derive a parametric expression for the set of feedback gains of decentralized controllers which achieve the desired eigenvalue assignment. The free parameters in this parametric expression can be used to assign eigenvectors as close to the desired ones as possible, while achieving the required eigenvalue assignment.     

Assigning cross-trained workers to departments: A two-stage optimization model to maximize utility and skill improvement

We develop a general framework that is applicable in both manufacturing and service settings for assigning cross-trained workers across departments. The framework consists of a two-stage optimization model where two objective functions, departmental utility and skill improvement, are considered sequentially. Departmental utility is a function of departmental labor shortage and the first-stage optimization model maximizes total departmental utility subject to typical assignment constraints. The second stage model seeks to maximize total skill improvement, which is quantified by a hyperbolic learning curve, while trying not to deviate from the utility level obtained during the first stage optimization. Our computational experiments suggest that incorporating the skill improvement function explicitly in the model results in significant improvement in the total skill level of the workforce and thus leads to more effective worker assignments.