On the Complexity of the Steiner Problem

Recently Rubinstein et al. gave a new proof of the NP-completeness of the discretized Steiner problem, that is, the problem of finding a shortest network connecting a given set of points in the plane where all vertices are integer points and a discretized metric is used. Their approach was to consider the complexity of the PALIMEST problem, the Steiner problem for sets of points lying on two parallel lines. In this paper, we give a new proof of this theorem, using simpler, more constructive arguments. We then extend the result to a more general class of networks known as APE-Steiner trees in which certain angles between edges or slopes of edges are specified beforehand.     

A Polynomial Time Approximation Scheme for the Problem of Interconnecting Highways

The objective of the Interconnecting Highways problem is to construct roads of minimum total length to interconnect n given highways under the constraint that the roads can intersect each highway only at one point in a designated interval which is a line segment. We present a polynomial time approximation scheme for this problem by applying Arora's framework (Arora, 1998; also available from http:www.cs.princeton.edu/~arora). For every fixed c > 1 and given any n line segments in the plane, a randomized version of the scheme finds a -approximation to the optimal cost in O(n ^O(c)log(n) time.     

The Steiner Tree Problem in Kalmanson Matrices and in Circulant Matrices

We investigate the computational complexity of two special cases of the Steiner tree problem where the distance matrix is a Kalmanson matrix or a circulant matrix, respectively. For Kalmanson matrices we develop an efficient polynomial time algorithm that is based on dynamic programming. For circulant matrices we give an -hardness proof and thus establish computational intractability.     

Polynomial Time Approximation Scheme for the Rectilinear Steiner Arborescence Problem

Given a set N of n terminals in the first quadrant of the Euclidean plane E², find a minimum length directed tree rooted at the origin o, connecting to all terminals in N, and consisting of only horizontal and vertical arcs oriented from left to right or from bottom to top. This problem is called rectilinear Steiner arborescence problem, which has been proved to be NP-complete recently (Shi and Su, 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2000, to appear). In this paper, we present a polynomial time approximation scheme for this problem.     

Minimum Cost Edge Subset Covering Exactly k Vertices of a Graph

Given a graph G with nonnegative edge costs and an integer k, we consider the problem of finding an edge subset S of minimum total cost with respect to the constraint that S covers exactly k vertices of G. An O(n ³) algorithm is presented where n is the order of G. It is based on the author's previous paper dealing with a similar problem asking S to cover at least k vertices.     

一类带有限制的网络瓶颈容量扩张问题

