基于离散与连续选址相结合的平面选址问题研究——以华北石油局大牛地气田污水处理厂选址为例

选址问题的研究中,大多考虑的是理论距离(例如欧式距离等);但在实际问题中,真实的公路运输距离和理论距离有较大差异,并且修建公路的成本较高.在尽量利用当前的公路交通网络同时,又能得到最优选址,在现实中具有重要意义.以华北石油局大牛地气田第一采气厂污水处理厂选址为例,分别采用重心法选址、最大值最小化选址、多目标选址等选址的方法得到污水处理厂的备选点,并结合实际距离模拟出了各个备选点的运输费用,再综合考虑当地政策和交通状况等因素,最终得到了使得运输费用最低的新的污水处理厂的位置坐标P(9.33,11.79),在该位置建立污水处理厂比之前的运输方案每年大约可节约511万元的运输费用.方法最大的优点是减小了在选址过程中理论距离与实际距离的误差,在现实中具有一定的指导意义.     

城市消防站点布局的改进启发式算法

面对数量较多需要及时处理的突发事故,为了满足最短应急时间限制,最低应急资源数和最少的出救点等目标,在城市规划决策中,考虑在一个确定应急限制期下的安全消防站选址问题,给出一个反映决策者对时间和费用偏好的折衷选址方案十分必要.从实际应用出发,运用改进启发式算法方法研究时间与资源限制条件下的多出救点组合模型求解问题.给出了应急限制期和安全消防设施点建立的费用模型,从理论上证明了模型求解方法的正确性.在给定限制期条件下,通过分析得出应急服务设施点选择方法.通过算例说明该计算方法的具体应用,为交通安全消防站点选择提供参考,该方法还适用于诸如医院急救站等类似公共设施的规划建设.     

碳排放限制下的冷藏集装箱多式联运路径优化

为了降低碳排放限制下的冷藏集装箱多式联运成本,实现节能减排的目的,高效的路径选择至关重要.该文基于碳排放限制的视角,针对多式联运网络中铁路和水路运输具有发班时间限制,以及冷藏集装箱需要考虑制冷费用、货损货差的特点,建立了在碳排放限制下以总成本最低为目标的优化模型.构建总成本时不仅考虑了运输费用和转运费用,还考虑了受发班时间影响而动态变化的冷藏费用和货损费用.设计了遗传算法求解,并进行了算例分析.结果表明:通过该模型和算法,可根据决策者的要求快速地选出成本最少的运输方案,为决策者提供决策支持.     

带补偿机制的垃圾焚烧厂选址问题研究

研究了带补偿机制的垃圾焚烧厂选址问题,在综合考虑选址成本、补偿标准等因素的前提下,建立了以垃圾焚烧厂对附近居民造成的负面影响极小化和垃圾焚烧厂的总运行费用极小化为目标的垃圾焚烧厂选址问题的双目标规划模型,通过一个具体算例验证了模型的有效性,得到了符合实际的结果.模型可推广应用于其它邻避型设施选址问题.     

油库选址决策的二层优化模型研究

油库物流设施的选址决策属于战略管理层的决策,它是整个物流系统运作的基础.油库的选址决策是库存和运输决策的基础,库存决策和运输决策则是在整个油品配送系统规划框架内对油库选址决策的完善和延伸.如何进行科学的油库选址是企业所关心的问题.本文将在考虑影响选址的定性成本因素以及运营过程中的非成本因素、定性和定量相结合的基础上利用多层决策理论,将油库选址问题归结为一个二层优化模型,并提出了确定理想选址区域和可行点的相关方法的计算方法.数值实验表明该算法是可行的.本文的结论对实际决策问题具有一定的借鉴作用.     

邮政运输网络中的邮路规划和邮车调度

本题是一道VRP问题,它涉及到最短路线、最小费用等条件下的优化问题.问题一中,我们论证出最少需要3辆邮车才能满足要求.然后对C1区域根据装载量、时间要求遍历出所有的可行路线,最后选出因空车率而减小的收入最小的邮路,其减少的收入为49.35元.问题二中,将整个区域进行划分,在每个小区域应用分枝定界法求出运行成本的路线.再通过对区域的微调讨论出使邮车数目更小的、更节省运行成本的邮路规划方案.问题三中,由于我们将Z55,Z57由县局X1负责运送,Z27由县局X2负责运送.问题四是一个选址问题.我们借助于中心点算法,考虑各支局在本县区域内的位置,并结合与地市局的距离,提出了相应的选址方案.     

存在三重属性节点的物流网络选址分配问题研究

