Point-to-point shortest paths on dynamic time-dependent road networks

This a summary of the author’s PhD thesis supervised by Leo Liberti, Philippe Baptiste and Daniel Krob and defended on 18 June 2009 at Ecole Polytechnique, Palaiseau, France. The thesis is written in English and is available at . The computation of point-to-point shortest paths in road networks has many practical applications that require very fast solution times, meaning that Dijkstra’s algorithm is not a viable option. In this work we develop an efficient algorithm to find the shortest route between two nodes of a large-scale, time-dependent graph, where we also allow the time-dependent arc cost functions to be updated at regular intervals. Furthermore, we propose a mathematical programming formulation for the shortest paths problem on time-dependent networks, that gives rise to integer programs. Within the context of solving Mixed-Integer Linear Programs through a Branch-and-Bound algorithm, we propose a new strategy for branching, mixing branching on single variables with branching on general hyperplanes. Finally, we introduce an effective heuristic for nonconvex Mixed-Integer Nonlinear Programss which combines VNS, Local Branching, NLP local search and Branch-and-Bound.     

Factorized time-dependent distributions for certain multiclass queueing networks and an application to?enzymatic processing networks

Motivated by applications in biological systems, we show for certain multiclass queueing networks that time-dependent distributions for the multiclass queue-lengths can have a factorized form which reduces the problem of computing such distributions to a similar problem for related single-class queueing networks. We give an example of the application of this result to an enzymatic processing network.     

Ranking paths in stochastic time-dependent networks

In this paper we address optimal routing problems in networks where travel times are both stochastic and time-dependent. In these networks, the best route choice is not necessarily a path, but rather a time-adaptive strategy that assigns successors to nodes as a function of time. Nevertheless, in some particular cases an origin–destination path must be chosen a priori, since time-adaptive choices are not allowed. Unfortunately, finding the a priori shortest path is an NP-hard problem.     

Mittag-Leffler stability of fractional-order Hopfield neural networks

Fractional-order Hopfield neural networks are often used to model how interacting neurons process information. To show reliability of the processed information, it is needed to perform stability analysis of these systems. Here, we perform Mittag-Leffler stability analysis for them. For this, we extend the second method of Lyapunov in the fractional-order case and establish a useful inequality that can be effectively used to this analysis. Importantly, these general results can help construct Lyapunov functions used to Mittag-Leffler stability analysis of fractional-order Hopfield neural networks. As a result, a set of sufficient conditions is derived to guarantee this stability. In addition, the general results can be easily used to the establishment of stability conditions for achieving complete and quasi synchronization in the coupling case of these networks with constant or time-dependent external inputs. Finally, two numerical examples are presented to show the effectiveness of our theoretical results.     

FE Analysis using Recurrent Neural Networks for Uncertain Stress-Strain-Time Dependencies

A new soft computing approach is described, which can be applied for the identification of uncertain time-dependent material behaviour. Artificial neural networks are utilized for model-free material formulations. Uncertain stress-strain-time dependencies obtained from uncertain results of experimental investigations are described by recurrent neural networks for fuzzy data. An incremental finite element formulation is presented using neural networks instead of material models. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Pathwise comparison results for stochastic fluid networks

We prove some new pathwise comparison results for single class stochastic fluid networks. Under fairly general conditions, monotonicity with respect to the (state- and time-dependent) routing matrices is shown. Under more restrictive assumptions, monotonicity with respect to the service rates is shown as well. We conclude by using the comparison results to establish a moment bound, a stability result for stochastic fluid networks with Lévy inputs, and a comparison result for multi-class GPS networks.     

Multiple periodic solutions in impulsive hybrid neural networks with delays

The existence of multiple periodic solutions and their exponential stability are investigated for impulsive hybrid Hopfield-type neural networks with both time-dependent and distributed delays, using the Leray-Schauder fixed point theorem and Lyapunov functionals. The criteria given are easily verifiable, possess many adjustable parameters, and depend on impulses, providing flexibility for the analysis and design of delayed neural networks with impulse effects. Examples are given.     

Approximate analysis of non-stationary loss queues and networks of loss queues with general service time distributions

A Fixed Point Approximation (FPA) method has recently been suggested for non-stationary analysis of loss queues and networks of loss queues with Exponential service times. Deriving exact equations relating time-dependent mean numbers of busy servers to blocking probabilities, we generalize the FPA method to loss systems with general service time distributions. These equations are combined with associated formulae for stationary analysis of loss systems in steady state through a carried load to offered load transformation. The accuracy and speed of the generalized methods are illustrated through a wide set of examples.     

