废弃物收运网络周期性选址-路径问题多目标优化模型及算法

废弃物处理设施是典型的"Semi-desirable"设施, 其选址相关的决策需要考虑成本、负效应等多个相互冲突的目标. 废弃物中转站的选址和路径优化是一类周期性选址-路径问题(PLRP), 目前缺乏对这类问题的多目标优化的研究. 以多目标城市废弃物收运网络周期性选址-路径问题为研究对象, 提出基于扩散距离的负效应测度方法; 建立考虑负效应和成本的双目标混合整数规划模型; 设计DRECWA-LS算法, 结合启发式优化策略, 求解收运计划对应的周期性选址-路径问题, 并采用扩展邻域搜索策略的多目标进化算法实现对可行收运计划的深度搜索, 同步求解收运计划、中转站选址-分配及车辆路径三个问题. 算例结果显示: 算法能成功求解较大规模问题, 具有较高的求解质量和运算效率.     

Multi-facility ordered median problems in directed networks

This paper uses a finite dominating set (FDS) to investigate the multi-facility ordered median problem (OMP) in a strongly connected directed network. The authors first prove that the multi-facility OMP has an FDS in the node set, which not only generalizes the FDS result provided by Kalcsics, et al. (2002), but also extends the FDS result from the single-facility case to the multiple case, filling an important gap. Then, based on this FDS result, the authors develop an exact algorithm to solve the problem. However, if the number of facilities is large, it is not practical to find the optimal solution, because the multi-facility OMP in directed networks is NP-hard. Hence, we present a constant-approximation algorithm for the p-median problem in directed networks. Finally, we pose an open problem for future research.     

能力限制条件下内河集装箱枢纽港选址问题研究:以长江为例

相比于海洋运输,内河运输中集装箱船舶较小,船舶装载能力受到一定的限制.本文研究能力限制条件下内河集装箱枢纽港选址问题,建立一个混合整数非线性规划模型.不同于传统的枢纽选址问题的研究大多是基于枢纽之间的运输折扣因子的假设,本文采用基于流量的非线性费用函数来表示规模经济.从而使得所研究的问题是一个凹函数优化问题.为简化本文的问题,将目标函数分段线性化.基于线性化后的模型,根据能力限制的条件,提出一个启发式求解算法,以及一个加速技巧.最后,通过以长江为例,进行算例分析,来说明模型和算法的效果.     

CONVEXIFICATION AND CONCAVIFICATION METHODS FOR SOME GLOBAL OPTIMIZATION PROBLEMS

In this paper, firstly, we propose several convexification and concavification transformations to convert a strictly monotone function into a convex or concave function, then we propose several convexification and concavification transformations to convert a non-convex and non-concave objective function into a convex or concave function in the programming problems with convex or concave constraint functions, and propose several convexification and concavification transformations to convert a non-monotone objective function into a convex or concave function in some programming problems with strictly monotone constraint functions. Finally, we prove that the original programming problem can be converted into an equivalent concave minimization problem, or reverse convex programming problem or canonical D.C. programming problem. Then the global optimal solution of the original problem can be obtained by solving the converted concave minimization problem, or reverse convex programming problem or canonical D.C     

VTS雷达及岸基溢油雷达组合选址优化

针对实际建址时存在障碍物遮挡和雷达传递衰减的船舶交通管理系统（Vessel Traffic Service，VTS）雷达及岸基溢油雷达组合选址问题，基于空间几何方法，在三维空间中提出了障碍物遮挡判断方法，并引入衰减函数进行雷达衰减测度，以建站成本最小和水域面积覆盖率最大为目标建立多目标选址模型。根据问题设计了自适应混沌多目标粒子群算法，在满足位置约束时生成初始解，提高算法求解速度；引入混沌机制和飞蛾火焰算法的螺旋搜索机制对粒子速度及位置更新策略进行改进，增强算法的局部和全局搜索能力。通过算例验证了本文所提出的判断方法及模型的有效性。研究成果不仅深化和拓展了VTS雷达选址及溢油问题的相关研究，也为海事主管机构在进行VTS雷达站及溢油雷达选址时提供理论依据。     

一类带容量限制的服务站选址问题

分析一类在交通网络中设立服务站的最优选址问题。在给定的网络G(V，A)中有r对O-D用户流，我们在总的建站费用最小的目标下考虑下面三个因素：①每对用户流都能得到服务；②每对用户流所走的总路程不超过某一给定的距离；③每个服务站的服务能力是有限制的。在分析这类问题的特征后，我们形成了一个线性混合整数规划模型，并给出求解实例。     

