共查询到20条相似文献,搜索用时 0 毫秒
1.
A. Klose 《International Transactions in Operational Research》1998,5(2):155-168
In this paper, a branch and bound algorithm for solving an uncapacitated facility location problem (UFLP) with an aggregate capacity constraint is presented. The problem arises as a subproblem when Lagrangean relaxation of the capacity constraints is used to solve capacitated facility location problems. The algorithm is an extension of a procedure used by Christofides and Beasley (A tree search algorithm for the p-median problem. European Journal of Operational Research , Vol. 10, 1982, pp. 196–204) to solve p -median problems and is based on Lagrangean relaxation in combination with subgradient optimization for lower bounding, simple Lagrangean heuristics to produce feasible solutions, and penalties to reduce the problem size. For node selection, a jump-backtracking rule is proposed, and alternative rules for choosing the branching variable are discussed. Computational experience is reported. 相似文献
2.
Dung-Ying Lin Ampol Karoonsoontawong S. Travis Waller 《Networks and Spatial Economics》2011,11(1):101-126
We present a heuristic to solve the NP-hard bi-level network design problem (NDP). The heuristic is developed based on the
Dantzig-Wolfe decomposition principle such that it iteratively solves a master problem and a pricing problem. The master problem
is the budget allocation linear program solved by CPLEX to determine the budget allocation and construct a modified cell transmission
network for the pricing problem. The pricing problem is the user-optimal dynamic traffic assignment (UODTA) solved by an existing
combinatorial algorithm. To facilitate the decomposition principle, we propose a backward connectivity algorithm and complementary
slackness procedures to efficiently approximate the required dual variables from the UODTA solution. The dual variables are
then employed to augment a new column in the master program in each iteration. The iterative process repeats until a stopping
criterion is met. Numerical experiments are conducted on two test networks. Encouraging results demonstrate the applicability
of the heuristic scheme on solving large-scale NDP. Though a single destination problem is considered in this paper, the proposed
scheme can be extended to solve multi-destination problems as well. 相似文献
3.
Flow shop调度问题属于NP难题,传统的方法很难求出精确最优解,提出了一种遗传分枝定界算法,即在遗传算法中引入分枝定界算法保持对优化解有贡献的工件部分顺序,求解3机Flow shop调度问题,该算法与常用的遗传局部算法和遗传动态规划算法类似,用随机方法测试例子,与目前著名的Taillard的禁忌搜索算法和Reeves的遗传算法两种改进算法进行比较,大量的数据实验证实了遗传分枝定界算法的有效性。 相似文献
4.
0-1背包问题是经典的NP问题。本文对0-1背包问题的分枝限界算法进行了分析,用Visual C++实现该算法。 相似文献
5.
分枝限界算法是一种求解组合优化问题的一般性方法,并行化是提高算法性能的有效手段。文章使用[5]中提出的算法模式和结构模式的概念和思想设计并实现了一个并行分枝限界算法的产生器。该产生器通过提供并行分枝限界算法的抽象框架,将它应用于要求解的问题,可以得到问题的并行分枝限界算法。 相似文献
6.
枝切法是一种高效的抗噪声相位展开方法,而最短枝切长度能够保证最优的相位展开结果。最短枝切长度问题属于组合优化问题,提出一种求解该问题的学习算法,将最短枝切长度问题的解视为个体,该算法通过个体之间的学习以及个体自身的变异实现进化,作用类似于遗传算法中的交叉算子以及变异算子。通过对多幅含噪声包裹相位图进行实验验证,该算法比传统的求解最短枝切长度问题的算法更快更优。 相似文献
7.
8.
为解决现有离散优化算法在有限时间内容易出现过早收敛或难以收敛的问题,提出了面向离散优化问题的量子协同演化算法。该算法通过种群初始化策略构建分布均匀的初始种群,并改进粒子群和单点优化算法成为具有不同搜索能力的协同演化策略,进而利用量子旋转门根据种群个体的进化情况自适应地选择合适的演化策略,最后利用精英保持策略避免种群的退化。在标准离散问题和背包问题的测试环境中,各算法的平均收敛精度和实际收敛情况均表明,已提出的算法能够在有限时间内,收敛到精度较高的解,可用于求解具有时效要求的离散优化问题。 相似文献
9.
10.
This paper addresses the discrete network design problem (DNDP) with emphasis on the environmental benefits. These benefits are traditionally quantified by emission models, which in general account for vehicle speeds, traffic flows and emission coefficients. An alternative approach for approximating the environmental impact of traffic is developed. This approach finds the route that keeps the most balanced speed profile throughout the route, which contributes to fuel consumption reduction. The paper formulates an optimization problem that includes the described approach for the DNDP. The solution of the problem consists of projects that contribute the most to the generation of such “balanced speed routes”. The paper illustrates the problem and the solution for a real-size network with a medium-size set of candidate projects. 相似文献
11.
《Neural Networks, IEEE Transactions on》2008,19(11):1961-1967
12.
In this paper, new ideas have been incorporated to a basic interval branch-and-bound algorithm which solves the problem of finding zeros in one-dimensional functions. These new ideas are based on the combination of a new rejection criterion, a selection strategy and an easy-to-obtain precondition of the problem at hand. The methodology described here focuses on finding the first zero crossing point, allowing the search of other zero crossing points to be avoided. In addition, a heuristic subdivision criterion has been proposed that, compared to bisection rule, provides improvements in most of the forty problems that have been tested. 相似文献
13.
14.
Peng Zhang 《International Journal of Software and Informatics》2011,5(4):607-636
The Rent-or-Buy Network Design problem is a fundamental connectivity-related network design problem. The problem captures the "economies of scale" property, which says that the per-unit cost of installing capacity on edges of the network decreases as more capacity is installed. The Sample-Augment algorithm is a simple but powerful randomized
approximation algorithm that effectively deals with the Rent-or-Buy and related problems. In this paper we systematically survey the Rent-or-Buy problem and the Sample-Augment algorithm, as well as its two analysis techniques, i.e., the cost-sharing method and the core-detouring scheme. 相似文献
15.
16.
17.
对随机组合优化问题中的概率旅行商问题(PTSP)的理论和方法进行了研究分析,采用现代进化算法中有代表性发展优势的萤火虫优化算法(FA),提出一种离散萤火虫优化算法(DFA)以求解.其中引入了新的学习机制使其相比原始的萤火虫优化算法,更容易搜索到全局最优解,有更好的收敛性能.实验中用TSPLIB中的经典实例进行测试来验证其可行性.考察了萤火虫数量和进化迭代次数对求解结果性能的影响,并将DFA与GA、PSO和ACO等其他著名的进化计算算法进行性能比较.实验结果证实了DFA无论对固定访问概率,还是访问概率为区间内随机数等不同情况,都具有良好的有效性和高效性,因此对求解随机组合优化系列问题的有效解决具有一定参考和借鉴价值. 相似文献
18.
本文针对带时间窗约束的同时送取货车辆路径问题,建立了以总配送距离最小化为目标的数学模型.根据模型的特征,在保留灰狼算法(GWO)搜索机制的基础上,提出了离散灰狼优化算法(DGWO)进行求解.采用多种策略构建种群的初始解,并允许出现不可行解,扩大种群的搜索区域;引入带评分策略的邻域搜索策略,调整每种算子的概率,使算法选择优化效果更好的算子;使用移除-插入机制,对优质解区域进行探索,加速种群的收敛.在仿真实验中对标准数据集进行了测试,将实验结果和p-SA算法、DCS算法、VNS-BSTS算法和SA-ALNS算法进行了对比,实验表明DGWO算法能有效地解决带时间窗约束的同时送取货车辆路径问题. 相似文献
19.
20.
本文将模式识别中的特征选择问题转化为有向图上最佳路径搜索问题,并应用AI中的
Best First (简记BF*)策略搜索最佳路径,提出了特征选择GBFF*和TBFF*算法,证明了
用它们可不穷举而一定找到最佳子集,同目前被认为最好的全局最佳算法--B&B相比,
TBFF*搜索的特征子集数目优于B&B. 相似文献