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.     

On the flow cost lowering problem

This paper presents the flow cost lowering problem (FCLP), which is an extension to the integral version of the well-known minimum cost flow problem (MCFP). While in the MCFP the flow costs are fixed, the FCLP admits lowering the flow cost on each arc by upgrading the arc. Given a flow value and a bound on the total budget which can be used for upgrading the arcs, the goal is to find an upgrade strategy and a flow of minimum cost. The FCLP is shown to be NP-hard even on series–parallel graphs. On the other hand the paper provides a polynomial time approximation algorithm on series–parallel graphs.     

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.     

Heuristics for multi-period capacity expansion in local telecommunications networks

In this paper, different heuristics are devised to solve a multi-period capacity expansion problem for a local access telecommunications network with a tree topology. This expansion is done by installing concentrators at the nodes and cables on the links of the network. The goal is to find a least cost capacity expansion strategy over a number of periods to satisfy the demand. A local search heuristic is first proposed to improve previously reported results on problem instances based on different cost and demand structures. This heuristic is then integrated into a genetic algorithm to obtain further improvements.     

An optimal capacity assignment for the robust design problem in capacitated flow networks

This paper proposes an exact algorithm to solve the robust design problem in a capacitated flow network in which each edge has several possible capacities. A capacitated flow network is popular in our daily life. For example, the computer network, the power transmission network, or even the supply chain network are capacitated flow networks. In practice, such network may suffer failure, partial failure or maintenance. Therefore, each edge in the network should be assigned sufficient capacity to keep the network functioning normally. The robust design problem (RDP) in a capacitated flow network is to search for the minimum capacity assignment of each edge such that the network still survived even under the edge’s failure. However, how to optimally assign the capacity to each edge is not an easy task. Although this kind of problem was known of NP-hard, this paper proposes an efficient exact algorithm to search for the optimal solutions for such a network and illustrates the efficiency of the proposed algorithm by numerical examples.     

A fuzzy programming approach for dynamic virtual hub location problem

Hub location problem has been used in transportation network to exploit economies of scale. For example, a controversial issue in the planning of air transportation networks is inclement weather or emergency conditions. In this situation, hub facilities would not be able to provide a good service to their spoke nodes temporarily. Thus, some other kinds of predetermined underutilized facilities in the network are used as virtual hubs to host some or all connections of original hubs to recover the incurred incapacitation and increase network flexibility and demand flow. In such an unexpected situation, it is not unreasonable to expect that some information be imprecise or vague. To deal with this issue, fuzzy concept is used to pose a more realistic problem. Here, we present a fuzzy integer liner programming approach to propose a dynamic virtual hub location problem with the aim of minimizing transportation cost in the network. We examine the effectiveness of our model using the well-known CAB data set.     

Modeling fuzzy multi-period production planning and sourcing problem with credibility service levels

A great deal of research has been done on production planning and sourcing problems, most of which concern deterministic or stochastic demand and cost situations and single period systems. In this paper, we consider a new class of multi-period production planning and sourcing problem with credibility service levels, in which a manufacturer has a number of plants and subcontractors and has to meet the product demand according to the credibility service levels set by its customers. In the proposed problem, demands and costs are uncertain and assumed to be fuzzy variables with known possibility distributions. The objective of the problem is to minimize the total expected cost, including the expected value of the sum of the inventory holding and production cost in the planning horizon. Because the proposed problem is too complex to apply conventional optimization algorithms, we suggest an approximation approach (AA) to evaluate the objective function. After that, two algorithms are designed to solve the proposed production planning problem. The first is a PSO algorithm combining the AA, and the second is a hybrid PSO algorithm integrating the AA, neural network (NN) and PSO. Finally, one numerical example is provided to compare the effectiveness of the proposed two algorithms.     

A note on fuzzy inventory model with storage space and budget constraints

In 1997, Roy and Maiti developed a fuzzy EOQ model with fuzzy budget and storage capacity constraints where demand is influenced by the unit price and the setup cost varies with the quantity purchased [T.K. Roy, M. Maiti, A fuzzy EOQ model with demand-dependent unit cost under limited storage capacity, Eur. J. Oper. Res. 99 (1997) 425–432]. However, their procedure has some questionable points and their numerical examples contain rather peculiar results. The purpose of this paper is threefold. First, for the same inventory model with fuzzy constraints, based on the max–min operator, we proposed an improved solution procedure. Second, we review the solution procedure by Roy and Maiti that is based on Kuhn–Tucker approach to point out their questionable results. Third, we compare Roy and Maiti’s approach with ours to explain why our approach can solve the problem and theirs cannot. Numerical examples provided by them also support our findings.     

A generalized bi-criteria fuzzy integer flow sharing problem

The flow sharing problem is a class of techniques that can be used to find the optimal flow in a capacitated network, which realizes an equitable distribution of flows. This paper extends the integer flow sharing problem by considering fuzzy capacities and fuzzy weights such that the flux received at each sink node and the flow value through each arc are restricted to be multiples of some block unit. Fuzzy capacity describes the flexibility of the upper limit of flow value through each arc. Fuzzy weight represents the degree of satisfaction of the flux to a sink node. Our model has the two following criteria: to maximize the minimal degree of satisfaction among all of the fuzzy capacity constraints and to maximize the minimal degree of satisfaction among the fluxes to all of the sink nodes. Because an optimal flow pattern that simultaneously maximizes the two objectives is usually not feasible, we define non-domination in this setting and propose a pseudo-polynomial algorithm that finds some non-dominated flow patterns. Finally, a numerical example is presented to demonstrate how our algorithm works.     

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.     

