Optimum departure times for commuters in congested networks

We propose an algorithm to compute the optimum departure time and path for a commuter in a congested network. Constant costs for use of arcs, cost functions of travel time depending on exogenous congestion and schedule delay are taken into account. A best path for a given departure time is computed with a previous algorithm for the generalized shortest path problem. The globally optimal departure time and an optimal path are determined by adapting Piyavskii's algorithm to the case of one-sided Lipschitz functions.This research has benefited from a grant of the Transportation Center of Northwestern University. The first author's research was partially supported by NSF grant No. SES-8911517 to Northwestern University. The second author's research was partially supported by AFOSR grants No. 89-0512 and 90-0008 to Rutgers University.     

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.     

Resource pooling in congested networks: proportional fairness and product form

We review two areas of recent research linking proportional fairness with product form networks. The areas concern, respectively, the heavy traffic and the large deviations limiting regimes for the stationary distribution of a flow model, where the flow model is a stochastic process representing the randomly varying number of document transfers present in a network sharing capacity according to the proportional fairness criterion. In these two regimes we postulate the limiting form of the stationary distribution, by comparison with several variants of the fairness criterion. We outline how product form results can help provide insight into the performance consequences of resource pooling.     

Location-allocation on a line with demand-dependent costs

This paper extends the location-allocation formulation by making the cost charged to users by a facility a function of the total number of users patronizing the facility. Users select their facility based on facility charges and transportation costs. We explore equilibria where each customer selects the least expensive facility (cost and transportation) and where the facility is at a point that minimizes travel costs for its customers. The problem in its general form is quite complex. An interesting special case is studied: facilities and customers are located on a finite line segment and demand is distributed on the line by a given density function.     

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).     

A set packing model for the ground holding problem in congested networks

Air traffic flow management (ATFM) consists of several activities performed by control authorities in order to reduce delays due to traffic congestion. Ground holding decisions restrict certain flights from tacking off at the scheduled departure time if congestion is expected at the destination airport. They are motivated by the fact that it is safer to hold an aircraft on the ground than in the air. Several integer linear programming models have been proposed to efficiently solve the ground holding problem (GHP). In this paper we investigate a set packing formulation of the GHP and design a branch-and-cut algorithm to solve the problem in high congestion scenarios, i.e., when lack of capacity induces flights cancellation. The constraint generation is carried out by heuristically solving the separation problem associated with a large class of rank inequalities. This procedure exploits the special structure of the GHP's intersection graphs. The computational results indicate that the proposed algorithm outperforms other algorithms in which flight cancellation has been allowed.     

A column generation algorithm for the estimation of origin–destination matrices in congested traffic networks

The general problem of estimating origin–destination (O–D) matrices in congested traffic networks is formulated as a mathematical programme with equilibrium constraints, referred to as the demand adjustment problem (DAP). This approach integrates the O–D matrix estimation and the network equilibrium assignment into one process. In this paper, a column generation algorithm for the DAP is presented. This algorithm iteratively solves a deterministic user equilibrium model for a given O–D matrix and a DAP restricted to the previously generated paths, whose solution generates a new O–D trip matrix estimation. The restricted DAP is formulated via a single level optimization problem. The convergence on local minimum of the proposed algorithm requires only the continuity of the link travel cost functions and the gauges used in the definition of the DAP.     

Location-allocation planning of stockpiles for effective disaster mitigation

In the existing framework for receiving and allocating Strategic National Stockpile (SNS) assistance, there are three noticeable delays: the delay by the state in requesting federal assets, the delay in the federal process which releases assets only upon the declaration of a disaster and lastly the time it takes to reach supplies rapidly from the SNS stockpile to where it is needed. The most efficient disaster preparedness plan is one that addresses all three delays taking into account the unique nature of each disaster. In this paper, we propose appropriate changes to the existing framework to address the first two delays and a generic model to address the third which determines the locations and capacities of stockpile sites that are optimal for a specific disaster. Specifically, our model takes into account the impact of disaster specific casualty characteristics, such as the severity and type of medical condition and the unique nature of each type of disaster, particularly with regard to advance warning and factors affecting damage. For disasters involving uncertainty (magnitude/severity) with regard to future occurrences, such as an earthquake, development of appropriate solution strategies involves an additional step using scenario planning and robust optimization. We illustrate the application of our model via case studies for hurricanes and earthquakes and are able to outline an appropriate response framework for each.     

