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.     

Probabilistic Formulation of the Emergency Service Location Problem

The problem of locating emergency service facilities is studied under the assumption that the locations of incidents (accidents, fires, or customers) are random variables. The probability distribution for rectilinear travel time between a new facility location and the random location of the incident P _i is developed for the case of P _i being uniformly distributed over a rectangular region. The location problem is considered in a discrete space. A deterministic formulation is obtained and recognized to be a set cover problem. Probabilistic variation of the central facility location problem is also presented.An example and some computational experience are provided to emphasize the impact of the probabilistic formulation on the location decision.     

求解无容量设施选址问题的拉格朗日蝙蝠算法

无容量设施选址问题(Uncapacitated Facility Location Problem,UFLP)是一类经典的组合优化问题,被证明是一种NP-hard问题,易于描述却难于求解.首先根据UFLP的数学模型及其具体特征,重新设计了蝙蝠算法的操作算子,给出了求解UFLP的蝙蝠算法.其次构建出三种可行化方法,并将其与求解UFLP的蝙蝠算法和拉格朗日松弛算法相结合,设计了求解该问题的拉格朗日蝙蝠算法.最后通过仿真实例和与其他算法进行比较的方式,验证了该混合算法用来求解UFLP的可行性,是解决离散型问题的一种有效方式.     

基于一类光滑函数法求解选址问题

选址问题是组合优化中一类有着重要理论意义和广泛实际背景的问题.在利用数学模型解决这类问题时经常会遇到非线性L_1问题,也就是不可微优化问题.为了解决这类问题,构造了适合于选址问题的一类新的光滑函数,并对这类光滑函数进行了性质描述,然后在此基础上提出了基于有效集法进行优化求解的计算步骤.最后,以实例证明了这类光滑函数应用在选址问题的优化求解上是有效的.     

改进的布谷鸟算法求解物流配送中心选址问题

针对基本布谷鸟算法求解物流配送中心选址问题时存在搜索精度低、易陷入局部最优值的缺陷,提出一种改进的布谷鸟算法.算法采用基于寄生巢适应度值排序的自适应方法改进基本布谷鸟算法的惯性权重,以平衡算法的全局开发能力和局部探索能力;利用NEH领域搜索以提高算法的搜索精度和收敛速度;引入停止阻止策略对全局最优寄生巢位置进行变异避免算法陷入局部最优值、增加种群的多样性.通过实验仿真表明,改进的布谷鸟算法在求解物流配送中心选址问题上要优与基本布谷鸟算法以及其它智群算法,是一种有效的算法.     

基于时间满意度的应急物资储备库选址问题

基于应急物资配送过程中时间因素的重要性,将时间满意度引人应急物资储备库选址问题中.针对时间满意度为线性分段函数,建立了以时间满意度最小的需求点的时间满意度尽量大以及系统总费用最小为目标的双目标混合整数规划模型,对目标函数的最小最大值问题进行转化,在此基础上构造新的优化模型,并设计了相应的启发式算法求解.最后通过算例说明算法的可行性和有效性.     

Solving a Bicriteria Problem of Optimal Service Centers Location

The problem of service centers location is formulated as a bicriteria optimization problem of finding a dominating set in graph. We investigate the properties of this problem and propose the methods for its solving. The results of computational experiment for instances with random data are presented.     

Developing Interdisciplinary Units: A Strategy Based on Problem Solving

While the benefits of the interdisciplinary unit are well documented, it presents a complex challenge to teachers in the natural and social sciences, mathematics, and humanities. Teachers must become active curriculum designers who shape and edit the curriculum according to students' needs. This paper describes knowledge for teachers as curriculum designers and a framework for interdisciplinary unit development. The framework addresses a metacurricular process (problem solving) that will be the unit centerpiece, the development of this central process related to the learner, and the tasks that teach explicit learning and thinking skills attached to the central process. An example of the framework in action is also described. As the faculty and curriculum coordinators for an innovative summer academy for minority students in northern Arizona have used this framework, they have evolved from a group that created a good idea to interest students with parallel subject development in separate classrooms to humanities/mathematics/science teams united in one team/classroom, in which content is integrated through the actions of the problem solving process.     

基于失效情景的应急设施选址问题

非常规突发事件巨大的破坏力以及发生时间、地点和规模的不确定性,使应急系统内设施有可能被破坏而失效,因此选址时必须考虑设施失效情景的发生.给出以最大限度覆盖用户需求为目标,基于失效设施数目具有不确定性情景的设施选址双层随机规划模型;通过计算模型上下界,给出减小规模的等价模型,降低了双层规划求解难度;最后实验验证了模型的合理性,并给出新增选址方案.     

