Solving the two-dimensional findpath problem using a line-triangle representation of the robot

We have developed a new approach to computing the collision boundary of a collection of obstacles grown by a convex robot. The essential idea of this approach involves first representing the robot as a set sum of line segments and triangles. The process of growing the obstacles by the robot can then be viewed as a sequence of steps where each step involves growing the partial grown collection of obstacles by a line segment or a triangle. A fast algorithm has been presented to solve this problem.     

Control of the optimum synthesis process of a four-bar linkage whose point on the working member generates the given path

This paper presents the optimum synthesis of a four-bar linkage in which the coupler point performs a path composed of rectilinear segments and a circular arc. The Grashof four-bar linkage whose geometry provides minimum deviations from the given problem for certain parts of the crank cycle is chosen. The motion of the coupler point of the four-bar linkage is controlled within the given values of allowed deviations so that it is always in the prescribed environment of the given point on the observed segment. The synthesis process tends to bring only those path segments that are beyond the boundaries within the prescribed boundary deviations. During the synthesis, allowed deviations change from the initial maximum values to the given minimum ones. Groups of mechanisms realising satisfactory approximation to the desired motion can be obtained by the method of controlled decrease of allowed deviations with the application of the Differential Evolution (DE) algorithm.     

Upper and lower bounding procedures for the minimum caterpillar spanning problem

A spanning caterpillar in a graph is a tree composed by a path such that all vertices not in the path are leaves. In the Minimum Spanning Caterpillar Problem (MSCP) each edge has two costs: a path cost when it belongs to the path and a connection cost when it is incident to a leaf. The goal is to find a spanning caterpillar minimizing the sum of all path and connection costs. In this paper we formulate the as a minimum Steiner arborescence problem. This reduction is the basis for the development of an efficient branch-and-cut algorithm for the MSCP. We als developed a GRASP heuristic to generate primal bounds. Experiments carried out on instances adapted from TSPLIB 2.1 revealed that the exact algorithm is capable to solve to optimality instances with up to 300 vertices in reasonable time. They also showed that our heuristic yields very high quality solutions.     

Graves triads,Möbius pairs,and related matrices

A Graves triad is a cyclic triad of triangles, each circumscribing the next, forming a Pappus configuration. If two of the triangles are in perspective, then so are the other two pairs. In a non-cyclic triad of such circumscribing triangles, if two pairs are in perspective, then so is the third pair. These results correspond to certain properties of 3×3 zero-diagonal matrices. There is also an analogous result for Möbius pairs of mutually circumscribing tetrahedra and 4×4 zero-diagonal matrices.     

Routing multi-class traffic flows in the plane

We study a class of multi-commodity flow problems in geometric domains: For a given planar domain P populated with obstacles (holes) of K?2types, compute a set of thick paths from a “source” edge of P to a “sink” edge of P for vehicles of K distinct classes. Each class k of vehicle has a given set, Ok, of obstacles it must avoid and a certain width, wk, of path it requires. The problem is to determine if it is possible to route Nk width-wk paths for class k vehicles from source to sink, with each path avoiding the requisite set Ok of obstacles, and no two paths overlapping. This form of multi-commodity flow in two-dimensional domains arises in computing throughput capacity for multiple classes of aircraft in an airspace impacted by different types of constraints, such as those arising from weather hazards.We give both algorithmic theory results and experimental results.We show hardness of many versions of the problem by proving that two simple variants are NP-hard even in the case K=2. If w₁=w₂=1, then the problem is NP-hard even when O₁=∅. If w₁=2, w₂=3, then the problem is NP-hard even when O₁=O₂. In contrast, the problem for a single width and a single type of obstacles is polynomially solvable.We present approximation algorithms for the multi-criteria optimization problems that arise when trying to maximize the number of routable paths. We also give a polynomial-time algorithm for the case in which the number of holes in the input domain is bounded.Finally, we give experimental results based on an implementation of our methods and experiment with enhanced heuristics for efficient solutions in practice. Our algorithms are being utilized in simulations with NASA?s Future Air traffic management Concepts Evaluation Tool (FACET). We report on experimental results based on applying our algorithms to weather-impacted airspaces, comparing heuristic strategies for searching for feasible path orderings and for computing short multi-class routes. Our results show that multi-class routes can feasibly be computed on real weather data instances on the scale required in air traffic management applications.     

Maximum thick paths in static and dynamic environments