A note on the minimum interval cost flow problem

We reduce the problem of minimum interval cost flow problem (MICFP) introduced by Hashemi et al. (2006) to the well-known minimum cost flow problem (MCFP).     

Tabu Search for a Network Loading Problem with Multiple Facilities

This paper examines a network design problem that arises in the telecommunications industry. In this problem, communication between a gateway vertex and a number of demand vertices is achieved through a network of fiber optic cables. Since each cable has an associated capacity (bandwidth), enough capacity must be installed on the links of the network to satisfy the demand, using possibly different types of cables. Starting with a network with no capacity or some capacity already installed, a tabu search heuristic is designed to find a solution that minimizes the cost of installing any additional capacity on the network. This tabu search applies a k-shortest path algorithm to find alternative paths from the gateway to the demand vertices. Numerical results are presented on different types of networks with up to 200 vertices and 100 demand vertices.     

最佳费用流

建立赋模糊数为费用权的容量－－费用网络中，据模糊决策来求解最佳费用流的网络模型，并给出这一模型的相应算法。     

A fuzzy stochastic model for telecommunications bandwidth brokers under probabilistic QoS measures

In this paper, we model and solve profit maximization problem of a telecommunications Bandwidth Broker (BB) under uncertain market and network infrastructure conditions. The BB may lease network capacity from a set of Backbone Providers (BPs) or from other BBs in order to gain profit by leasing already purchased capacity to end-users. BB’s problem becomes harder to deal with when bandwidth requests of end-users, profit and cost margins are not known in advance. The novelty of the proposed work is the development of a mechanism via combining fuzzy and stochastic programming methodologies for solving complex BP selection and bandwidth demand allocation problem in communication networks, based on the fact that information needed for making these decisions is not available prior to leasing capacity. In addition, suggested model aims to maximize BB’s decision maker’s satisfaction ratio rather than just profit. As a solution strategy, the resulting fuzzy stochastic programming model is transformed into deterministic crisp equivalent form and then solved to optimality. Finally, the numerical experiments show that on the average, proposed approach provides 14.30% more profit and 69.50% more satisfaction ratio compared to deterministic approaches in which randomness and vagueness in the market and infrastructure are ignored.     

Network simplex algorithm for the general equal flow problem

In this paper the general equal flow problem is considered. This is a minimum cost network flow problem with additional side constraints requiring the flow of arcs in some given sets of arcs to take on the same value. This model can be applied to approach water resource system management problems or multiperiod logistic problems in general involving policy restrictions which require some arcs to carry the same amount of flow through the given study period. Although the bases of the general equal flow problem are no longer spanning trees, it is possible to recognize a similar structure that allows us to take advantage of the practical computational capabilities of network models. After characterizing the bases of the problem as good (r+1)-forests, a simplex primal algorithm is developed that exploits the network structure of the problem and requires only slight modifications of the well-known network simplex algorithm.     

A Branch and Price algorithm for the k-splittable maximum flow problem

The Maximum Flow Problem with flow width constraints is an NP-hard problem. Two models are proposed: the first model is a compact node-arc model using two flow conservation blocks per path. For each path, one block defines the path while the other one sends the right amount of flow on it. The second model is an extended arc-path model, obtained from the first model after a Dantzig–Wolfe reformulation. It is an extended model as it relies on the set of all the paths between the source and the sink nodes. Some symmetry breaking constraints are used to improve the model. A Branch and Price algorithm is proposed to solve the problem. The column generation procedure reduces to the computation of a shortest path whose cost depends on weights on the arcs and on the path capacity. A polynomial-time algorithm is proposed to solve this subproblem. Computational results are shown on a set of medium-sized instances to show the effectiveness of our approach.     

A capable neural network model for solving the maximum flow problem

This paper presents an optimization technique for solving a maximum flow problem arising in widespread applications in a variety of settings. On the basis of the Karush–Kuhn–Tucker (KKT) optimality conditions, a neural network model is constructed. The equilibrium point of the proposed neural network is then proved to be equivalent to the optimal solution of the original problem. It is also shown that the proposed neural network model is stable in the sense of Lyapunov and it is globally convergent to an exact optimal solution of the maximum flow problem. Several illustrative examples are provided to show the feasibility and the efficiency of the proposed method in this paper.     

An Efficient Approach to Real-Time Traffic Routeing for Telephone Network Management

When contingencies occur in the telephone network the proper traffic control actions for rearranging the traffic flow must be promptly taken in a short period of time, otherwise, the congestion will soon spread to other parts of the network. In this paper, a multicommodity maximal flow model is proposed to formulate the problem, and an efficient approach is proposed to find the solution within a short time period. The node pairs are first sorted by the traffic demand into decreasing order and the capacity of links is allocated to the node pair with largest demand. The traffic allocation is then iteratively reallocated on those routes which share the same links to find a better solution, until that solution is obtained. The advantages of this approach are: (1) a feasible solution can be obtained within a short time period; (2) the affected traffic can be rerouted on paths with more than two links; (3) an acceptable solution can be found once the period has expired.