Location-allocation models for traffic police patrol vehicles on an interurban network

This research investigates the traffic police routine patrol vehicle (RPV) assignment problem on an interurban road network through a series of integer linear programs. The traffic police RPV’s main task, like other emergency services, is to handle calls-for-service. Emergency services allocation models are generally based on the shortest path algorithm however, the traffic police RPV also handles other roles, namely patrolling to create a presence that acts as a deterrence, and issuing tickets to offenders. The RPVs need to be located dynamically on both hazardous sections and on roads with heavy traffic in order to increase their presence and conspicuousness, in an attempt to prevent or reduce traffic offences, road accidents and traffic congestion. Due to the importance of the traffic patrol vehicle’s location with regard to their additional roles, allocation of the RPVs adheres to an exogenous, legal, time-to-arrival constraint. We develop location-allocation models and apply them to a case study of the road network in northern Israel. The results of the four models are compared to each other and in relation to the current chosen locations. The multiple formulations provide alternatives that jointly account for road safety and policing objectives which aid decision-makers in the selection of their preferred RPV assignments. The results of the models present a location-allocation configuration per RPV per shift with full call-for-service coverage whilst maximizing police presence and conspicuousness as a proxy for road safety.     

带危险度瓶颈限制的服务站截流选址－分配模型研究

该文考虑带危险度瓶颈限制的服务站截流选址－分配问题(FCLM). 假设网络中各边有两个向量:长度和危险度. 对于有一个起点和多个讫点的FCLM问题,网络的安全费用是一个关于可抵御最大危险度等级的非递减函数. 该问题考虑如何选取可抵御最大危险度的等级和服务站的位置使得建站费用和安全费用之和最小. 文中建立了该问题的模型并提出了基于后序遍历的替代算法.     

Solving Location-allocation Problems with Rectilinear Distances by Simulated Annealing

The objective of this study is to use the simulated annealing method to solve minisum location-allocation problems with rectilinear distances. The major advantage of the simulated annealing method is that it is a very general and efficient algorithm for solving combinatorial optimization problems with know objective functions. In this study, a simulated annealing algorithm was developed to solve the location-allocation problems, and its performance was compared with two other popular methods for solving location-allocation problems. The results show that simulated annealing is a good alternative to the two methods, as measured by both the solution quality and the computational time.     

Transaction tagging in highly congested queueing simulations

The purpose of this paper is to illustrate how a very simple queueing model can be used to gain insight into a computer memory management strategy that is important for a large class of discrete-event simulation models. To this end, an elementary queueing model is used to demonstrate that it can be advantageous to run transaction-based simulations with a relatively few tagged transactions that collect data. The remaining transactions merely congest the system. Conceptually the tagged transactions flow through the simulation acting similar to radioactive trace elements inserted into a biological system. The queueing model analyzed in this paper provides insight into some trade-offs in simulation data collection. We show that, while resulting in a longer computer run, an optimal tagging interval greater than one will minimize the probability of prematurely aborting the run. Finally, we propose a heuristic procedure to estimate the optimal tagging interval. We illustrate this with an actual simulation study of a steel production facility.This research was partially supported by a grant to Cornell University by the Bethlehem Steel Corporation     

时间满意逐渐覆盖电动汽车充电站选址及算法

作为电动汽车配套的基础设施,电动汽车充电站的选址对电动汽车的推广有着十分重要的意义.针对电动汽车充电站选址问题,别入逐渐覆盖思想和时间满意度函数,从需求点效用最大化的角度出发,提出了基于时间满意逐渐覆盖电动汽车充电站选址模型,并运用蝙蝠算法通过MATLAB实现.实例的求解比较验证了该模型及算法在电动汽车充电站选址决策中的有效性.     

Developments in network location with mobile and congested facilities

