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

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

基于两阶段启发式算法的物流配送选址-路径问题研究

为了解决配送中心选址与带时间窗的多中心车辆路径优化组合决策问题,利用双层规划法建立了配送中心选址与车辆路径安排的多目标整数规划模型,针对该模型的特点,采用两阶段启发式算法进行了求解。首先,通过基于聚集度的启发式算法对客户进行分类,确定了备选配送中心的服务范围;然后,基于双层规划法,以配送中心选址成本最小作为上层规划目标,以车辆配送成本最小作为下层规划目标,建立了多目标整数规划模型;最后,利用改进的蚁群算法进行了求解。通过分析实例数据和Barreto Benchmark算例的实验结果,验证了该模型的有效性和可行性。     

一类带单源约束的选址运输问题算法研究

带单源约束的选址运输问题是在经典的选址运输问题基础上考虑每个顾客需求的产品仅由一家工厂供应的情况。所建立的模型是整数规划，是NP难的。本文先考虑了开办费用为零的带单源约束的选址运输问题，即带单源约束的运输问题。松弛其中一种变量约束，借鉴求解运输问题的表上作业法，给出了一种修正的表上作业法，然后将算法推广。最后给出了将算法应用在Excel随机生成的测试问题上所得到的结果，与LINDO求得的最优解相比，差距很小。由此得出结论：对规模较小的带单源约束的选址运输问题，本文提出的算法是简便且行之有效的。     

生鲜农产品多配送中心连续选址FCM-ISA算法及应用

本文对生鲜农产品多配送中心连续选址问题进行了研究,在建立考虑最小距离约束下连续选址模型的基础上,针对以往连续选址模型求解过程中采用随机方式生成初始解会造成算法搜索范围过大且易陷入局部最优的局限,创新性地提出了连续选址模型的模糊C均值聚类-改进模拟退火(FCM-ISA)算法,并以杭州市为例验证了所建模型及设计算法的有效性。计算结果表明,本文所建立的生鲜农产品多配送中心连续选址模型更符合实际选址情景,设计的FCM-ISA算法收敛速度快且全局寻优效果好,对科学地进行生鲜农产品多配送中心选址决策具有重要的指导意义。     

多阶响应下军事物流配送中心可靠选址模型

为了提高战时物资配送的敏捷性和可靠性,结合军事物资配送的多阶响应过程,以部队用户对配送响应的时间约束为限制条件,以设施固定成本与期望配送成本之和为目标函数,并考虑设施未来失效的可能,建立了混合整数规划形式的军事物流配送中心可靠选址模型.结合模型的特点,采用基于时间约束的启发式算法将模型转化为可行子问题进行求解,使用仿真算例说明模型的优越性和算法的有效性.与不考虑设施失效的选址模型相比,考虑设施失效的选址方案在出现设施失效时,其应急配送成本平均增加量基本不超过设施固定成本的20％,平均最大增加量不超过25％;同一种失效情景下,考虑设施失效的选址方案的应急配送总成本也明显小于不考虑设施失效的选址方案的总成本.     

基于精英单亲遗传算法的冷链物流VRP模型优化研究

针对冷链物流配送的特殊性,探索冷链物流车辆路径问题(VRP)优化方案.首先,在保证货物不超载的条件下,建立基于时间和品质因素的顾客满意度约束的多配送中心VRP(MDVRP)模型;其次,采用重心分区法和改进的精英单亲遗传算法,求解顾客在配送中心的分配,确定配送车辆数以及顾客服务次序;最后,用Matlab工具编程对模型进行求解分析.结果表明构建基于满意度的冷链物流MDVRP模型更适合冷链物流配送最优路径选择,并且改进单亲遗传算法能够有效求解这类问题.     

带覆盖需求约束的设施选址问题

带覆盖需求约束的设施选址问题(FLPWCDL)研究:客户必须在规定的响应半径内被服务,并要求服务站能够覆盖规定的需求数量,如何选择合适的服务站,使总成本(建站成本+路线成本)最小.FLPWCDL广泛应用于应急服务、物流、便利店等服务站的选址.建立了问题的混合整数规划模型,并构造了求解FLPWCDL的Benders分解算法,计算实验显示Benders分解算法具有非常高的求解效率与求解质量.     

