A hub covering network design problem for cargo applications in Turkey

Hub location problems involve locating hub facilities and allocating demand nodes to hubs in order to provide service between origin–destination pairs. In this study, we focus on cargo applications of the hub location problem. Through observations from the Turkish cargo sector, we propose a new mathematical model for the hub location problem that relaxes the complete hub network assumption. Our model minimizes the cost of establishing hubs and hub links, while designing a network that services each origin–destination pair within a time bound. We formulate a single-allocation hub covering model that permits visiting at most three hubs on a route. The model is then applied to the realistic instances of the Turkish network and to the Civil Aeronautics Board data set.     

Network design problem with relays: A genetic algorithm with a path-based crossover and a set covering formulation

The network design problem with relays arises in telecommunications and distribution systems where the payload must be reprocessed at intermediate stations called relays on the route from its origin to its destination. In fiber-optic networks, for example, optical signals may be regenerated several times to overcome signal degradation because of attenuation and other factors. Given a network and a set of commodities, the network design problem with relays involves selecting network edges, determining a route for each commodity, and locating relays to minimize the network design cost. This paper presents a new formulation to the problem based on set covering constraints. The new formulation is used to design a genetic algorithm with a specialized crossover/mutation operator which generates a feasible path for each commodity, and the locations of relays on these paths are determined by solving the corresponding set covering problem. Computational experiments show that the proposed approach can outperform other approaches, particularly on large size problems.     

Location of hubs in a competitive environment

We offer a formulation that locates hubs on a network in a competitive environment; that is, customer capture is sought, which happens whenever the location of a new hub results in a reduction of the current cost (time, distance) needed by the traffic that goes from the specified origin to the specified destination. The formulation presented here reduces the number of variables and constraints as compared to existing covering models. This model is suited for both air passenger and cargo transportation. In this model, each origin–destination flow can go through either one or two hubs, and each demand point can be assigned to more than a hub, depending on the different destinations of its traffic. Links (“spokes”) have no capacity limit. Computational experience is provided.     

Improved rounding procedures for the discrete version of the capacitated EOQ problem

We consider a transportation problem where different products have to be shipped from an origin to a destination by means of vehicles with given capacity. The production rate at the origin and the demand rate at the destination are constant over time and identical for each product. The problem consists in deciding when to make the shipments and how to fill the vehicles, with the objective of minimizing the sum of the average transportation and inventory costs at the origin and at the destination over an infinite horizon. This problem is the well known capacitated EOQ (economic order quantity) problem and has an optimal solution in closed form. In this paper we study a discrete version of this problem in which shipments are performed only at multiples of a given minimum time. It is known that rounding-off the optimal solution of the capacitated EOQ problem to the closest lower or upper integer value gives a tight worst-case ratio of 2, while the best among the possible single frequency policies has a performance ratio of 5/3. We show that the 5/3 bound can be obtained by a single frequency policy based on a rounding procedure which considers classes of instances and, for each class, identifies a shipping frequency by rounding-off in a different way the optimal solution of the capacitated EOQ problem. Moreover, we show that the bound can be reduced to 3/2 by using two shipping frequencies, obtained by a rounding procedure, in one class of instances only.     

New formulation and relaxation to solve a concave-cost network flow problem

In this paper we study a minimum cost, multicommodity network flow problem in which the total cost is piecewise linear, concave of the total flow along the arcs. Specifically, the problem can be defined as follows. Given a directed network, a set of pairs of communicating nodes and a set of available capacity ranges and their corresponding variable and fixed cost components for each arc, the problem is to select for each arc a range and identify a path for each commodity between its source and destination nodes so as to minimize the total costs. We also extend the problem to the case of piecewise nonlinear, concave cost function. New mathematical programming formulations of the problems are presented. Efficient solution procedures based on Lagrangean relaxations of the problems are developed. Extensive computational results across a variety of networks are reported. These results indicate that the solution procedures are effective for a wide range of traffic loads and different cost structures. They also show that this work represents an improvement over previous work made by other authors. This improvement is the result of the introduction of the new formulations of the problems and their relaxations.     

