Assignment of add–drop multiplexer (ADM) rings and digital cross-connect system (DCS) mesh in telecommunication networks

This paper discusses a design of a hybrid ring–mesh network in a survivable communication network. Given a set of traffic demands, the problem is to assign each traffic demand to rings and mesh such that the cost of add–drop multiplexer (ADM) and digital cross-connect system (DCS) equipment required is minimized. This assignment problem can be considered together with the fibre routing of nodes on rings and mesh. As a solution procedure, a tabu search is developed with recency-based short-term and frequency-based long-term memory structures. In computational experiments, the proposed tabu search is compared with the solutions obtained by the branch and bound procedure of CPLEX. We see that the tabu search provides a nearly optimal solution within sufficiently short time periods for all test problems with a gap of approximately 1–4% from the lower bound.     

An optimization model and a solution algorithm for the many-to-many car pooling problem

Car pooling is one method that can be easily instituted and can help to resolve a variety of problems that continue to plague urban areas, ranging from energy demands and traffic congestion to environmental pollution. Although car pooling is becoming more common, in practice, participant matching results are still being obtained by an inefficient manual approach, which may possibly result in an inferior solution. In the past, when car pooling studies have been done the problem has been treated as either a to-work problem (from different origins to the same destination) or return-from-work problem (from the same origin to different destinations). However, in this study we employ a time-space network flow technique to develop a model for the many-to-many car pooling problem with multiple vehicle types and person types. The model is formulated as an integer multiple commodity network flow problem. Since real problem sizes can be huge, it could be difficult to find optimal solutions within a reasonable period of time. Therefore, we develop a solution algorithm based on Lagrangian relaxation, a subgradient method, and a heuristic for the upper bound solution, to solve the model. To test how well the model and the solution algorithm can be applied to real world, we randomly generated several examples based upon data reported from a past study carried out in northern Taiwan, on which we performed numerical tests. The test results show the effectiveness of the proposed model and solution algorithm.     

A framework for user equilibrium dynamic traffic assignment

Several analytic approaches have been developed to describe or predict traffic flows on networks with time-varying (dynamic) travel demands, flows and travel times. A key component of these models lies in modelling the flows and/or travel times on the individual links, but as this is made more realistic or accurate it tends to make the overall model less computationally tractable. To help overcome this, and for other reasons, we develop a bi-level user equilibrium (UE) framework that separates the assignment or loading of flows on the time–space network from the modelling of flows and trip times within individual links. We show that this model or framework satisfies appropriate definitions of UE satisfies a first-in-first-out (FIFO) property of road traffic, and has other desirable properties. The model can be solved by iterating between (a) a linear network-loading model that takes the lengths of time–space links as fixed (within narrow ranges), and (b) a set of link flow sub-models which update the link trip times to construct a new time–space network. This allows links to be processed sequentially or in parallel and avoids having to enumerate paths and compute path flows or travel times. We test and demonstrate the model and algorithms using example networks and find that the algorithm converges quickly and the solutions behave as expected. We show how to extend the model to handle elastic demands, multiple destinations and multiple traffic types, and traffic spillback within links and from link to link.     

Traffic assignment model with fuzzy level of travel demand: An efficient algorithm based on quasi-Logit formulas

The place of fuzzy concepts in traffic assignment (TA) models has been studied in recent literature. Keeping fuzzy level of travel demand in mind, we propose a new TA model in which the travel costs of links are depended on their congestion. From the results of such fuzzy TA model, network planners are able to estimate the number of travelers on network links. By using zero–one variables, the proposed model is transformed into a crisp mixed-integer problem with respect to path-flow variables. In order to produce the Logit flows from this problem, Damberg et al. algorithm is modified. Then, the level of certainty is maximized and perceived travel delays are minimized. For a fixed certainty degree, the obtained solution, which is named the fuzzy equilibrium flow, satisfies a quasi-Logit formula similar to ordinary expression of the Logit route choice model. Eventually, we examine the quality of different path enumeration techniques in the proposed model.     

Motorway traffic parameter estimation from mobile phone counts

In this paper a new method for real time estimation of vehicular flows and densities on motorways is proposed. This method is based on fusing traffic counts with mobile phone counts. The procedure used for the estimation of traffic flow parameters is based on the hypothesis that “instrumented” vehicles can be counted on specific motorway sections and traffic flow can be measured on entrance and exit ramps. The motorway is subdivided into cells, assuming that mobile phones entering and exiting every cell can be counted during the observation period. An estimate of “instrumented” vehicle concentration is obtained and propagated on the network in time and space. This allows one to estimate traffic flow parameters by sampling “instrumented” traffic flow parameters using a “concentration” (the ratio of the densities of instrumented vehicles to the density of overall traffic) propagation mechanism.     