基于网格化管理视角下灾后应急物流决策模型与算法研究

灾害发生后,应急资源的需求预测与应急配送中心的合理选址是实现高效救援的关键。本文通过在网格化管理视角下的信息更新将应急救援过程划分为多个阶段,在开展救援的过程中实现救援信息收集和救援预测的同步开展,建立一种多阶段带时间约束的应急救援物资配送响应-时效性的选址模型。借助遗传算法(NSGA-II),实现了基于编码结构独立、路径相互关联基础上的多目标规划求解。本研究的决策模型及算法有着较好的搜索与寻优能力,对实际救援开展具有指导意义。     

带退货和软时间窗的多仓库选址-路径问题研究

选址-路径问题(location routing problems, LRP)是集成物流网络研究中的难题,也是任何一个大型物流配送企业必须面对的管理决策问题。本文在仓库容量约束和车辆容量约束的基础上,结合送取货一体化的配送模式和客户服务时间要求,建立了带退货和软时间窗的多仓库选址-路径(MDLRP)数学模型。针对MDLRP问题求解的复杂性,引入局部搜索算法和重组策略,设计了自适应混合遗传算法,对模型进行整体求解。最后进行数值实验,表明本文提出的模型和改进算法具有实用性和优越性,可为选址和车辆运输决策提供重要参考依据。     

基于可变建设成本的风险共担选址—库存模型研究

在固定建设成本风险共担选址-库存问题(Location model of risk pooling,LMRP)研究基础上,本文从优化角度将配送中心建设成本设为配送中心规模的线性函数,将模型扩展为可变建设成本风险共担选址—库存问题(Location model of risk pooling based on variable construction cost,LMRPVCC),构建非线性0-1整数规划模型。采用启发式粒子群算法求解模型,对经典文献算例进行测算,并依据计算结果,对影响模型目标值的相关参数进行敏感性分析。     

Lagrangian heuristics for the two-echelon,single-source,capacitated facility location problem

Facility location problems form an important class of integer programming problems, with application in the distribution and transportation industries. In this paper we are concerned with a particular type of facility location problem in which there exist two echelons of facilities. Each facility in the second echelon has limited capacity and can be supplied by only one facility (or depot) in the first echelon. Each customer is serviced by only one facility in the second echelon. The number and location of facilities in both echelons together with the allocation of customers to the second-echelon facilities are to be determined simultaneously. We propose a mathematical model for this problem and consider six heuristics based on Lagrangian relaxation for its solution. To solve the dual problem we make use of a subgradient optimization procedure. We present numerical results for a large suite of test problems. These indicate that the lower-bounds obtained from some relaxations have a duality gap which frequently is one third of the one obtained from traditional linear programming relaxation. Furthermore, the overall solution time for the heuristics are less than the time to solve the LP relaxation.     

Pareto optimality and a class of set covering heuristics

The set covering problem has many diverse applications to problems arising in crew scheduling, facility location and other business areas. Since the problem is known to be hard to solve optimally, a number of approximate (heuristic) approaches have been designed for it. These approaches (with one exception) divide into two main groups, greedy heuristics and dual saturation heuristics. We use the concept of a Pareto optimal dual solution to show that an arbitrary dual saturation heuristic has the same worst-case performance guarantee as the two best known heuristics of that type. Moreover, this poor performance level is always attainable by those two heuristics.     

A heuristic lagrangean algorithm for the capacitated plant location problem

Lagrangean techniques have been widely applied to the uncapacitated plant location problem, and in some cases they have proven to be successfull even when capacitated problems with additional constraints are taken into account. In our paper we study the application of these techniques to the capacitated plant location problem when the model considered is a pure integer one. Several lagrangean decompositions are considered and for some of them heuristic algorithms have been designed to solve the resulting lagrangean subproblems, the heuristics consisting of a two phase procedure. The first (location phase) defines a set of multipliers from the analysis of the dual LP relaxation, and makes a choice of the plants considering the resulting subproblems as a particular case of the general assignment problems. Several heuristics have been studied for this second phase, based either on a decomposition of knapsack type subproblems through a definition of a set of penalties, or of looking into the duality gap and trying to reduce it. Computational experience is reported.     