A packet filter placement problem with application to defense against spoofed denial of service attacks

We analyze a problem in computer network security, wherein packet filters are deployed to defend a network against spoofed denial of service attacks. Information on the Internet is transmitted by the exchange of IP packets, which must declare their origin and destination addresses. A route-based packet filter verifies whether the purported origin of a packet is correct with respect to the current route map. We examine the optimization problem of finding a minimum cardinality set of nodes to filter in the network such that no spoofed packet can reach its destination. We prove that this problem is NP-hard, and derive properties that explicitly relate the filter placement problem to the vertex cover problem. We identify topologies and routing policies for which a polynomial-time solution to the minimum filter placement problem exists, and prove that under certain routing conditions a greedy heuristic for the filter placement problem yields an optimal solution.     

Infinite paths in a Lorentz lattice gas model

We consider infinite paths in an illumination problem on the lattice ℤ², where at each vertex, there is either a two-sided mirror (with probability p≥ 0) or no mirror (with probability 1 −p). The mirrors are independently oriented NE-SW or NW-SE with equal probability. We consider beams of light which are shone from the origin and deflected by the mirrors. The beam of light is either periodic or unbounded. The novel feature of this analysis is that we concentrate on the measure on the space of paths. In particular, under the assumption that the set of unbounded paths has positive measure, we are able to establish a useful ergodic property of the measure. We use this to prove results about the number and geometry of infinite light beams. Extensions to higher dimensions are considered. Received: 14 November 1996 / Revised version: 1 September 1998     

Network hub location problems: The state of the art

Hubs are special facilities that serve as switching, transshipment and sorting points in many-to-many distribution systems. The hub location problem is concerned with locating hub facilities and allocating demand nodes to hubs in order to route the traffic between origin–destination pairs. In this paper we classify and survey network hub location models. We also include some recent trends on hub location and provide a synthesis of the literature.     

Cutting plane algorithms for solving a stochastic edge-partition problem

We consider the edge-partition problem, which is a graph theoretic problem arising in the design of Synchronous Optical Networks. The deterministic edge-partition problem considers an undirected graph with weighted edges, and simultaneously assigns nodes and edges to subgraphs such that each edge appears in exactly one subgraph, and such that no edge is assigned to a subgraph unless both of its incident nodes are also assigned to that subgraph. Additionally, there are limitations on the number of nodes and on the sum of edge weights that can be assigned to each subgraph. In this paper, we consider a stochastic version of the edge-partition problem in which we assign nodes to subgraphs in a first stage, realize a set of edge weights from a finite set of alternatives, and then assign edges to subgraphs. We first prescribe a two-stage cutting plane approach with integer variables in both stages, and examine computational difficulties associated with the proposed cutting planes. As an alternative, we prescribe a hybrid integer programming/constraint programming algorithm capable of solving a suite of test instances within practical computational limits.     

Algorithms for the non-bifurcated network design problem

In this paper we consider the non-bifurcated network design problem where a given set of cities must be connected by installing on a given set of links integer multiples of some base capacity so that a set of commodity demands can be routed. Each commodity flow is constrained to run through a single path along the network. The objective is to minimize the sum of capacity installation and routing costs. We present an exact algorithm and four new heuristics. The first heuristic generates an initial feasible solution, then it improves it until a necessary condition for optimality is satisfied. Two heuristics are partial enumeration methods and the last one iteratively applies a tabu search method to different initial feasible solutions. Computational results over a set of test problems from the literature show the effectiveness of the proposed algorithms.     

Branch-and-price-and-cut algorithms for solving the reliable <Emphasis Type="Italic">h</Emphasis>-paths problem

