A fast and effective heuristic for the orienteering problem

In the orienteering problem, start and end points are specified along with other locations which have associated scores. Given a fixed amount of time, the goal is to determine a path from the start point to the end point through a subset of locations in order to maximize the total path score. In this paper, a fast and extremely effective heuristic is presented and tested on 67 problems taken from the literature and 40 new test problems. The computational results are presented in detail.     

One-dimensional machine location problems in a multi-product flowline with equidistant locations

An assignment of machines to locations along a straight track is required to optimize material flow in many manufacturing systems. The assignment of M unique machines to M locations along a linear material handling track with the objective of minimizing the total machine-to-machine material transportation cost is formulated as a quadratic assignment problem (QAP). The distance matrix in problems involving equally-spaced machine locations in one dimension is seen to possess some unique characteristics called amoebic properties. Since an optimal solution to a problem with large M is computationally intractable (the QAP is NP-hard), a number of the amoebic properties are exploited to devise heuristics and a lower bound on the optimal solution. Computational results which demonstrate the performance of the heuristics and the lower bound are presented.     

Centralized and distributed cooperative Receding Horizon control of autonomous vehicle missions

We consider a setting where multiple vehicles form a team cooperating to visit multiple target points and collect rewards associated with them. The team objective is to maximize the total reward accumulated over a given time interval. Complicating factors include uncertainties regarding the locations of target points and the effectiveness of collecting rewards, differences among vehicle capabilities, and the fact that rewards are time-varying. We present a Receding Horizon (RH) control scheme which dynamically determines vehicle trajectories by solving a sequence of optimization problems over a planning horizon and executing them over a shorter action horizon. A key property of this scheme is that the trajectories it generates are stationary, in the sense that they ultimately guide vehicles to target points, even though the controller is not designed to perform any discrete point assignments. The proposed scheme is centralized and it induces a cooperative behavior. We subsequently develop a distributed cooperative controller which does not require a vehicle to maintain perfect information on the entire team and whose computational cost is scalable and significantly lower than the centralized case, making it attractive for applications with real-time constraints. We include simulation-based comparisons between the centralized algorithm and the distributed version, which illustrate the effectiveness of the latter.     

Fuzzy disk for covering fuzzy points

In this paper, we consider an important fuzzy version of the well known smallest covering circle problem which is also called the Euclidean 1-center problem. Here we are given a set of points in the plane whose locations are crisp. However, the requirement for coverage of each point is fuzzy as represented by its grade of membership. As such we qualify the points as fuzzy. In the above framework, we wish to find a fuzzy disk with minimum fuzzy area for covering the given fuzzy points. After developing a general model, certain special cases are investigated in detail. Polynomial algorithms are presented for the special cases.     

Isodistant points in competitive network facility location

An isodistant point is any point on a network which is located at a predetermined distance from some node. For some competitive facility location problems on a network, it is verified that optimal (or near-optimal) locations are found in the set of nodes and isodistant points (or points in the vicinity of isodistant points). While the nodes are known, the isodistant points have to be determined for each problem. Surprisingly, no algorithm has been proposed to generate the isodistant points on a network. In this paper, we present a variety of such problems and propose an algorithm to find all isodistant points for given threshold distances associated with the nodes. The number of isodistant points is upper bounded by nm, where n and m are the number of nodes and the number of edges, respectively. Computational experiments are presented which show that isodistant points can be generated in short run time and the number of such points is much smaller than nm. Thus, for networks of moderate size, it is possible to find optimal (or near-optimal) solutions through the Integer Linear Programming formulations corresponding to the discrete version of such problems, in which a finite set of points are taken as location candidates.     

Bi-criteria dynamic location-routing problem for patrol coverage

In this paper, we address the problem of dynamic patrol routing for state troopers for effective coverage of highways. Specifically, a number of state troopers start their routes at temporary stations (TS), patrol critical locations with high crash frequencies, and end their shifts at other (or the same) TS so the starting points for the next period are also optimized. We determine the number of state troopers, their assigned routes, and the locations of the TS where they start and end their routes. The TS are selected from a given set of potential locations. The problem, therefore, is a multi-period dynamic location-routing problem in the context of public service. Our objective is to maximize the critical location coverage benefit while minimizing the costs of TS selections, vehicle utilizations, and routing/travel. The multi-objective nature of the problem is handled using an ?-constraint approach. We formulate the problem as a mixed integer linear programming model and solve it using both off-the-shelf optimization software and a custom-built, efficient heuristic algorithm. The heuristic, utilizing the hierarchical structure of the problem, is built on the decomposition of location and routing problems. By allowing routing to start from multiple locations, our model improves the coverage by as much as 12% compared with the single-depot coverage model.     