文章分析了一种存在三种属性节点的物流网络,即在该网络中存在一类节点同时承担供应、需求和中转的功能。同时,还考虑了在任意两节点间单位运费可变条件下,如何进行中转点选址和流量分配,使物流网络的运输费用最小。在此背景下建立了选址分配优化模型,设计出一种将串形编码和矩阵编码相结合的两层遗传算法对其进行求解,并通过一个实例对算法加以验证并对求解结果进行分析。研究结果表明:相比于一般的需求点就近分配原则,本文提出的基于产品流进行的物流网络选址与分配模型,能够避免某些运输线路上的过度集货的现象,从而进一步降低整个物流网络的运输费用。     

区际救援物资中转调度的动态决策模型与算法

考虑灾害救援中灾区对应急物资的持续消耗,研究了区际多品种救援物资的动态中转调度问题.综合考虑各阶段调度费用、运输费用和库存费用总和最小化的救援物资中转调度安排和库存规划,建立了一个区际救援物资中转调度动态决策模型,并设计了一种矩阵编码的协进化遗传算法.最后通过一个算例验证了模型和算法的有效性.     

求解GPRs条件下的项目最小费用问题

在项目管理中,最低成本是主要目标之一,也是求解诸如时间-费用权衡等相关问题时必备的起始点,通常只需令各工序选用费用最低的工期即可.但是当工序之间存在一般优先关系(简称GPRs)时,各工序选用费用最低的工期往往无法满足时间约束,使得项目不可行,因此需要考虑其它费用较高的工期.针对如何在满足GPRs条件下使项目成本最低,首先,通过分析GPRs网络的特点,建立了GPRs网络的最小费用模型;其次,对模型进行对偶变换,等效转化为最小费用流模型,其特点是,除了与起点或终点连接的弧,其余均没有容量限制.当前已有的算法能够有效求解该模型,并跟据其最优解可求得原问题的最优解.     

考虑乘客时间成本与换乘感受的中转航班登机口分配问题研究

针对2018年"华为杯"第十五届中国研究生数学建模竞赛F题展开研究对考虑乘客时间成本与换乘感受的中转航班登机口分配调度问题(Airport Gate Assignment Problem,AGAP)进行研究,建立了多目标0-1整数线性规划的中转航班登机口分配模型.根据不同的实际应用条件,对该模型进行相应改进,并使用Lingo求解,得出在最大化航班分配数量的基础上,最小化乘客换乘成本,同时尽量减少登机口使用数量的最优中转航班登机口分配方案,最后对分配结果进行分析.模型亮点在于:1)创新性地引入了乘客换乘成本惩罚因子,令模型对实际问题考虑更加全面.2)模型在时间离散化的基础上,将航班间隔时间纳入航班占用时间,建立了0-1整数线性规划模型求最优解,求解结果更加可靠.3)模型通过线性加权的方法,将多目标规划问题简化为单目标问题进行建模.     

双会议服务器选址问题研究

中位选址问题一直是管理学科的研究热点,本文考虑平面点集选址问题中的双会议服务器选址问题,该问题可以看成是2中位问题的衍生问题。令P为平面上包含n个点的点集,双会议服务器选址问题即为寻找由该点集构成的一棵二星树,使得这棵树上所有叶子之间的距离和最小。本文给出求解该问题的关键几何结构和最优解算法设计,并证明所给算法时间复杂性为O(n³logn)。     

Global optimization of a nonconvex single facility location problem by sequential unconstrained convex minimization

The problem of maximizing the sum of certain composite functions, where each term is the composition of a convex decreasing function, bounded from below, with a convex function having compact level sets arises in certain single facility location problems with gauge distance functions. We show that this problem is equivalent to a convex maximization problem over a compact convex set and develop a specialized polyhedral annexation procedure to find a global solution for the case when the inside function is a polyhedral norm. As the problem was solved recently only for local solutions, this paper offers an algorithm for finding a global solution. Implementation and testing are not treated in this short communication.An earlier version of this paper appeared in the proceedings of a conference on Recent Advances in Global Optimization, C. Floudas and P. Pardalos, eds., Princeton University Press, 1991.     

The transfer point location problem

In this paper, we introduce the transfer point location problem. Demand for emergency service is generated at a set of demand points who need the services of a central facility (such as a hospital). Patients are transferred to a helicopter pad (transfer point) at normal speed, and from there they are transferred to the facility at increased speed. The general model involves the location of p helicopter pads and one facility. In this paper, we solve the special case where the location of the facility is known and the best location of one transfer point that serves a set of demand points is sought. Both minisum and minimax versions of the models are investigated. In follow up papers we investigate the general model using the results obtained in this paper.     