We consider the problem of finding a large number of disjoint paths for unit disks moving amidst static or dynamic obstacles. The problem is motivated by the capacity estimation problem in air traffic management, in which one must determine how many aircraft can safely move through a domain while avoiding each other and avoiding “no-fly zones” and predicted weather hazards. For the static case we give efficient exact algorithms, based on adapting the “continuous uppermost path” paradigm. As a by-product, we establish a continuous analogue of Menger's Theorem.Next we study the dynamic problem in which the obstacles may move, appear and disappear, and otherwise change with time in a known manner; in addition, the disks are required to enter/exit the domain during prescribed time intervals. Deciding the existence of just one path, even for a 0-radius disk, moving with bounded speed is NP-hard, as shown by Canny and Reif [J. Canny, J.H. Reif, New lower bound techniques for robot motion planning problems, in: Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci., 1987, pp. 49–60]. Moreover, we observe that determining the existence of a given number of paths is hard even if the obstacles are static, and only the entry/exit time intervals are specified for the disks. This motivates studying “dual” approximations, compromising on the radius of the disks and on the maximum speed of motion.Our main result is a pseudopolynomial-time dual-approximation algorithm. If K unit disks, each moving with speed at most 1, can be routed through an environment, our algorithm finds (at least) K paths for disks of radius somewhat smaller than 1 moving with speed somewhat larger than 1.     

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.     

Heuristic algorithms for a complex parallel machine scheduling problem

In this work we present a new scheduling model for parallel machines, which extends the multiprocessor scheduling problem with release times for minimizing the total tardiness, and also extends the problem of vehicle routing with time windows. This new model is motivated by a resource allocation problem, which appears in the service sector. We present two class of heuristic algorithms for the solution of the problem, the first class is a class of greedy algorithms, the second class is based on the solutions of linear assignment problems. Furthermore we give a rescheduling algorithm, which improves a given feasible solution of the problem. This research has been supported by the Hungarian National Foundation for Scientific Research, Grant T046405.     

Test driving three 1995 genetic algorithms: New test functions and geometric matching

Genetic algorithms have attracted a good deal of interest in the heuristic search community. Yet there are several different types of genetic algorithms with varying performance and search characteristics. In this article we look at three genetic algorithms: an elitist simple genetic algorithm, the CHC algorithm and Genitor. One problem in comparing algorithms is that most test problems in the genetic algorithm literature can be solved using simple local search methods. In this article, the three algorithms are compared using new test problems that are not readily solved using simple local search methods. We then compare a local search method to genetic algorithms for geometric matching and examine a hybrid algorithm that combines local and genetic search. The geometric matching problem matches a model (e.g., a line drawing) to a subset of lines contained in a field of line fragments. Local search is currently the best known method for solving general geometric matching problems.     

The prize-collecting generalized minimum spanning tree problem

We introduce the prize-collecting generalized minimum spanning tree problem. In this problem a network of node clusters needs to be connected via a tree architecture using exactly one node per cluster. Nodes in each cluster compete by offering a payment for selection. This problem is NP-hard, and we describe several heuristic strategies, including local search and a genetic algorithm. Further, we present a simple and computationally efficient branch-and-cut algorithm. Our computational study indicates that our branch-and-cut algorithm finds optimal solutions for networks with up to 200 nodes within two hours of CPU time, while the heuristic search procedures rapidly find near-optimal solutions for all of the test instances.     

Shortest path in the presence of obstacles: An application to ocean shipping

This paper presents the problem of determining the estimated time of arrival (ETA) at the destination port for a ship located at sea. This problem is formulated as a shortest path problem with obstacles, where the obstacles are modelled by polygons representing the coastlines. An efficient solution algorithm is proposed to solve the problem. Instead of generating a complete visibility graph and solving the problem as an ordinary shortest path problem, the algorithm constructs arcs to the ship node during the solution process only when needed. This greatly enhances the algorithmic performance. Computational results based on test problems from an actual dry-bulk shipping operation are provided. The proposed algorithm is implemented in a decision support system for the planning of ship operations and it has successfully been applied on several real life problems.     

满足路径约束的最优路算法

满足路径约束的最优路问题已被证明是NP-hard问题。本针对源点到宿点满足两个QoS(服务质量)度量的路由问题，给出一种保证时延的最小费用路由启发式算法。这个算法的优点是计算较简单、占用内存小、时间短。算法的复杂度是多项式的，表明算法是有效的。     

A branch and bound algorithm for the acyclic subgraph problem

A branch and bound algorithm for the acyclic subgraph problem (feedback are set problem) is described. The branching scheme lexicographically enumerates all permutations, skipping initial segments known by some easy tests not to have any optimal completion. A lower bound for the number of feedback arcs is given by the size of any collection of disjoint cycles. We propose a heuristic algorithm to find a large collection. The size of the problems our branch and bound algorithm can solve varies from 25 to 34 nodes, depending on the nature of the problem.     

An O(n) algorithm to find a near-optimum partition of a convex polygon

