Search

In this paper, we study the visualization of complex structures in the context of automatic graph drawing. Constructing geometric representations of combinatorial structures, such as networks or graphs, is a difficult task that requires an expert system. The automatic generation of drawings of graphs finds many applications from software engineering to social media. The objective of graph drawing expert systems is to generate layouts that are easy to read and understand. This main objective is achieved by solving several optimization problems. In this paper we focus on the most important one: reducing the number of arc crossings in the graph. This hard optimization problem has been studied extensively in the last decade, proposing many exact and heuristic methods to minimize the total number of arc crossings. However, despite its practical significance, the min–max variant in which the maximum number of crossings over all edges is minimized, has received very little attention. We propose new heuristic methods based on the strategic oscillation methodology to solve this NP-hard optimization problem. Our experimentation shows that the new method compares favorably with the existing ones, implemented in current graph drawing expert systems. Therefore, a direct application of our findings will improve these functionality (i.e., crossing reduction) of drawing systems.

In this paper, a districting problem with stochastic demands is investigated. The goal is to divide a geographic area into p contiguous districts such that, with some given probability, the districts are balanced with respect to some given lower and upper thresholds. The problem is cast as a p -median problem with contiguity constraints that is further enhanced with chance-constrained balancing requirements. The total assignment cost of the territorial units to the representatives of the corresponding districts is used as a surrogate compactness measure to be optimized. Due to the tantalizing purpose of deriving a deterministic equivalent for the problem, a two-phase heuristic is developed. In the first phase, the chance-constraints are ignored and a feasible solution is constructed for the relaxed problem; in the second phase, the solution is corrected if it does not meet the chance-constraints. In this case, a simulation procedure is proposed for estimating the probability of a given solution to yield a balanced districting. That procedure also provides information for guiding the changes to make in the solution. The results of a series of computational tests performed are discussed based upon a set of testbed instances randomly generated. Different families of probability distributions for the demands are also investigated, namely: Uniform, Log-normal, Exponential, and Poisson.

In this paper we study the hub location problem, where the goal is to identify an optimal subset of facilities (hubs) to minimize the transportation cost while satisfying certain capacity constraints. In particular, we target the single assignment version, in which each node in the transportation network is assigned to only one hub to route its traffic. We consider here a realistic variant introduced previously, in which the capacity of edges between hubs is increased in a modular way. This reflects the practical situation in air traffic where the number of flights between two locations implies a capacity in terms of number of passengers. Then, the capacity can be increased in a modular way, as a factor of the number of flights. We propose heuristic methods to obtain high-quality solutions in short computing times. Specifically, we implement memory structures to create advanced search methods and compare them with previous heuristics on a set of benchmark instances. Memory structures have been widely implemented in the context of the tabu search methodology, usually embedded in local search algorithms. In this paper we explore an alternative design in which the constructive method is enhanced with frequency information and the local search is coupled with a path relinking post-processing. Statistical tests confirm the superiority of our proposal with respect to previous developments.

Hub networks are commonly used in telecommunications and logistics to connect origins to destinations in situations where a direct connection between each origin–destination (o-d) pair is impractical or too costly. Hubs serve as switching points to consolidate and route traffic in order to realize economies of scale. The main decisions associated with hub-network problems include (1) determining the number of hubs (p), (2) selecting the p-nodes in the network that will serve as hubs, (3) allocating non-hub nodes (terminals) to up to r-hubs, and (4) routing the pairwise o-d traffic. Typically, hub location problems include all four decisions while hub allocation problems assume that the value of p is given. In the hub median problem, the objective is to minimize total cost, while in the hub center problem the objective is to minimize the maximum cost between origin–destination pairs. We study the uncapacitated (i.e., links with unlimited capacity) r-allocation p-hub equitable center problem (with1

The capacitated single assignment hub location problem with modular link capacities is a variant of the classical hub location problem in which the cost of using edges is not linear but stepwise, and the hubs are restricted in terms of transit capacity rather than in the incoming traffic. We propose a metaheuristic algorithm based on strategic oscillation, a methodology originally introduced in the context of tabu search. Our method incorporates several designs for constructive and destructive algorithms, together with associated local search procedures, to balance diversification and intensification for an efficient search. Computational results on a large set of instances show that, in contrast to exact methods that can only solve small instances optimally, our metaheuristic is able to find high-quality solutions on larger instances in short computing times. In addition, the new method, which joins tabu search strategies with strategic oscillation, outperforms the previous tabu search implementation.

This paper explores the concept of capacity transfer in the context of capacitated facility location problems. This is accomplished by assuming that facilities with surplus capacity/production can cooperate with those facing shortage by transferring part of that capacity/production. Such a transfer incurs a cost that nonetheless may be compensated by savings both in the installation costs and in the distribution costs. Mixed-integer mathematical programming models are proposed for the problem. A distinction is made between the case in which the triangle inequality holds for the transfer costs and the case in which it does not. We present compact models, which are enhanced with valid inequalities that are separated in a branch-and-cut fashion. A comprehensive computational study with several hundreds of instances is reported showing the value of transferring capacities. Overall, this work investigates a problem that is at the core of more comprehensive models emerging in the context of logistics network design.