Multi-period capacity expansion for a local access telecommunications network

In this paper, we examine a multi-period capacity expansion problem for a local access telecommunications network with a tree topology. Capacity expansion is realized through the installation of concentrators at the nodes and cables on the links of the network. Clearly, the installation of concentrators reduces the need for additional cables, and conversely. The goal is to find the least cost alternative to satisfy the demand. A heuristic approach is proposed to solve this problem, where local installation decisions at each node are propagated in the network. This information is then used to adjust prices that guide the decision process from one iteration to the next, until a fixed point is reached. Numerical results are reported on problem instances based on different cost and demand structures.     

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.     

Generalized minimal cost flow problem in fuzzy nature: An application in bus network planning problem

The aim of minimal cost flow problem (MCFP) in fuzzy nature, which is denoted with FMCFP, is to find the least cost of the shipment of a commodity through a capacitated network in order to satisfy imprecise concepts in supply or demand of network nodes and capacity or cost of network links. Fuzzy supply–demand may arise in real problems, where incomplete statistical data or simulation results are used. Also, variation in the cost or capacity of links is commonly happening. In the present paper, after defining a total order on LR type fuzzy numbers, three models are studied; MCFP with fuzzy costs, MCFP with fuzzy supply–demand and a combination of two cases. For the first model, scaling negative cycle cancelling algorithm, which is a polynomial time algorithm, is proposed. For the second model, “nominal flow” is introduced which provides an efficient scheme for finding fuzzy flow. For the third model, we present an exact and some heuristic methods. Numerical examples are illustrated to demonstrate the efficiency of the proposed schemes. Finally, an application of this viewpoint in bus network planning problem is provided.     

Routing and capacity assignment in backbone communication networks under time varying traffic conditions

This paper studies the problem of assigning capacities to links in a backbone communication network and determining the routes used by messages for all communicating node pairs in the network under time varying traffic conditions. The best routes are to be chosen from among all possible routes in the network. Tradeoffs between link costs and response time to users are achieved by specifying an upper limit on the average link queueing delay in the network. The goal is to minimize total link fixed and variable costs. The topology of the network and the end-to-end traffic requirements during the different busy-hours are assumed to be known. The problem is formulated as a mathematical programming model. An efficient solution procedure based on a Lagrangian relaxation of the problem is developed. The results of extensive computational experiments across a variety of networks are reported. These results indicate that the solution procedure is effective for a wide range of traffic loads and cost structures.     

Survivable capacitated network design problem: new formulation and Lagrangean relaxation

This work is focused on the analysis of the survivable capacitated network design problem. This problem can be stated as follows: Given a supply network with point-to-point traffic demands, specific survivability requirements, a set of available capacity ranges and their corresponding discrete costs for each arc, find minimum cost capacity expansions such that these demands can be met even if a network component fails. Solving this problem consists of selecting the links and their capacity, as well as the routings for each demand in every failure situation. This type of problem can be shown to be NP-hard. A new linear mixed-integer mathematical programming formulation is presented. An effective solution procedure based on Lagrangean relaxation is developed. Comparison heuristics and improvement heuristics are also described. Computational results using these procedures on different sizes of randomly generated networks are reported.     

Solving the minimum toll revenue problem in real transportation networks

As a means to relieve traffic congestion, toll pricing has recently received significant attention by transportation planners. Inappropriate use of transportation networks is one of the major causes of network congestion. Toll pricing is a method of traffic management in which traffic flow is guided to proper time and path in order to reduce the total delay in the network. This article investigates a method for solving the minimum toll revenue problem in real and large-scale transportation networks. The objective of this problem is to find link tolls that simultaneously cause users to efficiently use the transportation network and to minimize the total toll revenues to be collected. Although this model is linear, excessive number of variables and constraints make it very difficult to solve for large-scale networks. In this paper, a path-generation algorithm is proposed for solving the model. Implementation of this algorithm for different networks indicates that this method can achieve the optimal solution after a few iterations and a proper CPU time.     

Tree network design avoiding congestion

We introduce in this paper an optimal method for tree network design avoiding congestion. We see this problem arising in telecommunication and transportation networks as a flow extension of the Steiner problem in directed graphs, thus including as a particular case any alternative approach based on the minimum spanning tree problem. Our multi-commodity formulation is able to cope with the design of centralized computer networks, modern multi-cast multi-party or hub-based transportation trees. The objective in such cases is the minimization of the sum of the fixed (structural) and variable (operational) costs of all the arcs composing an arborescence that links the origin node (switching center, server, station) to every demand node (multi-cast participants, users in general). The non-linear multi-commodity flow model is solved by a generalized Benders decomposition approach.     