Networks of infinite-server queues with nonstationary Poisson input

In this paper we focus on networks of infinite-server queues with nonhomogeneous Poisson arrival processes. We start by introducing a more general Poisson-arrival-location model (PALM) in which arrivals move independently through a general state space according to a location stochastic process after arriving according to a nonhomogeneous Poisson process. The usual open network of infinite-server queues, which is also known as a linear population process or a linear stochastic compartmental model, arises in the special case of a finite state space. The mathematical foundation is a Poisson-random-measure representation, which can be obtained by stochastic integration. It implies a time-dependent product-form result: For appropriate initial conditions, the queue lengths (numbers of customers in disjoint subsets of the state space) at any time are independent Poisson random variables. Even though there is no dependence among the queue lengths at each time, there is important dependence among the queue lengths at different times. We show that the joint distribution is multivariate Poisson, and calculate the covariances. A unified framework for constructing stochastic processes of interest is provided by stochastically integrating various functionals of the location process with respect to the Poisson arrival process. We use this approach to study the flows in the queueing network; e.g., we show that the aggregate arrival and departure processes at a given queue (to and from other queues as well as outside the network) are generalized Poisson processes (without necessarily having a rate or unit jumps) if and only if no customer can visit that queue more than once. We also characterize the aggregate arrival and departure processes when customers can visit the queues more frequently. In addition to obtaining structural results, we use the stochastic integrals to obtain explicit expressions for time-dependent means and covariances. We do this in two ways. First, we decompose the entire network into a superposition of independent networks with fixed deterministic routes. Second, we make Markov assumptions, initially for the evolution of the routes and finally for the entire location process. For Markov routing among the queues, the aggregate arrival rates are obtained as the solution to a system of input equations, which have a unique solution under appropriate qualifications, but not in general. Linear ordinary differential equations characterize the time-dependent means and covariances in the totally Markovian case.     

Betweenness in time dependent networks

The concept of betweenness has given rise to a very useful class of network centrality measures. Loosely, betweenness quantifies the level of importance of a node in terms of its propensity to act as an intermediary when messages are passed around the network. In this work we generalize a walk-based betweenness measure to the case of time-dependent networks, such as those arising in telecommunications and on-line social media. We also introduce a new kind of betweenness measure, temporal betweenness, which quantifies the importance of a time-point. We illustrate the effectiveness of these new measures on synthetic examples, and also give results on real data sets involving voice call, email and Twitter.     

Prediction of Time-Dependent Structural Responses with Recurrent Neural Networks

A concept for the mapping of fuzzy structural action processes onto fuzzy structural response processes is presented. Recurrent neural networks for fuzzy data are developed for this mapping. The presented method can be applied to the model-free numerical prediction of time-dependent structural responses. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Time-adaptive and history-adaptive multicriterion routing in stochastic, time-dependent networks

We compare two different models for multicriterion routing in stochastic time-dependent networks: the classic “time-adaptive” model and the more flexible “history-adaptive” one. We point out several properties of the sets of efficient solutions found under the two models. We also devise a method for finding supported history-adaptive solutions.     

Blocking Probabilities in Mobile Communications Networks with Time-Varying Rates and Redialing Subscribers

Call-blocking probabilities are among the key performance measures in mobile communications networks. For their analysis, mobile networks can be modelled as networks of Erlang loss queues with common capacity restrictions dictated by the allocation of frequencies to the cells of the network. However, due to the time-varying load offered to the cells of such networks, blocking probabilities usually cannot be obtained in closed form. The relation between networks of Erlang loss queues and networks of infinite server queues, for which the time-dependent occupancy distribution is multidimensional Poisson, suggests to use that distribution as approximate distribution for the network of Erlang loss queues. This paper extends this so-called Modified Offered Load (MOL) approximation to networks of Erlang loss queues, and also allows subscribers that find their call blocked to redial to continue their call. For GSM networks operating under Fixed Channel Allocation, it is shown that blocking probabilities are increasing in the redial rates so that the MOL approximation that is most accurate for maximal redial rates turns out to be fairly accurate for the resulting upper bound for blocking probabilities. The accuracy is explicitly evaluated in an application of the results towards blocking probabilities in a hot spot travelling along a road through a GSM network.     

由软件和硬件构成的串联可修计算机系统的适定性及渐近稳定性