带有空间公平性约束的换乘停车场布局双目标规划模型

为规划城市交通网络中换乘停车场的布局,建立了带有空间公平性约束的双目标规划模型,目标分别为换乘停车场的客流量最大和建立换乘停车场的成本最少. 提出了单位成本客流量的概念,将原问题转化为含参数的单目标问题求解,分析了模型解的性质,并给出了单位成本客流量在参数 的不同区间上的函数增减性以及上下界. 模型应用在Anaheim市的交通路网中. 该研究为换乘停车场 的投资方从成本-收益角度评价建设方案提供决策支持,对城市交通部门进行换乘停车场的布局规划 具有理论指导意义.     

Budget constrained flow interception location model for congested systems

To study location problems with congestion demand, a bi-objective model based on flow interception problem is proposed. The model is formulated from the view of M/M/m queuing systems. Service quantity and quality are simultaneously considered as objectives, with constraint on total cost. Service quality includes deviation distance from preplanned trips and customers’ waiting time. Service quantity is the number of interception customers. A multi-objective evolutionary algorithm combined with greedy heuristic is proposed. Finally a computational experiment is given, and the algorithm is proved to be efficient.     

损毁情景下应急设施选址的多目标决策方法

应急设施选址问题是应急管理中的重要问题,设施的长期战略性地位,促使决策者在进行选址决策时关注多种目标.在一定的经济投入条件下,本文首先提出了决策者制定设施选址方案时的目标原则,构建以时效性、均衡性和鲁棒性为核心的评价体系,进而建立了应急设施选址的多目标优化模型,用覆盖为目标的救援总时间反映时效性,最大救援半径反映均衡性,以及设施损毁情景下额外增加的救援变更时间反映鲁棒性,用三个目标函数组成的三元组刻画选址决策的目标向量,理想点是一个三元向量,每一个分量值表示只以这个分量目标函数求解得到的最优值,提出了基于理想点的目标扰动最小化模型,并采用遗传算法设计求解方法,通过算例分析了模型和算法的有效性,说明本文提出的模型与算法在解决应急设施选址决策方面具有一定的应用价值.     

Some inverse optimization problems on network

In this paper, the authors consider some inverse problems on network, such as the inverse transport problems with gains (IGTP) and the inverse linear fractional minimum cost flow problem (IFFP). Firstly, the authors give the mathematics model of (IGTP) and an efficient method of solving it under l ₁ norm; Secondly, taking advantage of the optimality conditions, the authors consider the (IFFP) and give a simple method of solving it. Finally, an numerical example test is also developed.     

基于“情景-应对”的国家应急平台体系基础科学问题与集成平台

基金委"非常规突发事件应急管理研究"重大研究计划集成项目直接面向和紧密围绕重大研究计划的总体目标从两方面开展研究: 提升现有国家应急平台体系科学性的多学科融合的基础研究; 相关研究成果的集成升华和与国家应急平台体系的"对接". 具体包括: 突发事件应急场景下数据集成、组织与存储、数据共享方法研究; 面向应急辅助决策的定量与定性相结合的案例分析与集成管理方法; 网络分布式多模型环境下的智能化应急处置决策模型库构建方法; 个体和群体在紧急状态下的心理反应与行为规律; 面向"情景-应对"型决策、与国家应急平台体系相融合的应急管理开放式集成研究平台设计与构建; 基于集成平台的突发事件情景推演与决策过程模拟仿真与集成应用示例. 提出"数据融合-模型推演-案例推理-心理行为规律"综合集成的"情景-应对"型应急决策理论和方法; 构建基于"网络集成-计算集成-应用系统集成"三层交互的, 与国家应急平台体系相融合的, 跨学科、跨地域协作共享的"交响"式应急管理开放集成研究平台.     

工程项目工期-成本-质量均衡优化

工程项目管理的重要内容之一就是对工程工期、成本、质量等目标进行综合均衡控制,而这三者又是相互关联的矛盾对立统一体,即三大目标中任一目标的增强必然以牺牲其他目标为代价。本文在对比分析了现有文献中关于质量问题的多目标优化模型——质量成本模型、质量可靠度模型、工期-质量曲线模型、赢得值模型等的基础上,提出了基于网络系统可靠度的质量模型,进而改进了工程项目工期-成本-质量三者的均衡优化模型,最后运用该模型对一个工程实例进行优化。在优化过程中,本文采用了基于免疫遗传的微粒群算法(IGPSO),优化结果证明了该模型的可行性和有效性,为项目管理者提供了有效的决策支持。     

直线上的双旅行售货员位置问题

