Rectilinear Location Revisited

In this note we study the multidimensional maximin rectilinear location problem. A general framework is given, partial optimal solutions introduced—together with an algorithm and its properties—and an upper bound analysis is conducted.     

Solving Rectilinear Planar Location Problems with Barriers by a Polynomial Partitioning

This paper considers planar location problems with rectilinear distance and barriers where the objective function is any convex, nondecreasing function of distance. Such problems have a non-convex feasible region and a nonconvex objective function. Based on an equivalent problem with modified barriers, derived in a companion paper [3], the non convex feasible set is partitioned into a network and rectangular cells. The rectangular cells are further partitioned into a polynomial number of convex subcells, called convex domains, on which the distance function, and hence the objective function, is convex. Then the problem is solved over the network and convex domains for an optimal solution. Bounds are given that reduce the number of convex domains to be examined. The number of convex domains is bounded above by a polynomial in the size of the problem.     

Optimal Spreading in an n Dimensional Rectilinear Grid

A disturbance spreads in a rectilinear n dimensional grid moving from each affected point to at most one neighbor in each unit of time. The question how many points can be affected in N units of time is answered to the two leading orders of N.     

基于加权绝对值距离Steiner最优树的选址问题

提出基于加权绝对值距离Steiner最优树思想的选址模型,给出了该模型的蚂蚁算法实现策略.在此基础上,分析了电子商务环境下企业配送中心选址问题,并用算例验证了该选址方案的可行性.     

An Efficient Algorithm for Solving the Rectilinear Multifacility Location Problem

One of the efficient methods for solving large rectilinear multifacilitylocation problems is the Direct Search method. The only drawbackof this method lies in the following difficulty. In some situations,when t new facilities are located together at one point, thenumber of arithmetic operations which are needed to establishoptimality is proportional to t²2^t. Therefore the method needsa prohibitive amount of computation time whenever t exceeds,say, 20. This paper gives a simple remedy for this problem.The paper states and proves a new necessary and sufficient optimalitycondition. This condition transforms the problem of computinga descent direction into a constrained linear least-squaresproblem. The latter problem is solved by a relaxation methodthat takes advantage of its special structure. The new techniqueis incorporated into the Direct Search method. This yields animproved algorithm that handles efficiently very large clusters.Numerical results are included.     

A Primal Simplex Based Solution Procedure for the Rectilinear Distance Multifacility Location Problem

In this paper a primal simplex based solution procedure is developed for a multiproduct, multi-facility location problem using rectilinear distance measures. By overcoming the combinatorial nature of the problem which arises in the presence of degeneracy, this procedure is capable of handling large size problems. Computational results are also provided.     

Is Linear Programming Necessary for Single Facility Location with Maximin of Rectilinear Distance?

This paper discusses the problem of locating a single obnoxious or undesirable facility so as to maximize its rectilinear distance from a given set of existing facilities. An outline of published linear programming methods is given. Based on these ideas we present an algorithm which exploits known properties of the optimal solution and does not use linear programming at all.     

An Equivalence Result for Single Facility Planar Location Problems with Rectilinear Distance and Barriers

This paper considers planar location problems with rectilinear distance and barriers, where the objective function is any convex, nondecreasing function of distance. Such problems have a non-convex feasible region and a non-convex objective function. A modification of the barriers is developed based on properties of the rectilinear distance. It is shown that the original problem with barriers is equivalent to the problem with modified barriers. A particular modification is given that reduces the feasible region and permits its partitioning into convex subsets on which the objective function is convex. A solution algorithm based on the partitioning is the subject of a companion paper.     

An Enhancement of the Drezner—Wesolowsky Algorithm for Single-Facility Location with Maximin of Rectilinear Distance

In this note, we examine the algorithm of Drezner and Wesolowsky for locating a facility with maximin rectilinear distance to a given set of demand points. The concept of the closest-point constraint is introduced as a technique for increasing the efficiency of the algorithm. This potential increase in efficiency is demonstrated by an example.     

Rectilinear laminar flow of a visco-elastic fluid

Zusammenfassung Eine inkompressible viskoelastische Flüssigkeit fliesst zwischen zwei parallelen, starren, unendlichen Wänden. Es wird unter der Voraussetzung, dass die eine Wand fest ist und die andere sich mit einer exponentiell abklingenden Geschwindigkeit bewegt, das zur Aufrechterhaltung einer speziellen laminaren Strömung nötige Kraftfeld bestimmt.     