This paper presents a heuristic algorithm to partition an n-sided convex polygon into n ? 2 nonintersecting triangles. Based on some theorems in [T. C. Hu and M. T. Shing, to appear], we can give a general formula to find the maximum ratio between the cost of the heuristic partition and the cost of the optimum partition and prove that this ratio never exceeds 1.155. We also given an example to show that the bound is tight.     

Computing simple paths among obstacles

Given a set X of points in the plane, two distinguished points s,tX, and a set Φ of obstacles represented by line segments, we wish to compute a simple polygonal path from s to t that uses only points in X as vertices and avoids the obstacles in Φ. We present two results: (1) we show that finding such simple paths among arbitrary obstacles is NP-complete, and (2) we give a polynomial-time algorithm that computes simple paths when the obstacles form a simple polygon P and X is inside P. Our algorithm runs in time O(m²n²), where m is the number of vertices of P and n is the number of points in X.     

Admission control with advance reservations in simple networks

In the admission control problem we are given a network and a set of connection requests, each of which is associated with a path, a time interval, a bandwidth requirement, and a weight. A feasible schedule is a set of connection requests such that at any given time, the total bandwidth requirement on every link in the network is at most 1. Our goal is to find a feasible schedule with maximum total weight.We consider the admission control problem in two simple topologies: the line and the tree. We present a 12c-approximation algorithm for the line topology, where c is the maximum number of requests on a link at some time instance. This result implies a 12c-approximation algorithm for the rectangle packing problem, where c is the maximum number of rectangles that cover simultaneously a point in the plane. We also present an O(logt)-approximation algorithm for the tree topology, where t is the size of the tree. We consider the loss minimization version of the admission control problem in which the goal is to minimize the weight of unscheduled requests. We present a c-approximation algorithm for loss minimization problem in the tree topology. This result is based on an approximation algorithm for a generalization of set cover, in which each element has a covering requirement, and each set has a covering potential. The approximation ratio of this algorithm is Δ, where Δ is the maximum number of sets that contain the same element.     

Testing Homotopy for Paths in the Plane

In this paper we present an efficient algorithm to test if two given paths are homotopic; that is, whether they wind around obstacles in the plane in the same way. For paths specified by n line segments with obstacles described by n points, several standard ways achieve quadratic running time. For simple paths, our algorithm runs in O(n log n) time, which we show is tight. For self-intersecting paths the problem is related to Hopcrofts problem; our algorithm runs in O(n ^3/2log n) time.     

Minimum cost multi-product flow lines

In this paper, the problem of finding the minimum cost flow line able to produce different products is considered. This problem can be formulated as a shortest path problem on an acyclic di-graph when the machines graph associated with each product family is a chain or a comb. These graphs are relevant in production planning when dealing with pipelined assembly systems. We solve the problem using A ^* algorithm which can be efficiently exploited when there is a good estimate on the value of an optimal solution. Therefore, we adapt a known bound for the Shortest Common Supersequence problem to our case and show the effectiveness of the approach by presenting an extensive computational experience.     

A fast heuristic algorithm for the maximum concurrent <Emphasis Type="Italic">k</Emphasis>-splittable flow problem

In this paper, we propose a fast heuristic algorithm for the maximum concurrent k-splittable flow problem. In such an optimization problem, one is concerned with maximizing the routable demand fraction across a capacitated network, given a set of commodities and a constant k expressing the number of paths that can be used at most to route flows for each commodity. Starting from known results on the k-splittable flow problem, we design an algorithm based on a multistart randomized scheme which exploits an adapted extension of the augmenting path algorithm to produce starting solutions for our problem, which are then enhanced by means of an iterative improvement routine. The proposed algorithm has been tested on several sets of instances, and the results of an extensive experimental analysis are provided in association with a comparison to the results obtained by a different heuristic approach and an exact algorithm based on branch and bound rules.     

A Combined Evolutionary Search and Multilevel Optimisation Approach to Graph-Partitioning

The graph-partitioning problem is to divide a graph into several pieces so that the number of vertices in each piece is the same within some defined tolerance and the number of cut edges is minimised. Important applications of the problem arise, for example, in parallel processing where data sets need to be distributed across the memory of a parallel machine. Very effective heuristic algorithms have been developed for this problem which run in real-time, but it is not known how good the partitions are since the problem is, in general, NP-complete. This paper reports an evolutionary search algorithm for finding benchmark partitions. A distinctive feature is the use of a multilevel heuristic algorithm to provide an effective crossover. The technique is tested on several example graphs and it is demonstrated that our method can achieve extremely high quality partitions significantly better than those found by the state-of-the-art graph-partitioning packages.