讨论由软件和硬件构成的串联可修计算机系统的时间依赖解,运用C_0-半群理论及算子理论,证明系统的适定性和时间依赖非负解的存在唯一性.通过研究系统相应算子的谱特征,得到系统时间依赖解的渐近稳定性.     

Exponential stability of delayed fuzzy cellular neural networks with diffusion

The exponential stability of delayed fuzzy cellular neural networks (FCNN) with diffusion is investigated. Exponential stability, significant for applications of neural networks, is obtained under conditions that are easily verified by a new approach. Earlier results on the exponential stability of FCNN with time-dependent delay, a special case of the model studied in this paper, are improved without using the time-varying term condition: dτ(t)/dt < μ.     

Variational inequalities for a system of elliptic–parabolic equations

We create a general framework for mathematical study of variational inequalities for a system of elliptic–parabolic equations. In this paper, we establish a solvability theorem concerning the existence of solutions for the vector-valued elliptic–parabolic variational inequality with time-dependent constraint. Moreover, we give some applications of the system, for example, time-dependent boundary obstacle problem and time-dependent interior obstacle problem.     

Reliability function of a class of time-dependent systems with standby redundancy

By applying shortest path analysis in stochastic networks, we introduce a new approach to obtain the reliability function of time-dependent systems with standby redundancy. We assume that not all elements of the system are set to function from the beginning. Upon the failure of each element of the active path in the reliability graph, the system switches to the next path. Then, the corresponding elements are activated and consequently the connection between the input and the output is established. It is also assumed each element exhibits a constant hazard rate and its lifetime is a random variable with exponential distribution. To evaluate the system reliability, we construct a directed stochastic network called E-network, in which each path corresponds with a minimal cut of the reliability graph. We also prove that the system failure function is equal to the density function of the shortest path of E-network. The shortest path distribution of this new constructed network is determined analytically using continuous-time Markov processes.     

Stability on Time-Dependent Domains

We explore the key differences in the stability picture between extended systems on time-fixed and time-dependent spatial domains. As a paradigm, we take the complex Swift–Hohenberg equation, which is the simplest nonlinear model with a finite critical wavenumber, and use it to study dynamic pattern formation and evolution on time-dependent spatial domains in translationally invariant systems, i.e., when dilution effects are absent. In particular, we discuss the effects of a time-dependent domain on the stability of spatially homogeneous and spatially periodic base states, and explore its effects on the Eckhaus instability of periodic states. New equations describing the nonlinear evolution of the pattern wavenumber on time-dependent domains are derived, and the results compared with those on fixed domains. Pattern coarsening on time-dependent domains is contrasted with that on fixed domains with the help of the Cahn–Hilliard equation extended here to time-dependent domains. Parallel results for the evolution of the Benjamin–Feir instability on time-dependent domains are also given.     

Dynamic system optimal performances of shared autonomous and human vehicle system for heterogeneous travellers

ABSTRACT

Autonomous vehicles (AV) can solve vehicle relocation problems faced by traditional one-way vehicle-sharing systems. This paper explores the deterministic time-dependent system optimum of mixed shared AVs (SAV) and human vehicles (SHV) system to provide the benchmark for the situation of mixed vehicle flows. In such a system, the system planner determines vehicle-traveller assignment and optimal vehicle routing in transportation networks to serve predetermined travel demand of heterogeneous travellers. Due to large number of vehicles involved, travel time is considered endogenous with congestion. Using link transmission model (LTM) as a traffic flow model, the deterministic time-dependent system optimum is formulated as linear programming (LP) model to minimize the comprehensive cost including travellers’ travel time cost, waiting time cost and empty vehicle repositioning time cost. Numerical examples are conducted to show system performances and model effectiveness.     

A simulated annealing algorithm for transient optimization in gas networks

In this paper we present a simulated annealing approach for the gas network optimization problem. A gas network consists of a set of pipes to transport the gas from the sources to the sinks whereby gas pressure gets lost due to friction. Further on there are compressors, which increase gas pressure, and valves. The aim is to minimize fuel gas consumption of the compressors whereas demands of consumers have to be satisfied. The problem of transient (time-dependent) optimization of gas networks results in a highly complex mixed integer nonlinear program. We relax the equations describing the gas dynamic in pipes by adding these constraints combined with appropriate penalty factors to the objective function. A suitable neighborhood structure is developed for the relaxed problem where time steps as well as pressure and flow of the gas are decoupled. Our approach convinces with flexibility and very good computational results.