Bi-Criteria Optimization, Geometric Location & Related Problems

双标准优化、几何位置

• 批准号: 9309743
• 负责人: D. Lee
• 金额: $ 22.12万
• 依托单位: Northwestern University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1993
• 资助国家: 美国
• 起止时间: 1993-08-15 至 1997-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9309743&HistoricalAwards=false
• 关键词: Bi; Criteria; Optimization; Geometric; Location

Optimization problems that arise in computational and other related areas are investigated in this project. Special emphasis is placed on bi-criteria optimization problems and geometric problems. In a communication network, the two important criteria that are of great practical implications are the communication delay and total cost. In path planning routing, the two important criteria are the total length and the number of bends. Optimization problems concerning two criteria either simultaneously or in lexicographical order are studied. Among those to be studied are weighted farthest neighbor Voronoi diagram construction for a set of point sites, a new class of geometric problems, called the capacitated path problem, in which the obstacles have capacities and the cost of a path avoiding these obstacles is a function of the length of the path and the capacities of the obstacles visited by the path, and routing problems with multiple source-destination pairs such that these paths do not cross and yet their total length is to be minimized. The goals of this research are to apply geometric techniques to tackle these new classes of optimization problems, and to identify problems that can (or cannot) benefit from the geometric properties.

计算中出现的优化问题 及其他相关领域的研究。 特别强调的是放在双准则优化问题和几何 问题 在通信网络中， 具有重大实际意义的标准是通信延迟， 总成本。 在路径规划路由中，两个重要的标准是 总长度和弯曲的数量。 关于两个问题的优化问题 同时或按词典编纂顺序研究标准。 其中要研究的是加权最远邻Voronoi图 构造一组点，一类新的几何问题， 称为能力限制路径问题，其中障碍物具有能力， 避免这些障碍物的路径的成本是路径长度的函数。 路径和路径访问的障碍物的容量，以及路由 多个源-目的地对的问题，使得这些路径 不交叉，但它们的总长度要最小化。 这个的目标 研究是应用几何技术来解决这些新的类别， 优化问题，并确定可以（或不能）受益于 几何性质