We examine a routing problem in which network arcs fail according to independent failure probabilities. The reliable h-path routing problem seeks to find a minimum-cost set of h ≥ 2 arc-independent paths from a common origin to a common destination, such that the probability that at least one path remains operational is sufficiently large. For the formulation in which variables are used to represent the amount of flow on each arc, the reliability constraint induces a nonconvex feasible region, even when the integer variable restrictions are relaxed. Prior arc-based models and algorithms tailored for the case in which h = 2 do not extend well to the general h-path problem. Thus, we propose two alternative integer programming formulations for the h-path problem in which the variables correspond to origin-destination paths. Accordingly, we develop two branch-and-price-and-cut algorithms for solving these new formulations, and provide computational results to demonstrate the efficiency of these algorithms.     

Dynamic journeying under uncertainty

We introduce a journey planning problem in multi-modal transportation networks under uncertainty. The goal is to find a journey, possibly involving transfers between different transport services, from a given origin to a given destination within a specified time horizon. Due to uncertainty in travel times, the arrival times of transport services at public transport stops are modeled as random variables. If a transfer between two services is rendered unsuccessful, the commuter has to reconsider the remaining path to the destination. The problem is modeled as a Markov decision process in which states are defined as paths in the transport network. The main contribution is a backward induction method that generates an optimal policy for traversing the public transport network in terms of maximizing the probability of reaching the destination in time. By assuming history independence and independence of successful transfers between services we obtain approximate methods for the same problem. Analysis and numerical experiments suggest that while solving the path dependent model requires the enumeration of all paths from the origin to the destination, the proposed approximations may be useful for practical purposes due to their computational simplicity. In addition to on-time arrival probability, we show how travel and overdue costs can be taken into account, making the model applicable to freight transportation problems.     

On finding dissimilar Pareto-optimal paths

The aim of the present paper is to provide a methodology for finding a set of alternative paths between an origin and a destination site on which routing one or a set of dangerous goods. Finding a set of paths allows one to equally distribute the total risk among the population exposed. The concept of equity of risk is here related to the concept of determining spatially dissimilar paths. We divide our approach into two phases. In the first phase we find a set of Pareto-Optimal paths between an origin and a destination, by implementing a multicriteria shortest path algorithm. In the second one, for each path previously found, and by using a geographical information system, we construct a Buffer Zone approximating the impact area of a material being released after an accident. Based on these Buffer Zones, a dissimilarity index between every pair of paths can be derived in order to find the most spatially different routes. We then compare our method with an iterative penalty method and discuss computational results based both on a real application and on test problems.     

An ant colony optimization metaheuristic for single-path multicommodity network flow problems

This paper studies the single-path multicommodity network flow problem (SMNF), inwhich the flow of each commodity can only use one path linking its origin anddestination in the network. We study two versions of this problem based on twodifferent objectives. The first version is to minimize network congestion, anissue of concern in traffic grooming over wavelength division multiplexing(WDM), and in which there generally exists a commodity flow between every pairof nodes. The second problem is a constrained version of the general linearmulticommodity flow problem, in which, for each commodity, a single path isallowed to send the required flow, and the objective is to determine a flowpattern that obeys the arc capacities and minimizes the total shipping cost.Based on the node-arc and the arc-chain representations, we first present twoformulations. Owing to computational impracticality of exact algorithms forpractical networks, we propose an ant colony optimization-(ACO) basedmetaheuristic to deal with SMNF. Considering different problem properties, wedevise two versions of ACO metaheuristics to solve these two problems,respectively. The proposed algorithms’ efficiencies are experimentallyinvestigated on some generated instances of SMNF. The test results demonstratethat the proposed ACO metaheuristics are computationally efficient and robustapproaches for solving SMNF.     

Robust solutions for network design under transportation cost and demand uncertainty