旅行售货员位置问题在组合优化中是非常困难的问题之一,由于它的困难（它涉及到族行售货员问题和位置问题双重问题）这个问题一直引起人们极大关注,然而多于一人的旅行售货员问题还没有去探讨。本文提出一个复杂度为Ｏ（ｎ４）的算法解决直线上的双旅行售货员位置问题     

设施拥堵状态下的层次性备用覆盖网络模型与改进遗传算法

经典的分层覆盖位置问题(HCLP)是在有限预算内找到设施位置以提供分层服务的问题.这个过程中,需求点的差异化服务需求可以来自层次型网络中不同服务可用性的设施.我们设计了混合服务可用性的层次型网络,通过讨论层次型设施数量为定量和变量的情况构建混合层次网络备用覆盖问题的整数规划模型,并设计、改进元启发式算法来求解问题.结果表明考虑变量的混合服务可用性的优化模型在一次覆盖中能更好的满足客户的需求,而其备用覆盖能力和系统造价并非始终优于单类型层次网络;建议的启发式算法在合理的计算时间内产生高质量的解.     

证据网络模型及其推理算法

本文在证据理论与图模型研究的基础上,针对不确定性与关联性相结合的系统建模问题,提出并建立了证据网络模型,定义了证据网络的参数,总结了证据网络的建模特点;分析了证据网络模型的推理问题,建立了其推理策略和推理过程,推导出其正向推理算法和反向推理算法,并通过示例进行了计算验证;证据网络模型将为管理决策分析、系统工程管理等领域的问题分析和求解提供一种有效的技术方法支持.     

网络运输价格性质研究

为解决动态定价中价格数据的理论依据问题,根据最大凹向包络理论,在界定有关概念、推导相关定理的基础上,对网络运输中各旅行区段的价格性质进行拓展研究,探讨各区段给定价格集合与最优价格之间的联系,进行算例分析,为网络运输区段价格的制订提供新的研究途径.     

Solving DCLAP-MSN based on hybrid genetic algorithm

The dynamic capacitated location allocation problem in the military supportive network (DCLAP-MSN) is a representative of combinative optimization problems, and its optimization process is complicated. For this reason, a dynamic capacitated location allocation model is provided firstly. Then, a hybrid heuristic algorithm which combines genetic algorithm, repair algorithm of solutions and greedy search, is proposed as the solving method.The optimization performance is improved by effectively integrating the repair algorithm of solutions and greedy search with genetic optimization. The experiment results indicate that the proposed algorithm is a feasible and effective method for the problem.     

On-Line Scheduling on Parallel Machines to Minimize the Makespan

This paper considers two parallel machine scheduling problems,where the objectives of both problems are to minimize the makespan,and the jobs arrive over time,on two uniform machines with speeds 1 and s(s≥1),and on m identical machines,respectively.For the first problem,the authors show that the on-line LPT algorithm has a competitive ratio of(1 +5~(1/2))/2≈1.6180 and the bound is tight.Furthermore,the authors prove that the on-line LPT algorithm has the best possible competitive ratio if s≥1.8020.For the second problem,the authors present a lower bound of(15-(17)~(1/2))/8≈1.3596 on the competitive ratio of any deterministic on-line algorithm.This improves a previous result of 1.3473.     

ROW-ACTION METHODS FOR CONVEX QUADRATIC PROGRAMMING

ＲＯＷ－ＡＣＴＩＯＮＭＥＴＨＯＤＳＦＯＲＣＯＮＶＥＸＱＵＡＤＲＡＴＩＣＰＲＯＧＲＡＭＭＩＮＧＧＵＯＴｉａｎｄｅ（ＭａｔｈｅｍａｔｉｃｓＤｅｐａｒｔｍｅｎｔｏｆＱｕｆｕＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｑｕｆｕ，Ｓｈａｎｄｏｎｇ２７３１６５，Ｃｈｉｎａ...     

无向正权网络最短路模型的建立和理论分析

路径问题是运筹学的重要分支, 更是图论学科成立的奠基问题.针对无向网络中的路径问题, 首先, 建立了无向正权网络最短路模型, 提出一些能够反映无向网络中节点、边和路线规律性的参数概念, 包括点参数和边参数, 用这些参数代替边的权数描述无向正权网络; 其次, 通过对模型进行理论分析, 推导出与各参数相关的结论, 利用参数揭示了点、边、路线以及无向正权网络之间的关系, 并初步体现了该模型的用途; 第三, 利用该模型求解了与无向正权网络相关的几类基本路径问题; 最后, 通过应用举例, 阐述了该模型的部分应用. 需注意的是, 该模型也适用于带回路的有向正权网络.