考虑需求不确定的多级应急物流设施选址研究

为了对急物流设施选址问题进行合理的研究,建立了包含配送中心、配送点和需求点的多级应急物流网络。基于应急物资需求特点,使用三角模糊数表示应急物资需求的不确定性,同时考虑应急救援成本和应急救援时间两个目标,建立了应急物流设施选址模型。采用去模糊化方法将三角模糊数转化为确定数,利用成本和时间的单目标的最优结果将多目标转化为相对值,再对时间和成本目标进行加权处理,既消除了不同目标之间的单位及数量级差异,还可以进行动态调整。设计了遗传算法对模型进行求解,通过实际算例表明了模型和算法可以有效地解决应急物流设施选址问题。     

A repeated matching heuristic for the single-source capacitated facility location problem

Facility location models form an important class of integer programming problems, with application in many areas such as the distribution and transportation industries. An important class of solution methods for these problems are so-called Lagrangean heuristics which have been shown to produce high quality solutions and which are at the same time robust. The general facility location problem can be divided into a number of special problems depending on the properties assumed. In the capacitated location problem each facility has a specific capacity on the service it provides. We describe a new solution approach for the capacitated facility location problem when each customer is served by a single facility. The approach is based on a repeated matching algorithm which essentially solves a series of matching problems until certain convergence criteria are satisfied. The method generates feasible solutions in each iteration in contrast to Lagrangean heuristics where problem dependent heuristics must be used to construct a feasible solution. Numerical results show that the approach produces solutions which are of similar and often better than those produced using the best Lagrangean heuristics.     

The maximum return-on-investment plant location problem with market share

This paper examines the plant location problem under the objective of maximizing return-on-investment. However, in place of the standard assumption that all demands must be satisfied, we impose a minimum acceptable level on market share. The model presented takes the form of a linear fractional mixed integer program. Based on properties of the model, a local search procedure is developed to solve the problem heuristically. Variable neighbourhood search and tabu search heuristics are also developed and tested. Thus, a useful extension of the simple plant location problem is examined, and heuristics are developed for the first time to solve realistic instances of this problem.     

改进的蝗虫优化算法在双目标应急物资中心选址问题中的应用

近年来世界各地频发灾情疫情等紧急事件,严重影响人民的生活物资保障。在这种情况下,急需建立应急物资中心来缓解燃眉之急。该类问题通常面临资源稀缺并且时间相对紧迫的处境,因此需要在短时间内获得合理的应急设施选址方案来提升服务的质量和效率。本文对应急物资中心选址问题展开研究,提出一种考虑后续运输成本以及有概率发生紧急事件而导致无法正常运送物资的双目标离散选址模型,并为此设计一种二进制多目标蝗虫优化算法。该算法采用模糊关联熵系数来引导迭代更新,同时为其添加外部档案,最优解选择机制和竞争决策机制来提升算法性能。多次数值实验表明该算法的计算效率和求解质量较高,可作为应急物资中心选址问题的一种可行且有效的算法。     

Unified encoding for hyper-heuristics with application to bioinformatics

This paper introduces a new approach to applying hyper-heuristic algorithms to solve combinatorial problems with less effort, taking into account the modelling and algorithm construction process. We propose a unified encoding of a solution and a set of low level heuristics which are domain-independent and which change the solution itself. This approach enables us to address NP-hard problems and generate good approximate solutions in a reasonable time without a large amount of additional work required to tailor search methodologies for the problem in hand. In particular, we focused on solving DNA sequencing by hybrydization with errors, which is known to be strongly NP-hard. The approach was extensively tested by solving multiple instances of well-known combinatorial problems and compared with results generated by meta heuristics that have been tailored for specific problem domains.     

Heuristics for solving a capacitated multiple allocation hub location problem with application in German wagonload traffic

In this paper, we present a capacitated multiple allocation hub location problem, which arose from a network design problem in German wagonload traffic. We develop heuristic solution approaches based on local improvements. We solve the problem with the heuristics and CPLEX on test data sets provided by our partner Deutsche Bahn AG. The computational results are presented and compared.