在一些物理网络中,当设施（边的容量等）建立后,由于需求增加,需要调整网络的容量来提高服务水平。调整优化的过程中既要考虑扩张成本,同时也要考虑需要调整的总边数,以尽可能小的影响人们的正常生活。本文研究对于一个给定的网络G,已知边e_i的初始容量和单位容量扩张成本,在预算成本和扩张总边数的约束下,如何有效地扩张边的容量至x_i,使得系统的容量最大,即max{min_ei∈T x_i,T是网络G中的生成树。首先求解两个与之相关的模型,然后通过分析两个相关模型与原问题之间的联系与区别,提出了原问题的多项式时间算法。最后,通过算例说明算法的步骤,并分析了不同参数值对系统容量的影响。     

Two Novel Evolutionary Formulations of the Graph Coloring Problem

We introduce two novel evolutionary formulations of the problem of coloring the nodes of a graph. The first formulation is based on the relationship that exists between a graph's chromatic number and its acyclic orientations. It views such orientations as individuals and evolves them with the aid of evolutionary operators that are very heavily based on the structure of the graph and its acyclic orientations. The second formulation, unlike the first one, does not tackle one graph at a time, but rather aims at evolving a program to color all graphs belonging to a class whose members all have the same number of nodes and other common attributes. The heuristics that result from these formulations have been tested on some of the Second DIMACS Implementation Challenge benchmark graphs, and have been found to be competitive when compared to the several other heuristics that have also been tested on those graphs.     

Proof of Toft's Conjecture: Every Graph Containing No Fully Odd K4 is 3-Colorable

A fully odd K₄ is a subdivision of K₄ such that each of the six edges of the K₄ is subdivided into a path of odd length. In 1974, Toft conjectured that every graph containing no fully odd K₄ can be vertex-colored with three colors. The purpose of this paper is to prove Toft's conjecture.     

基于整数规划强对偶求解一类局域性资源受限项目调度问题

资源受限项目调度问题(简称RCPSP)是最具代表性的项目调度问题之一,调度过程可理解为,将受资源约束的平行工序调整为顺序工序。本文针对实际中广泛存在的资源局域、而非全局受限的情况,研究局域性RCPSP,并重点考虑一类问题：项目某环节的一系列平行工序,可用资源量只有一半,各资源可重复利用且具有相应多功能,但最多能承担2个工序,需将这些工序两两排列成对,实现项目工期最短。本文首先探索问题“局域性”特征,量化局域调度对项目工期的影响;基于此,构建只涵盖“局域调度工序”的0-1规划模型;再者,发展整数规划强对偶理论,结合Dangzig-Wolfe分解等方法,提出多项式时间的精确算法;最后通过算例测试,验证算法优势,例如,计算大规模算例的最优解,运用该算法比常规精确方法可快数万倍以上。     

基于不对称需求信息的供应链最小订购量决策

在由一个供应商和一个零售商组成的两级分散供应链中,供应商通过制定最小订购量取得规模效应,保障自身利益。当零售商和供应商之间存在需求信息不对称时,即零售商掌握需求信息而供应商仅知道需求信息中价格敏感因子的分布,如何进行最小订购量决策成为供应商面临的一个重要问题。针对这一问题,从营销视角构建了基于Stackelberg博弈的利润最大化模型。假设供应商知道需求的价格敏感因子服从正态分布,通过严密的数学推导确定了模型中的最优最小订购量。将提出的最优最小订购量决策方法应用于云存储的销售供应链中,确定了云存储供应商销售的最优最小存储容量,阐释了方法的合理性与有效性。通过实验研究发现,最小订购量的设置提升了供应商的利润。所提方法对于考虑最小订购量的供应链协调研究具有积极的推动作用。     

最短时限运输问题及解法

提出了存在于实际中的最短时限运输问题,研究了其解的最优性充分条件,并给出了求解这一问题的具体步骤,最后用实例说明了解法的可操作性,该解法是解决这一类问题的一个好算法。     

电子易货资源匹配模型研究

针对电子易货市场资源匹配问题,通过系统分析易货市场中资源分类情况以及匹配的目标要求,得到资源匹配的数学模型;运用网络流理论对问题模型进行转化,把资源匹配数量最大的目标转换成有流量限制的网络最小费用流问题,依此建立网络模型;最后,以制造业和服务业之间的易货进行案例分析建模,用winQSB软件求解验证。结果表明,该模型的应用提高了易货资源匹配的运算效率和准确性。     

基于分层网络的机动时间研究

现有网络计划技术的研究主要针对单层网络,难以有效地指导大型项目的生产。原因在于大型工程项目生产过程复杂,工序成千上万,给对应的网络图描述带来了极大的困难。然而,通过网络分层技术则能把一个复杂的网络分解成多个简单的子网络,即将大型网络过渡到几个简单的单层网络,继而利用单层网络技术对其进行分析。本文依据大型网络的构建过程提出简化组合模型,将多层次复杂网络转化为多个单层次简单网络,在此基础上给出分层网络机动时间的计算公式。最后通过一个实例验证了此方法的正确性和可行性。     

有顾客时间窗和发货量变化的紧急车辆调度研究

对紧急车辆调度系统进行了研究,探讨了紧急车辆调度问题实现的关键技术.对有顾客时间窗和发货量变化的紧急车辆调度问题,运用了禁忌算法(TS)进行优化.算法基于实数编码,应用GENI插入法产生初始解和进行邻域操作,设计了三种邻域,利用容量约束控制单条路径配送点数,采用惩罚函数处理时间窗约束,通过设计虚拟车场等方法实现了车辆的紧急调度.本文给出了一个具有代表性的算例试验结果,算例结果及其分析表明了此方法对优化紧急车辆调度问题的有效性.     

考虑充电策略与电池损耗的电动汽车路径优化问题研究

针对目前研究电动物流车辆路径问题的文章未考虑电池损耗对运营成本的影响,且多在充电速率为恒定值的情况下对充电策略进行优化,本文将电动物流车辆在配送货物途中的充电时间和电池损耗成本纳入目标函数并建立了线性规划数学模型,统筹安排车辆行驶路径和充电策略使得物流企业整体运营成本最低。其次,提出了求解该问题的多阶段启发式算法MCWIGALNS。随后,通过多组算例验证了模型和算法的准确性。实验结果表明,考虑充电时间与深度放电成本的模型可以在配送距离不变或略有增加的情况下,较大幅度减少充电时间与电池损耗成本,到达降低运营成本的目的。最后,将算法实验结果与本领域已发表的成果进行比较,证明了MCWIGALNS算法对车辆路径问题具有出色的求解能力,提升了该问题理论成果的实用性。可以为物流企业电动汽车路径策略提供良好借鉴与帮助。     

随机条件下房地产开发的最优时机选择及其可达性问题研究

实物期权框架下的房地产投资相关研究长期忽视了对投资时机可达性问题的研究、忽视了对收益流与成本流相关性问题的探讨.有鉴于此,本文在房地产价格与建安成本二重随机性以及二者具有相关性的条件下,运用期权分析技术建模研究了房地产开发商的最优时机选择问题及最优时机的可达性问题.同时,文章对研究结果作了可达性分析、比较静态分析、数值分析、经济含义分析与政策含义分析,并对结论做了定性的实证检验.     

Using Graph Models to Analyze the Vulnerability of Electric Power Networks

In this article, we model electric power delivery networks as graphs, and conduct studies of two power transmission grids, i.e., the Nordic and the western states (U.S.) transmission grid. We calculate values of topological (structural) characteristics of the networks and compare their error and attack tolerance (structural vulnerability), i.e., their performance when vertices are removed, with two frequently used theoretical reference networks (the Erdös‐Rényi random graph and the Barabási‐Albert scale‐free network). Further, we perform a structural vulnerability analysis of a fictitious electric power network with simple structure. In this analysis, different strategies to decrease the vulnerability of the system are evaluated. Finally, we present a discussion on the practical applicability of graph modeling.     

考虑差异化服务时间的多车型电动汽车路径优化与充电策略研究

在政府政策大力支持以及社会环境意识不断增长的背景下,电动汽车在物流配送行业快速普及。电动汽车参与的物流配送服务需要物流专员、电动汽车和顾客三方协作完成。因此,在传统车辆配送路径优化的基础上,车辆的多样性、充电策略、人车的匹配以及服务时间差异化等因素都会影响物流运营成本。本文提出了考虑差异化服务成本的多车型电动汽车路径优化与充电策略问题并建立了该问题的整数规划数学模型。其次,提出了混合启发式算法MCWGATS,并通过多组算例验证了算法的有效性。最后,采用多组算例分析了多车型和差异化服务时间对运营成本的影响。实验结果表明,该模型有助于物流企业提高人员、物流车辆、服务时间等资源的利用效率,降低运营成本。     

Evaluation of Two Approaches to Defining Extinction Risk under the U.S. Endangered Species Act

The predominant definition of extinction risk in conservation biology involves evaluating the cumulative distribution function (CDF) of extinction time at a particular point (the “time horizon”). Using the principles of decision theory, this article develops an alternative definition of extinction risk as the expected loss (EL) to society resulting from eventual extinction of a species. Distinct roles are identified for time preference and risk aversion. Ranges of tentative values for the parameters of the two approaches are proposed, and the performances of the two approaches are compared and contrasted for a small set of real‐world species with published extinction time distributions and a large set of hypothetical extinction time distributions. Potential issues with each approach are evaluated, and the EL approach is recommended as the better of the two. The CDF approach suffers from the fact that extinctions that occur at any time before the specified time horizon are weighted equally, while extinctions that occur beyond the specified time horizon receive no weight at all. It also suffers from the fact that the time horizon does not correspond to any natural phenomenon, and so is impossible to specify nonarbitrarily; yet the results can depend critically on the specified value. In contrast, the EL approach has the advantage of weighting extinction time continuously, with no artificial time horizon, and the parameters of the approach (the rates of time preference and risk aversion) do correspond to natural phenomena, and so can be specified nonarbitrarily.