Multistate components assignment problem with optimal network reliability subject to assignment budget

The typical assignment problem for finding the optimal assignment of a set of components to a set of locations in a system has been widely studied in practical applications. However, this problem mainly focuses on maximizing the total profit or minimizing the total cost without considering component’s failure. In practice, each component should be multistate due to failure, partially failure, or maintenance. That is, each component has several capacities with a probability distribution and may fail. When a set of multistate components is assigned to a system, the system can be treated as a stochastic-flow network. The network reliability is the probability that d units of homogenous commodity can be transmitted through the network successfully. The multistate components assignment problem to maximize the network reliability is never discussed. Therefore, this paper focuses on solving this problem under an assignment budget constraint, in which each component has an assignment cost. The network reliability under a components assignment can be evaluated in terms of minimal paths and state-space decomposition. Subsequently an optimization method based on genetic algorithm is proposed. The experimental results show that the proposed algorithm can be executed in a reasonable time.     

Time version of the shortest path problem in a stochastic-flow network

Many studies on hardware framework and routing policy are devoted to reducing the transmission time for a flow network. A time version of the shortest path problem thus arises to find a quickest path, which sends a given amount of data from the unique source to the unique sink with minimum transmission time. More specifically, the capacity of each arc in the flow network is assumed to be deterministic. However, in many real-life networks, such as computer systems, telecommunication systems, etc., the capacity of each arc should be stochastic due to failure, maintenance, etc. Such a network is named a stochastic-flow network. Hence, the minimum transmission time is not a fixed number. We extend the quickest path problem to evaluating the probability that d$d$ units of data can be sent under the time constraint T$T$. Such a probability is named the system reliability. In particular, the data are transmitted through two minimal paths simultaneously in order to reduce the transmission time. A simple algorithm is proposed to generate all (d,T)$(d,T)$-MPs and the system reliability can then be computed in terms of (d,T)$(d,T)$-MPs. Moreover, the optimal pair of minimal paths with highest system reliability could be obtained.     

基于部件指派的多状态系统可靠度优化研究

针对一般二态系统假设的不足,提出了多状态系统条件下的可靠度优化指派问题。该问题以系统可靠度最大化为优化目标,在考虑部件分配成本和总分派成本预算的前提下,对多状态系统下不同状态对应的性能水平的进行了分析,给出了基于通用生成函数的多状态系统的可靠度评估方法。根据指派问题的组合优化的特性和多状态系统可靠性评估的特点,对传统遗传算法的适应度函数进行了改进,设计了基于整数编码的遗传算法,该算法具有离散变量的设计灵活性和强大的搜索性能。算例实验表明,本文设计的优化算法具有较好的求解质量,同时算法的运行时间也得到了大幅的缩短。本研究为多状态系统的可靠度优化提供了一条可借鉴的思路。     

The alternating basis algorithm for assignment problems

The purpose of this paper is to present a new primal extreme point algorithm for solving assignment problems which both circumvents and exploits degeneracy. The algorithm is based on the observation that the degeneracy difficulties of the simplex method result from the unnecessary inspection of alternative basis representations of the extreme points. This paper characterizes a subsetQ of all bases that are capable of leading to an optimal solution to the problem if one exists. Using this characterization, an extreme point algorithm is developed which considers only those bases inQ. Computational results disclose that the new algorithm is substantially more efficient than previously developed primal and primal-dual extreme point (simplex) methods for assignment problems.     

The daily tail assignment problem under operational uncertainty using look-ahead maintenance constraints

The tail assignment problem is a critical part of the airline planning process that assigns specific aircraft to sequences of flights, called lines-of-flight, to satisfy operational constraints. The aim of this paper is to develop an operationally flexible method, based upon the one-day routes business model, to compute tail assignments that satisfy short-range—within the next three days—aircraft maintenance requirements. While maintenance plans commonly span multiple days, the methods used to compute tail assignments for the given plans can be overly complex and provide little recourse in the event of schedule perturbations. The presented approach addresses operational uncertainty by using solutions from the one-day routes aircraft maintenance routing approach as input. The daily tail assignment problem is solved with an objective to satisfy maintenance requirements explicitly for the current day and implicitly for the subsequent two days. A computational study will be performed to assess the performance of exact and heuristic solution algorithms that modify the input lines-of-flight to reduce maintenance misalignments. The daily tail assignment problem and the developed algorithms are demonstrated to compute solutions that effectively satisfy maintenance requirements when evaluated using input data collected from three different airlines.     