Using artificial neural networks to solve the orienteering problem

In the orienteering problem, we are given a transportation network in which a start point and an end point are specified. Other points have associated scores. Given a fixed amount of time, the goal is to determine a path from start to end through a subset of locations in order to maximize the total path score. This problem has received a considerable amount of attention in the last ten years. The traveling salesman problem is a variant of the orienteering problem. This paper applies a modified, continuous Hopfield neural network to attack this NP-hard optimization problem. In it, we design an effective energy function and learning algorithm. Unlike some applications of neural networks to optimization problems, this approach is shown to perform quite well.     

Empirical Mark Covariance and Product Density Function of Stationary Marked Point Processes—A Survey on Asymptotic Results

Marked point processes are stochastic models to describe random patterns of marked points {[X _i ,M _i ], i?≥?1} in some bounded subset of the d-dimensional Euclidean space (usually d?=?1, 2 or 3 in applications), where each point X _i carries additional random information expressed as mark M _i taking values in some metric space. To study the correlations between distinct points and between marks located at distinct points we use kernel-type estimators of the second-order product density and the mark covariance function of a spatially homogeneous marked point process. Both functions and their empirical counterparts are suitable characteristics to identify point process models by construction of statistical goodness-of-fit tests.     

Sets with not more than two-valued metric projection on planes

For a set M in the Euclidean plane ?², we prove that if any point x ∈ ?² has one or two closest points in M, then each point of the convex hull of M lies in the segment with endpoints in M.     

Deformation of CR-manifolds,minimal points and CR-manifolds with the microlocal analytic extension property

LetM be a smooth CR-manifold embedded into ? ⁿ . Letp be a point inM and letC be a small truncated cone inM (in suitable Euclidean coordinates onM) with vertexp which “symmetry axis” is a real vector in the complex tangent space. Then one can deformM into a smooth CR-manifoldM _d letting fixed all points outsideC in such a way thatp is a minimal point ofM _d . This result is used to give a new proof of the fact that wedge extendability of continuous CR-functions propagates along the CR-orbits of a CR-manifold. It allows also to prove the following natural result which was conjectured by Trepreau. LetM be a smooth generic CR-manifold in ? ⁿ . SupposeM consists of one single CR-orbit. Then each continuous CR-function onM is wedge extendable at any point ofM. Uniqueness theorems for continuous CR-functions are derived.     

De Rham cohomology of manifolds containing the points of infinite type,and Sobolev estimates for the\bar \partial - Neumann problem

We consider smooth bounded pseudoconvex domains Ω in Cⁿ whose boundary points of infinite type are contained in a smooth submanifoldM (with or without boundary) of the boundary having its (real) tangent space at each point contained in the null space of the Levi form ofbΩ at the point. (In particular, complex submanifolds satisfy this condition.) We consider a certain one-form α onbΩ and show that it represents a De Rham cohomology class on submanifolds of the kind described. We prove that if α represents the trivial cohomology class onM, then the Bergman projection and the \(\bar \partial - Neumann\) operator on Ω are continuous in Sobolev norms. This happens, in particular, ifM has trivial first De Rham cohomology, for instance, ifM is simply connected.     

Fast multipole methods for approximating a function from sampling values

Both barycentric Lagrange interpolation and barycentric rational interpolation are thought to be stable and effective methods for approximating a given function on some special point sets. A direct evaluation of these interpolants due to N interpolation points at M sampling points requires \(\mathcal {O}(NM)\) arithmetic operations. In this paper, we introduce two fast multipole methods to reduce the complexity to \(\mathcal {O}(\max \left \{N,M\right \})\). The convergence analysis is also presented in this paper.     

Reducing work-in-process movement for multiple products in one-dimensional layout problems

This research describes a method to assign M machines, which are served by a material handling transporter, to M equidistant locations along a track, so that the distance traveled by a given set of jobs is minimized. Traditionally, this problem (commonly known as a machine location problem) has been modeled as a quadratic assignment problem (QAP), which is NP-hard, thus motivating the need for efficient procedures to solve instances with several machines. In this paper we develop a branching heuristic to obtain sub-optimum solutions to the problem; a lower bound on the optimum solution has also been presented. Results obtained from the heuristics are compared with results obtained from other heuristics with similar objectives. It is observed that the results are promising, and justify the usage of developed methods.     