Solving the Simple Plant Location Problem using a Data Correcting Approach

The Data Correcting Algorithm is a branch and bound type algorithm in which the data of a given problem instance is `corrected' at each branching in such a way that the new instance will be as close as possible to a polynomially solvable instance and the result satisfies an acceptable accuracy (the difference between optimal and current solution). In this paper the data correcting algorithm is applied to determining exact and approximate optimal solutions to the simple plant location problem. Implementations of the algorithm are based on a pseudo-Boolean representation of the goal function of this problem, and a new reduction rule. We study the efficiency of the data correcting approach using two different bounds, the Khachaturov-Minoux bound and the Erlenkotter bound. We present computational results on several benchmark instances, which confirm the efficiency of the data-correcting approach.     

Solving a bi-objective Transportation Location Routing Problem by metaheuristic algorithms

In this work we consider a Transportation Location Routing Problem (TLRP) that can be seen as an extension of the two stage Location Routing Problem, in which the first stage corresponds to a transportation problem with truck capacity. Two objectives are considered in this research, reduction of distribution cost and balance of workloads for drivers in the routing stage. Here, we present a mathematical formulation for the bi-objective TLRP and propose a new representation for the TLRP based on priorities. This representation lets us manage the problem easily and reduces the computational effort, plus, it is suitable to be used with both local search based and evolutionary approaches. In order to demonstrate its efficiency, it was implemented in two metaheuristic solution algorithms based on the Scatter Tabu Search Procedure for Non-Linear Multiobjective Optimization (SSPMO) and on the Non-dominated Sorting Genetic Algorithm II (NSGA-II) strategies. Computational experiments showed efficient results in solution quality and computing time.     

应急资源调度问题的改进进化规划算法研究

针对应急资源调度问题,建立一种多资源时间-成本调度模型。设计了进化规划算法的全局变异算子和局部变异算子,根据全局变异前后个体适应度值和分量值的变化趋势,实现定向变异。构建了具有惩罚系数的适应度函数,给出了改进的进化规划算法种群进化策略。计算实验表明,改进的进化规划算法具有较强的局部寻优能力,在收敛速度和求解精度方面优于比较的遗传算法、差分进化算法和进化规划算法,解决了标准进化算法的早熟收敛问题。     

运筹学中几种运输问题的求解方法探析

从目前研究生入学考试中出现的几种新的运筹学运输问题出发,探讨了各种运输问题与传统运输问题的差异。提出以传统运输问题为本,将非传统运输问题转化为传统运输问题借助表上作业法求解的思路。并针对6种不同的非传统运输问题分析了转化的过程和步骤,为运输问题的研究提供了新的内容.     

一类应急服务设施选址问题的模型及算法

在分析城市应急服务设施选址问题基础上,建立了限定期条件下应急服务设施选址问题的数学模型,提出了一种基于遗传算法的应急服务设施选址模型的有效算法,并通过算例分析验证了该方法的有效性.     

考虑绕行特征的电动汽车快速充电站选址问题及自适应遗传算法

快速充电站选址是电动汽车运营的重要内容之一。本文考虑电动汽车用户会通过绕行一定距离对车辆进行充电这一特征,建立了一个以电动汽车快速充电站建站成本和旅客整体绕行成本之和最小的双层整数规划模型。本文首先给出了用于生成绕行路径集合的A^*算法,然后设计了一种包含局部迭代搜索的自适应遗传算法对该模型进行求解。为了测试算法性能,通过两个不同规模的算例图与已有求解FPLM问题的遗传算法进行了比较,数值试验部分证明了算法的正确性和有效性。最后引入浙江省的高速路网图,从建站成本和截流量两方面对电池续航里程带来的影响进行了相关的灵敏度分析。     

基于人工蜂群算法的配送中心选址问题求解

采用人工蜂群算法对配送中心选址问题进行求解,给出食物源的编码方法,通过整数规范化,使算法能在整数空间内对问题进行求解.应用算法进行了仿真实验,并将结果与其它一些启发式算法进行了比较和分析.计算结果表明人工蜂群算法可以有效求解配送中心选址问题,同时也为算法求解其它一些组合优化问题提供了有益思路.     

A Plan for Problem Solving

<正>In mathematics,you often encounter some difficult problem.When solving math problems,it is often helpful to have an organized problem-solving plan.Today we will talk about"A Plan for Problem Solving"When solving math problems,the four steps listed below can be used to solve any problem.1.Explore·Read the problem carefully.·What facts do you know?·What do you need to find out?·Is enough information given?·Is there extra information?2.Plan·How do the facts relate to each other?·Plan a strategy for solving the problem.