Hybrid meta-heuristic algorithms for solving network design problem

Network design problem has been, and is, an important problem in transportation. Following an earlier effort in designing a meta-heuristic search technique by an ant system, this paper attempts to hybridize this concept with other meta-heuristic concepts such as genetic algorithm, simulated annealing, and tabu search. Seven hybrids have been devised and tested on the network of Sioux Falls. It has been observed that the hybrids are more effective to solve the network design problem than the base ant system. Application of the hybrid containing all four concepts on a real network of a city with over 2 million population has also proved to be more effective than the base network, in the sense of finding better solutions sooner.     

Discrete-time dynamic traffic assignment models with periodic planning horizon: system optimum

This paper proposes a system optimal dynamic traffic assignment model that does not require the network to be empty at the beginning or at the end of the planning horizon. The model assumes that link travel times depend on traffic densities and uses a discretized planning horizon. The resulting formulation is a nonlinear program with binary variables and a time-expanded network structure. Under a relatively mild condition, the nonlinear program has a feasible solution. When necessary, constraints can be added to ensure that the solution satisfies the First-In-First-Out condition. Also included are approximation schemes based on linear integer programs that can provide solutions arbitrarily close to that of the original nonlinear problem.     

Doubly uncertain transportation network: Degradable capacity and stochastic demand

This study developed a methodology to model doubly uncertain transportation network with stochastic link capacity degradation and stochastic demand. We consider that the total travel demand comprises of two parts, infrequent travelers and commuters. The traffic volume of infrequent travelers is stochastic, which adds to the network traffic in a random manner based on fixed route choice proportions. On the other hand, the traffic volume of commuters is stable or deterministic. Commuters acquire the network travel time variability from past experiences, factor them into their route choice considerations, and settle into a long-term habitual route choice equilibrium in which they have no incentive of switching away. To define this equilibrium, we introduce the notion of “travel time budget” to relate commuters’ risk aversion on route choices in the presence of travel time variability. The travel time budget varies among commuters according to their degrees of risk aversion and requirements on punctual arrivals. We then developed a mixed-equilibrium formulation to capture these stochastic considerations and illustrated its properties through some numerical studies.     

Bees algorithm for generalized assignment problem

Bees algorithm (BA) is a new member of meta-heuristics. BA tries to model natural behavior of honey bees in food foraging. Honey bees use several mechanisms like waggle dance to optimally locate food sources and to search new ones. This makes them a good candidate for developing new algorithms for solving optimization problems. In this paper a brief review of BA is first given, afterwards development of a BA for solving generalized assignment problems (GAP) with an ejection chain neighborhood mechanism is presented. GAP is a NP-hard problem. Many meta-heuristic algorithms were proposed for its solution. So far BA is generally applied to continuous optimization. In order to investigate the performance of BA on a complex integer optimization problem, an attempt is made in this paper. An extensive computational study is carried out and the results are compared with several algorithms from the literature.     

A forward/reverse auction algorithm for asymmetric assignment problems

In this paper we consider the asymmetric assignment problem and we propose a new auction algorithm for its solution. The algorithm uses in a novel way the recently proposed idea of reverse auction, where, in addition to persons bidding for objects by raising their prices, we also have objects competing for persons by essentially offering discounts. In practice, the new algorithm apparently deals better with price wars than the currently existing auction algorithms. As a result, it tends to terminate substantially (and often dramatically) faster than its competitors.     

考虑运营稳定性的内支线班轮航线网络规划模型

货主选择承运航线的影响因素,既包括挂靠港口的计划到港时间与单箱运价,还包括反映班轮运营稳定性的甩箱率与准班率。对此,文章将挂靠港口的航行与在港时间不确定引入研究,并对挂靠港口间的不确定性建立联系,基于航次仿真来计算各挂靠港的到港时间分布、船舶的航次最大载箱量分布。以班轮航线的甩箱率与准班率限制、内支线最大船型与最长往返时间为约束,在优化内支线航线网络结构的同时,计算航线适配船型、班期密度及挂靠港计划到港时间。针对所构建的带不确定参数的NP难问题,文章设计了基于模拟仿真的智能优化算法,通过方案仿真技术来处理输入模型的众分布函数,借助智能优化原理从大范围解空间内寻找满意方案。文末对船舶航次仿真与网络规划模型的有效性进行了验证,算例分析表明:内支线班轮航线网络的货主选择比例达64%,且不论货主更偏好运输时间或价格,航线方案皆能贴近货主偏好。     