On the conjugate locus of pseudo-Riemannian manifolds

Let expm :T_mM → M be the exponential map of a Riemannian manifold M at a point m ∈ M. Warner proved that in any neighbourhood of a conjugate point in T_mM, the map exp_m is not injective. Moreover, he described the exponential map in a suitable coordinate system in a neighbourhood of a regular conjugate point, these points build an open dense set in the conjugate locus. We will investigate in the pseudo-Riemannian case such subsets, where the results of Warner generalize. For the definition of these subsets of the conjugate locus we use a bilinear form on ker(T_v exp_m), where v is a conjugate point, which will defined by the geodesic flow and the pseudo-Riemannian metric tensor.     

Special conformal groups of a Riemannian manifold and Lie point symmetries of the nonlinear Poisson equation

We obtain a complete group classification of the Lie point symmetries of nonlinear Poisson equations on generic (pseudo) Riemannian manifolds M. Using this result we study their Noether symmetries and establish the respective conservation laws. It is shown that the projection of the Lie point symmetries on M are special subgroups of the conformal group of M. In particular, if the scalar curvature of M vanishes, the projection on M of the Lie point symmetry group of the Poisson equation with critical nonlinearity is the conformal group of the manifold. We illustrate our results by applying them to the Thurston geometries.     

Generalized gradients and characterization of epi-Lipschitz sets in Riemannian manifolds

In this paper, a notion of generalized gradient on Riemannian manifolds is considered and a subdifferential calculus related to this subdifferential is presented. A characterization of the tangent cone to a nonempty subset S of a Riemannian manifold M at a point x is obtained. Then, these results are applied to characterize epi-Lipschitz subsets of complete Riemannian manifolds.     

Fixed point theorems for generalized set-contraction maps and their applications

A new generalized set-valued contraction on topological spaces with respect to a measure of noncompactness is introduced. Two fixed point theorems for the KKM type maps which are either generalized set-contraction or condensing ones are given. Furthermore, applications of these results for existence of coincidence points and maximal elements are deduced.     

Backtracking and its Amoebic Properties in One-dimensional Machine Location Problems

This paper studies the assignment of M unique machines to M equally spaced locations along a linear material handling track with the objective of minimizing the cost of (jobs) backtracking (i.e. moving upstream). Because of the arrangement of machines and restrictions imposed by the sequence of operations for each job, some jobs may have to backtrack to complete required processing on different machines. This problem is formulated as a quadratic assignment problem. An optimal solution to a problem with large M is computationally intractable. The backtracking distance matrix in problems involving equally-spaced machine locations in one dimension is seen to possess some unique characteristics called amoebic properties. Ten amoebic properties have been identified and exploited to devise a heuristic and a lower bound on the optimal solution. Results which describe the performance of the heuristic and the lower bound are presented.     

Simulated annealing and tabu search approaches for the Corridor Allocation Problem

In the Corridor Allocation Problem, we are given n facilities to be arranged along a corridor. The arrangements on either side of the corridor should start from a common point on the left end of the corridor. In addition, no space is allowed between two adjacent facilities. The problem is motivated by applications such as the arrangement of rooms in office buildings, hospitals, shopping centers or schools. Tabu search and simulated annealing algorithms are presented to minimize the sum of weighted distances between every pair of facilities. The algorithms are evaluated on several instances of different sizes either randomly generated or available in the literature. Both algorithms reached the optimal (when available) or best-known solutions of the instances with n ? 30. For larger instances with size 42 ? n ? 70, the simulated annealing implementation obtained smaller objective values, while requiring a smaller number of function evaluations.     

CAT(0) 4-manifolds possessing a single tame point are Euclidean

The concepts of geometric and topological tame point are introduced for a space of nonpositive curvature. These concepts are applied to the characterization problem forCAT(0) 4-manifolds. It is shown that everyCAT(0)M ⁴ having a single (geometric or topological) tame point is homeomorphic toR ⁴. Davis and Januszkiewicz have recently constructedCAT(0)n-manifolds,M ⁿ withn ≥ 5 such that the set of tame points form a dense open subset ofM ⁿ , butM ⁿ ≠R ⁿ .