In many applications, the network design problem (NDP) faces significant uncertainty in transportation costs and demand, as it can be difficult to estimate current (and future values) of these quantities. In this paper, we present a robust optimization-based formulation for the NDP under transportation cost and demand uncertainty. We show that solving an approximation to this robust formulation of the NDP can be done efficiently for a network with single origin and destination per commodity and general uncertainty in transportation costs and demand that are independent of each other. For a network with path constraints, we propose an efficient column generation procedure to solve the linear programming relaxation. We also present computational results that show that the approximate robust solution found provides significant savings in the worst case while incurring only minor sub-optimality for specific instances of the uncertainty.     

The traveling purchaser problem with stochastic prices: Exact and approximate algorithms

The paper formulates an extension of the traveling purchaser problem where multiple types of commodities are sold at spatially distributed locations with stochastic prices (each following a known probability distribution). A purchaser’s goal is to find the optimal routing and purchasing strategies that minimize the expected total travel and purchasing costs needed to purchase one unit of each commodity. The purchaser reveals the actual commodity price at a seller upon arrival, and then either purchases the commodity at the offered price, or rejects the price and visits a next seller. In this paper, we propose an exact solution algorithm based on dynamic programming, an iterative approximate algorithm that yields bounds for the minimum total expected cost, and a greedy heuristic for fast solutions to large-scale applications. We analyze the characteristics of the problem and test the computational performance of the proposed algorithms. The numerical results show that the approximate and heuristic algorithms yield near-optimum strategies and very good estimates of the minimum total cost.     

Bilateral representation of trade for inter- regional models

A representation of trade is given for an inter-regional model in which the origin and destination of exports and imports of each commodity traded can be tracked. This representation retains the structure of the original model (i.e. one with trade ‘pools’ undifferentiated by origin or destination) in that the same algebraic and computational tools can be used, with minor modifications. Scenarios that can be studied with this formulation but not with the original one are presented.     

Solving a new stochastic multi-mode p-hub covering location problem considering risk by a novel multi-objective algorithm

In this paper, we develop a novel stochastic multi-objective multi-mode transportation model for hub covering location problem under uncertainty. The transportation time between each pair of nodes is an uncertain parameter and also is influenced by a risk factor in the network. We extend the traditional comprehensive hub location problem by considering two new objective functions. So, our multi-objective model includes (i) minimization of total current investment costs and (ii) minimization of maximum transportation time between each origin–destination pair in the network. Besides, a novel multi-objective imperialist competitive algorithm (MOICA) is proposed to obtain the Pareto-optimal solutions of the problem. The performance of the proposed solution algorithm is compared with two well-known meta-heuristics, namely, non-dominated sorting genetic algorithm (NSGA-II) and Pareto archive evolution strategy (PAES). Computational results show that MOICA outperforms the other meta-heuristics.     

A distribution map for the one-median location problem on a network

In this paper we consider the Weber (one-median) location problem on a network. The weights at the nodes are drawn from a multivariate normal distribution. We find the probability that the optimal location is at each of the nodes. This set of probabilities is the distribution map. The methodology is illustrated on two networks of 20 nodes each.     

A probabilistic approach to modelling uncertain logical arguments

Argumentation can be modelled at an abstract level using a directed graph where each node denotes an argument and each arc denotes an attack by one argument on another. Since arguments are often uncertain, it can be useful to quantify the uncertainty associated with each argument. Recently, there have been proposals to extend abstract argumentation to take this uncertainty into account. This assigns a probability value for each argument that represents the degree to which the argument is believed to hold, and this is then used to generate a probability distribution over the full subgraphs of the argument graph, which in turn can be used to determine the probability that a set of arguments is admissible or an extension. In order to more fully understand uncertainty in argumentation, in this paper, we extend this idea by considering logic-based argumentation with uncertain arguments. This is based on a probability distribution over models of the language, which can then be used to give a probability distribution over arguments that are constructed using classical logic. We show how this formalization of uncertainty of logical arguments relates to uncertainty of abstract arguments, and we consider a number of interesting classes of probability assignments.