Closest assignment constraints in discrete location problems

The objective of this paper is to identify the most promising sets of closest assignment constraints in the literature of Discrete Location Theory, helping the authors in the field to model their problems when clients must be assigned to the closest plant inside an Integer Programming formulation. In particular, constraints leading to weak Linear Programming relaxations should be avoided if no other good property supports their use. We also propose a new set of constraints with good theoretical properties.     

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.     

Optimal double-resource assignment for the robust design problem in multistate computer networks

This paper proposes a novel approach to get the exact optimal double-resource assignment for the robust design problem in multistate computer networks. A multistate computer network consists of links and vertices where both kinds of resources may have several states due to failure, partial failure or maintenance. Therefore, each link (vertex) in the network should be assigned sufficient capacity to keep the network functioning normally. The robust design problem (RDP) in a multistate computer network (MCN) is to search for the minimum capacity assignment of each link and vertex such that the network still survived even under both kinds of failures. However, how to optimally assign the capacity to each resource is not an easy task. This paper proposes an efficient approach to do such assignment and illustrates the efficiency of the proposed approach by some numerical examples.     

Constraint Generation for Network Reliability Problems

This paper presents a constraint generation approach to the network reliability problem of adding spare capacity at minimum cost that allows the traffic on a failed link to be rerouted to its destination. Any number of non-simultaneous link failures can be part of the requirements on the spare capacity. The key result is a necessary and sufficient condition for a multicommodity flow to exist, which is derived in the appendix. Computational results on large numbers of random networks are presented.     

An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors

Given a complete k-partite graph G=(V₁,V₂,…,V_k;E) satisfying |V₁|=|V₂|=?=|V_k|=n and weights of all  k-cliques of G, the  k-dimensional assignment problem finds a partition of vertices of G into a set of (pairwise disjoint) n k-cliques that minimizes the sum total of weights of the chosen cliques. In this paper, we consider a case in which the weight of a clique is defined by the sum of given weights of edges induced by the clique. Additionally, we assume that vertices of G are embedded in the d-dimensional space Q^d and a weight of an edge is defined by the square of the Euclidean distance between its two endpoints. We describe that these problem instances arise from a multidimensional Gaussian model of a data-association problem.We propose a second-order cone programming relaxation of the problem and a polynomial time randomized rounding procedure. We show that the expected objective value obtained by our algorithm is bounded by (5/2−3/k) times the optimal value. Our result improves the previously known bound (4−6/k) of the approximation ratio.     

Simulating vehicular traffic in a network using dynamic routing

We present a new numerical code which solves the Lighthill – Whitham model, the classic macroscopic model for vehicular traffic flow, in a network with multi-destinations. We use a high-resolution shock-capturing scheme with approximate Riemann solver to solve the partial differential equations of the Lighthill – Whitham theory. These schemes are very efficient, robust and moreover well adapted to simulations of traffic flows. We develop a theory of dynamic routing including a procedure for traffic flow assignment at junctions which reproduces the correct propagation of irregularities and ensures at the same time conservation of the number of vehicles.     

A logistics problem: a non-markovian queueing network model and algorithm

In this paper, a stochastic version of the classical deterministic balanced single commodity capacitated transportation network problem is presented. In this model, each arc of the network connects a supply node to a demand node and the flow of units forming along each arc of the network forms a stochastic process (i.e.G/M/1 queueing system with generally distributed interarrival time, a Markovian server, a single server, infinite capacity, and the first come first served queueing discipline). In this model, the total transportation cost is minimized such that the total supply rate is equal to the total demand rate, and the resulting probability of finding excessive congestion along each arc (i.e., the resulting probability of finding congestion inside the queueing system formed along each arc in excess of a fixed number) is equal to a desirable value     

A new bound for the quadratic assignment problem based on convex quadratic programming

We describe a new convex quadratic programming bound for the quadratic assignment problem (QAP). The construction of the bound uses a semidefinite programming representation of a basic eigenvalue bound for QAP. The new bound dominates the well-known projected eigenvalue bound, and appears to be competitive with existing bounds in the trade-off between bound quality and computational effort. Received: February 2000 / Accepted: November 2000?Published online January 17, 2001