We review four facility location problems which are motivated by urban service applications and which can be thought of as extensions of the classic Q-median problem on networks. In problems P1 and P2 it is assumed that travel times on network links change over time in a probabilistic way. In P2 it is further assumed that the facilities (servers) are movable so that they can be relocated in response to new network travel times. Problems P3 and P4 examine the Q-median problem for the case when the service capacity of the facilities is finite and, consequently, some or all of the facilities can be unavailable part of the time. In P3 the facilities have stationary home locations but in P4 they have movable locations and thus can be relocated to compensate for the unavailability of the busy facilities. We summarize our main results to date on these problems.     

Optimizing capacity,pricing and location decisions on a congested network with balking

In this paper, we consider the problem of making simultaneous decisions on the location, service rate (capacity) and the price of providing service for facilities on a network. We assume that the demand for service from each node of the network follows a Poisson process. The demand is assumed to depend on both price and distance. All facilities are assumed to charge the same price and customers wishing to obtain service choose a facility according to a Multinomial Logit function. Upon arrival to a facility, customers may join the system after observing the number of people in the queue. Service time at each facility is assumed to be exponentially distributed. We first present several structural results. Then, we propose an algorithm to obtain the optimal service rate and an approximate optimal price at each facility. We also develop a heuristic algorithm to find the locations of the facilities based on the tabu search method. We demonstrate the efficiency of the algorithms numerically.     

Selecting the location of minihubs for freight delivery in congested downtown areas

The delivery of freight in urban areas has to face many restrictions and regulations that constrain the efficient flow of goods. One of the most common regulations in medium and large cities is the establishment of access time windows, whereby delivery vehicles can only access the most central and congested areas of the city during a pre-specified period of the day. To avoid the costs imposed on carriers by this regulation while maintaining the social and environmental sustainability benefits, we propose here the establishment of a system of mini-hubs where delivery vehicles may park for the final deliveries to be completed on foot. Given that the optimal location of these mini-hubs is essential for the operation of the system, we formulate a location model and apply a computational process based on genetic algorithms to optimize it. We apply this procedure to a case study in the Spanish city of Seville, showing the effect of mini-hubs on the costs of the overall delivery system.     

A column generation heuristic for congested facility location problem with clearing functions

Nonlinear clearing functions, an idea initially suggested to reflect congestion effects in production planning, are used to express throughput of facilities prone to congestion in a facility location problem where each demand site is served by exactly one facility. The traditional constant capacity constraint for a facility is replaced with the nonlinear clearing function. The resulting nonlinear integer problem is solved by a column generation heuristic in which initial columns for the restricted master problem are generated by known existing algorithms and additional columns by a previously developed dynamic programming algorithm. Computational experimentation in terms of dual gap and CPU time based on both randomly generated and published data sets show not only clear dominance of the column generation over a Lagrangian heuristic previously developed, but also the high quality of results from the suggested heuristic for large problems.     

Fuzzy flows on networks

We present a theory of fuzzy flows on networks generalizing [2] and find closed formulas giving necessary and sufficient conditions for admissible flows to exist and for the maximal admissible flow.     

Recent advances on failure and recovery in networks of networks

Until recently, network science has focused on the properties of single isolated networks that do not interact or depend on other networks. However it has now been recognized that many real-networks, such as power grids, transportation systems, and communication infrastructures interact and depend on other networks. Here, we will present a review of the framework developed in recent years for studying the vulnerability and recovery of networks composed of interdependent networks. In interdependent networks, when nodes in one network fail, they cause dependent nodes in other networks to also fail. This is also the case when some nodes, like for example certain people, play a role in two networks, i.e. in a multiplex. Dependency relations may act recursively and can lead to cascades of failures concluding in sudden fragmentation of the system. We review the analytical solutions for the critical threshold and the giant component of a network of n interdependent networks. The general theory and behavior of interdependent networks has many novel features that are not present in classical network theory. Interdependent networks embedded in space are significantly more vulnerable compared to non-embedded networks. In particular, small localized attacks may lead to cascading failures and catastrophic consequences. Finally, when recovery of components is possible, global spontaneous recovery of the networks and hysteresis phenomena occur. The theory developed for this process points to an optimal repairing strategy for a network of networks. Understanding realistic effects present in networks of networks is required in order to move towards determining system vulnerability.