Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Self-Organizing Extreme-Point Tabu-Search Algorithm for Fixed Charge Network Problems with Extensions
100
0
0.0
(
0
)
Added by
Richard Barr
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Richard S. Barr
Ask ChatGPT about the research
No Arabic abstract
We propose a new self-organizing algorithm for fixed-charge network flow problems based on ghost image (GI) processes as proposed in Glover (1994) and adapted to fixed-charge transportation problems in Glover, Amini and Kochenberger (2005). Our self-organizing GI algorithm iteratively modifies an idealized representation of the problem embodied in a parametric ghost image, enabling all steps to be performed with a primal network flow algorithm operating on the parametric GI. Computational tests are carried out on an extensive set of benchmark problems which includes the previous largest set in the literature, comparing our algorithm to the best methods previously proposed for fixed-charge transportation problems, though our algorithm is not specialized to this class. We also provide comparisons for additional more general fixed-charge network flow problems against Cplex 12.8 to demonstrate that the new self-organizing GI algorithm is effective on large problem instances, finding solutions with statistically equivalent objective values at least 700 times faster. The attractive outcomes produced by the current GI/TS implementation provide a significant advance in our ability to solve fixed-cost network problems efficiently and invites its use for larger instances from a variety of application domains.
rate research
Read More
We present the `Basic S* algorithm for computing shortest path through a metric simplicial complex. In particular, given a metric graph, $G$, which is constructed as a discrete representation of an underlying configuration space (a larger continuous space/manifold typically of dimension greater than one), we consider the Rips complex, $mathcal{R}(G)$, associated with it. Such a complex, and hence shortest paths in it, represent the underlying metric space more closely than what the graph does. While discrete graph representations of continuous spaces is convenient for motion planning in configuration spaces of robotic systems, the metric induced in them by the ambient configuration space is significantly different from the metric of the configuration space itself. We remedy this problem using the simplicial complex representation. Our algorithm requires only an abstract graph, $G=(V,E)$, and a cost/length function, $d:Erightarrow mathbb{R}_+$, as inputs, and no global information such as an embedding or a global coordinate chart is required. The complexity of the Basic S* algorithm is comparable to that of Dijkstras search, but, as the results presented in this paper demonstrate, the shortest paths obtained using the proposed algorithm represent/approximate the geodesic paths in the original metric space significantly more closely.
Transportation networks frequently employ hub-and-spoke network architectures to route flows between many origin and destination pairs. Hub facilities work as switching points for flows in large networks. In this study, we deal with a problem, called the single allocation hub-and-spoke network design problem. In the problem, the goal is to allocate each non-hub node to exactly one of given hub nodes so as to minimize the total transportation cost. The problem is essentially equivalent to another combinatorial optimization problem, called the metric labeling problem. The metric labeling problem was first introduced by Kleinberg and Tardos in 2002, motivated by application to segmentation problems in computer vision and related areas. In this study, we deal with the case where the set of hubs forms a star, which arises especially in telecommunication networks. We propose a polynomial-time randomized approximation algorithm for the problem, whose approximation ratio is less than 5.281. Our algorithms solve a linear relaxation problem and apply dependent rounding procedures.
This paper introduces a multi-period inspector scheduling problem (MPISP), which is a new variant of the multi-trip vehicle routing problem with time windows (VRPTW). In the MPISP, each inspector is scheduled to perform a route in a given multi-period planning horizon. At the end of each period, each inspector is not required to return to the depot but has to stay at one of the vertices for recuperation. If the remaining time of the current period is insufficient for an inspector to travel from his/her current vertex $A$ to a certain vertex B, he/she can choose either waiting at vertex A until the start of the next period or traveling to a vertex C that is closer to vertex B. Therefore, the shortest transit time between any vertex pair is affected by the length of the period and the departure time. We first describe an approach of computing the shortest transit time between any pair of vertices with an arbitrary departure time. To solve the MPISP, we then propose several local search operators adapted from classical operators for the VRPTW and integrate them into a tabu search framework. In addition, we present a constrained knapsack model that is able to produce an upper bound for the problem. Finally, we evaluate the effectiveness of our algorithm with extensive experiments based on a set of test instances. Our computational results indicate that our approach generates high-quality solutions.
Quantum Computing is considered as the next frontier in computing, and it is attracting a lot of attention from the current scientific community. This kind of computation provides to researchers with a revolutionary paradigm for addressing complex optimization problems, offering a significant speed advantage and an efficient search ability. Anyway, Quantum Computing is still in an incipient stage of development. For this reason, present architectures show certain limitations, which have motivated the carrying out of this paper. In this paper, we introduce a novel solving scheme coined as hybrid Quantum Computing - Tabu Search Algorithm. Main pillars of operation of the proposed method are a greater control over the access to quantum resources, and a considerable reduction of non-profitable accesses. To assess the quality of our method, we have used 7 different Traveling Salesman Problem instances as benchmarking set. The obtained outcomes support the preliminary conclusion that our algorithm is an approach which offers promising results for solving partitioning problems while it drastically reduces the access to quantum computing resources. We also contribute to the field of Transfer Optimization by developing an evolutionary multiform multitasking algorithm as initialization method.
We propose an artificial life framework aimed at facilitating the emergence of intelligent organisms. In this framework there is no explicit notion of an agent: instead there is an environment made of atomic elements. These elements contain neural operations and interact through exchanges of information and through physics-like rules contained in the environment. We discuss how an evolutionary process can lead to the emergence of different organisms made of many such atomic elements which can coexist and thrive in the environment. We discuss how this forms the basis of a general AI generating algorithm. We provide a simplified implementation of such system and discuss what advances need to be made to scale it up further.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