Rectilinear drawings of graphs

We consider graphs drawn in the plane such that every edge crosses at most one other edge. We characterize, in terms of two forbidden sub-configurations, which of these graphs are equivalent to drawings such that all edges are straight line segments. As a consequence we obtain a complete characterization of the pairs of dual graphs that can be represented as geometric dual graphs such that all edges except one are straight line segments.     

Embedding into Rectilinear Spaces

We show that the problem whether a given finite metric space (X,d) can be embedded into the rectilinear space R ^m can be formulated in terms of m -colorability of a certain hypergraph associated with (X,d) . This is used to close a gap in the proof of an assertion of Bandelt and Chepoi [2] on certain critical metric spaces for this embedding problem. We also consider the question of determining the maximum number of equidistant points that can be placed in the m -dimensional rectilinear space and show that this number is equal to 2m for m ≤ 3 . Received March 19, 1996, and in revised form March 14, 1997.     

Optimal Design of a Circular Plate with Rectilinear Anisotropy

We investigate the problem of optimization of the basic frequency of free oscillations of a nonorthotropic ring plate with rectilinear anisotropy that is undergoing shear. We introduce a small physical parameter characterizing the anisotropy properties of the plate material. By assuming that the thickness of the plate varies within relatively small limits, we apply the small-parameter method to solve the optimization problem, which allows us to obtain an approximate analytic solution of the problem and an asymptotic estimate of the maximum value of the basic frequency.     

基于网格化管理视角下灾后应急物流决策模型与算法研究

灾害发生后,应急资源的需求预测与应急配送中心的合理选址是实现高效救援的关键。本文通过在网格化管理视角下的信息更新将应急救援过程划分为多个阶段,在开展救援的过程中实现救援信息收集和救援预测的同步开展,建立一种多阶段带时间约束的应急救援物资配送响应-时效性的选址模型。借助遗传算法(NSGA-II),实现了基于编码结构独立、路径相互关联基础上的多目标规划求解。本研究的决策模型及算法有着较好的搜索与寻优能力,对实际救援开展具有指导意义。     

Rectilinear paths among rectilinear obstacles

Given a set of obstacles and two distinguished points in the plane the problem of finding a collision-free path subject to a certain optimization function is a fundamental problem that arises in many fields, such as motion planning in robotics, wire routing in VLSI and logistics in operations research. In this survey we emphasize its applications to VLSI design and limit ourselves to the rectilinear domain in which the goal path to be computed and the underlying obstacles are all rectilinearly oriented, i.e., the segments are either horizontal or vertical. We consider different routing environments, and various optimization criteria pertaining to VLSI design, and provide a survey of results that have been developed in the past, present current results and give open problems for future research.     

Maximal Rectilinear Crossing of Cycles

We address the following question: In drawing a cycle on n vertices (or a graph all of whose degrees are 2) in the plane with straight line arcs, how many crossings can there be? A complete answer is given; namely, if n is odd, the number of crossings can be anything up to n(n?3)/2 except n(n?3)/2?1. For n even, the number of crossings in one cycle can be any integer up to n(n?4)/2+1; general bivalent even graphs can achieve any integer up to n(2n?7)/4 as the number of crossings.     

On Special Classes of Rectilinear Congruences

Let Σ be an oriented rectilinear congruence in three-dimensional Euclidean space E³ and f a one-to-one mapping between the points of the middle surface and the points of the middle envelope of it. In this paper we investigate some properties of Σ, when f is equiareal or isometric.     

Rectilinear distance to a facility in the presence of a square barrier

This paper derives analytical expressions for the rectilinear distance to a facility in the presence of a square barrier. The distribution of the barrier distance is derived for two regular patterns of facilities: square and diamond lattices. This distribution, which provides all the information about the barrier distance, will be useful for facility location problems with barriers and reliability analysis of facility location. The distribution of the barrier distance demonstrates how the location and the size of the barrier affect the barrier distance. A?numerical example shows that the total barrier distance increases as the barrier gets closer to a facility, whereas the maximum barrier distance increases as the barrier becomes greater in size.     

关于三维Minkowski空间中直线汇的一些注记

本文研究了三维Minkowski空间中直线汇的一些性质,特别是关于类时线汇的性质．讨论了线汇基本元素的存在性,并证明了关于三维Minkowski空间中类时线汇的配分参数的一个结果,推广了苏步青1927年的—个成果．