A Transportation Network Model as a Tool to Solve Urban Planning Location Problems

The aim of this paper is to formulate a transportation network model conceived as a basis of possible tools to be used by administrators and planners to approach location problems in a urban context. The key element of this model is a static representation of the transportation network, made of oriented links and nodes, connecting the facilities located in a prespecified urban area. Such a representation is based on an analogy of electric nature, thus allowing to exploit conventional electric networks solvers to determine the relevant features of the traffic flow in each link of the transportation network. The facility quality level is also taken into account in a quantitative fashion. Relying on the proposed model, different related results, such as the minimum path matrix and the induced traffic in each link of the network can be retrieved.     

A Comparison of Optimal Methods for Local Access Uncapacitated Network Design

We compare some optimal methods addressed to a problem of local access network design. We see this problem arising in telecommunication as a flow extension of the Steiner problem in directed graphs, thus including as particular cases some alternative approaches based on the spanning tree problem. We work with two equivalent flow formulations for the problem, the first referring to a single commodity and the second being a multicommodity flow model. The objective in both cases is the cost minimization of the sum of the fixed (structural) and variable (operational) costs of all the arcs composing an arborescence that links the origin node (switching center) to every demand node. The weak single commodity flow formulation is solved by a branch-and-bound strategy that applies Lagrangian relaxation for computing the bounds. The strong multicommodity flow model is solved by a branch-and-cut algorithm and by Benders decomposition. The use of a linear programming solver to address both the single commodity and the multicommodity models has also been investigated. Our experience suggests that a certain number of these modeling and solution strategies can be applied to the frequently occurring problems where basic optimal solutions to the linear program are automatically integral, so it also solves the combinatorial optimization problem right away. On the other hand, our main conclusion is that a well tailored Benders partitioning approach emerges as a robust method to cope with that fabricated cases where the linear programming relaxation exhibits a gap between the continuous and the integral optimal values.     

Optimal gossiping in paths and cycles

In the gossiping problem, each node in a network possesses a token initially; after gossiping, every node has a copy of every other node's token. The nodes exchange their tokens by packets. A solution to the problem is judged by how many rounds of packet sending it requires. In this paper, we consider the version of the problem in which a packet is of limited size (a packet can hold up to p tokens), the links (edges) of the network are half-duplex (only one packet can flow through a link at a time), and the nodes are all-port (a node's incident edges can all be active at the same time). We study the path and the cycle which are essential building blocks for more complex structures. We present tight lower bounds and algorithms which match them. The results also lead to the conclusion that p=2 is the optimal packet size.     

基于交通流的多模糊时间窗车辆路径优化

研究了基于交通流的多模糊时间窗车辆路径问题,考虑了实际中不断变化的交通流以及客户具有多个模糊时间窗的情况,以最小化配送总成本和最大化客户满意度为目标,构建基于交通流的多模糊时间窗车辆路径模型。根据伊藤算法的基本原理,设计了求解该模型的改进伊藤算法,结合仿真算例进行了模拟计算,并与蚁群算法的计算结果进行了对比分析,结果表明,利用改进伊藤算法求解基于交通流的多模糊时间窗车辆路径问题,迭代次数小,效率更高,能够在较短的时间内收敛到全局最优解,可以有效的求解多模糊时间窗车辆路径问题。     

A ring-mesh topology design problem for optical transport networks

This paper deals with a ring-mesh network design problem arising from the deployment of an optical transport network. The problem seeks to find an optimal clustering of traffic demands in the network such that the total cost of optical add-drop multiplexer (OADM) and optical cross-connect (OXC) is minimized, while satisfying the OADM ring capacity constraint, the node cardinality constraint, and the OXC capacity constraint. We formulate the problem as an integer programming model and propose several alternative modeling techniques designed to improve the mathematical representation of the problem. We then develop various classes of valid inequalities to tighten the mathematical formulation of the problem and describe an algorithmic approach that coordinates tailored routines with a commercial solver CPLEX. We also propose an effective tabu search procedure for finding a good feasible solution as well as for providing a good incumbent solution for the column generation based heuristic procedure that enhances the solvability of the problem. Computational results exhibit the viability of the proposed method.     

Neural network for the exact RLS adaptive algorithm

This paper proposes a neural network approach to the implementation of the exact recursive least-squares (RLS) algorithm. We show that the proposed neural network is guaranteed to be stable and to provide the results arbitrarily close to the accurate optimal solution of the RLS algorithm within an elapsed time of only a few characteristic time constants of the network. The parameters of the network (such as interconnections strengths and bias currents) can be obtained from the available data with a few computations, which are much fewer than the computations required in the exact RLS algorithm; as a result, this proposed scheme is very suitable for real time applications of the exact RLS algorithm.     

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.