The multiple location of transfer points

In this paper, we investigate the location of several transfer points to serve as collector points for customers who need the services of a facility. For example, demand for emergency services by patients is generated at a set of demand points that need the services of a central facility (such as a hospital). Patients are transferred to a helicopter pad (transfer point) at normal speed, and from there they are transferred to the facility at increased speed. The general model involves the location of multiple transfer points and one facility. Locating one transfer point when the set of demand points and the location of the facility are known was investigated in a previous paper by the authors. In this paper, we apply the results of that paper to solve the problem when the location of the facility is known. Both minisum and minimax versions of the models are investigated both in the plane and on the network.     

柯西分布的参数估计

研究了柯西分布的参数估计问题,给出了位置参数的最小一乘估计和尺度参数的低阶矩估计.证明了柯西分布位置参数的最小一乘估计具有渐近无偏性与强相合性;尺度参数的低阶矩估计具有强相合性.     

On Data-Driven Computation of Information Transfer for Causal Inference in Discrete-Time Dynamical Systems

In this paper, we provide a novel approach to capture causal interaction in a dynamical system from time series data. In Sinha and Vaidya (in: IEEE conference on decision and control, pp 7329–7334, 2016), we have shown that the existing measures of information transfer, namely directed information, Granger causality and transfer entropy, fail to capture the causal interaction in a dynamical system and proposed a new definition of information transfer that captures direct causal interactions. The novelty of the information transfer definition used in this paper is the fact that it can differentiate between direct and indirect influences Sinha and Vaidya (2016). The main contribution of this paper is to show that the proposed definition of information transfers in Sinha and Vaidya (2016) and Sinha and Vaidya (in: Indian control conference, pp 303–308, 2017) can be computed from time series data, and thus, the direct influences in a dynamical system can be identified from time series data. We use transfer operator theoretic framework, involving Perron–Frobenius and Koopman operators for the data-driven approximation of the system dynamics and computation of information transfer. Several examples, involving linear and nonlinear system dynamics, are presented to verify the efficiency of the developed algorithm.

     

Open problems

One of the most fruitful activities that takes place at a conference is the interchange of problems. Often, in later years the success of a conference may be judged by the number of problems raised there which are eventually solved. The papers in the remainder of this volume contain several problems, but here are some more that did not fit naturally into any of those papers. I hope to see solutions of at least some of these problems in the pages of Positivity in years to come.     

Coal bank scheduling using a mathematical programming model

Coals are extracted from mines and upgraded on the surface for customers. The upgraded coals must be aged at least four weeks in a bank before being supplied to customers. Different sizes of banks are required for different lengths of time at different points in time. Bigger banks increase the floor space capacity and reduce handling costs. The proper location of banks reduces the total space requirement and bank movement after building. In this paper, we address the bank size and location problem and solve it by using a mathematical programming approach.     

A Newton Acceleration of the Weiszfeld Algorithm for Minimizing the Sum of Euclidean Distances

The Weiszfeld algorithm for continuous location problems can be considered as an iteratively reweighted least squares method. It generally exhibits linear convergence. In this paper, a Newton algorithm with similar simplicity is proposed to solve a continuous multifacility location problem with the Euclidean distance measure. Similar to the Weiszfeld algorithm, the main computation can be solving a weighted least squares problem at each iteration. A Cholesky factorization of a symmetric positive definite band matrix, typically with a small band width (e.g., a band width of two for a Euclidean location problem on a plane) is performed. This new algorithm can be regarded as a Newton acceleration to the Weiszfeld algorithm with fast global and local convergence. The simplicity and efficiency of the proposed algorithm makes it particularly suitable for large-scale Euclidean location problems and parallel implementation. Computational experience suggests that the proposed algorithm often performs well in the absence of the linear independence or strict complementarity assumption. In addition, the proposed algorithm is proven to be globally convergent under similar assumptions for the Weiszfeld algorithm. Although local convergence analysis is still under investigation, computation results suggest that it is typically superlinearly convergent.     

The p/q-active uncapacitated facility location problem: Investigation of the solution space and an LP-fitting heuristic

The p/q-active uncapacitated facility location problem is the problem of locating p facilities on n possible sites each serving at least q of the m clients at the minimum cost. The problem is an extension of the uncapacitated facility location problem (UFL) where constraints on the number of facilities and their minimum activity have been added. A use of this formulation could be the opening of p new schools where each must have at least q pupils. p/q-active is NP-hard like the UFL.