偏倚随机算法解决带软约束的容量设施定位问题

需积分: 9 9 浏览量更新于2024-06-30 收藏 2.47MB PDF 举报

"这篇论文是关于偏倚随机算法在处理有软约束的容量限制设施定位问题中的应用。作者包括Alejandro Estrada-Moreno、Albert Ferrer、Angel A. Juan、Adil Bagirov和Javier Panadero。该研究发表在《运筹学学会期刊》(Journal of the Operational Research Society)上，ISSN号为0160-5682（印刷版）和1476-9360（在线版）。文章的DOI为10.1080/01605682.2019.1639478，于2019年8月23日在线发布。" 在运筹学领域，设施定位问题是一个重要的优化问题，特别是在物流、供应链管理和资源分配等场景中。容量限制的设施定位问题（Capacitated Facility Location Problem, CFLP）是指在一定的设施容量下，决定在何处建立或关闭设施以服务需求点，同时最小化成本。这个问题通常伴随着硬约束，如设施的容量限制和服务覆盖范围，但在此研究中，引入了软约束的概念。软约束允许在一定程度上违反原有的规则，以换取更好的解决方案或更高的灵活性。这可能是为了平衡成本与服务质量，或者在实际操作中考虑到某些特殊情况。偏倚随机算法是一种混合了确定性和随机性的优化方法，它通过引入偏倚来指导搜索过程，以更倾向于找到潜在的优秀解。论文中，作者可能详细介绍了如何设计并实施这种偏倚随机算法，包括算法的各个步骤、如何处理软约束以及如何调整偏倚以改善性能。他们可能还进行了数值实验，比较了提出的算法与传统方法在解决CFLP问题上的效果，评估了算法的效率和解的质量。此外，文章可能还涵盖了以下内容： 1. 算法的理论基础，包括概率论和随机过程的基本概念。 2. 优化问题的建模，如何将软约束纳入传统的CFLP模型。 3. 实验设计，包括不同的实例、数据集和性能指标。 4. 结果分析，展示算法的性能优势以及对不同问题规模和约束条件的适应性。 5. 对未来研究的讨论，可能提出了进一步改进算法或将其应用于其他相关问题的研究方向。这篇论文对于理解和解决有软约束的复杂优化问题提供了新的视角，对于运筹学、计算机科学和管理科学领域的研究人员和实践者都具有较高的参考价值。引用这篇文章的其他研究可能已经进一步发展了这个算法，或者将其应用于实际的业务场景中。

Hirsch, 2019; Juan, Pascual, Guimarans, &

Barrios, 2015).

The remaining of the paper is structured as fol-

lows: Section 2 presents some works on the

SSCFLP. A mathematical description of the non-

smooth SSCFLP is provided in Section 3.InSection

4, a BRILS algorithm is proposed as a solving

method for the non-smooth SSCFLP. Section 5 is

devoted to explain the computational experiments

performed. Finally, conclusions and future work are

discussed in Section 6.

2. Related work on the SSCFLP

Some seminal contributions to the FLP can be

found in Revelle, Marks, and Liebman (1970),

Guignard and Spielberg (1977), Cornuejols (1978),

and Krarup and Pruzan (1983). In the latter, the

authors mention several real-world applications

regarding the number, size, design, location, and

service patterns for “facilities” such as high schools,

hospitals, silos, slaughterhouses, warehouses, and

production plants. The survey written by Klose and

Drexl (2005) and the book edited by Eiselt and

Marianov (2011) cover many relevant works on

the FLP.

One of the most interesting FLP variants is the

aforementioned single-source capacitated FLP. Many

of solving approaches proposed for the SSCPLP are

based on obtaining good Lagrangian duals, whose

solutions improve the lower bounds provided by the

LP-relaxation. Each proposed method differs in the

constraints that are relaxed: the assignment con-

straints, the capacity constraints, or both. In add-

ition, a primal heuristic is usually included in order

to find feasible solutions. For instance, Klincewicz

and Luss (1986) relax the capacity constraints. Thus,

the uncapacitated FLP is obtained as a subproblem

and solved by employing the well-known dual

ascent algorithm. The Lagrangian relaxations are

complemented by an add heuristic, which is used to

obtain an initial feasible solution. Similarly, Pirkul

(1987) uses the Lagrangian relaxation of the capacity

constraints to develop optimal and heuristic proce-

dures for this problem. Barcel



o and Casanovas

(1984) develop several Lagrangian decompositions

and, for some of them, heuristic algorithms were

designed to solve the resulting Lagrangian subpro-

blems. Hindi and Pie



nkosz (1999) devise a heuristic

combining Lagrangian relaxation with restricted

neighbourhood search. Cortinhal and Captivo

(2003) obtain lower bounds by using a Lagrangian

relaxation, while upper bounds are achieved by

Lagrangian-based heuristics followed by search

methods and by a tabu search metaheuristic. Chen

and Ting (2008) develop a hybrid algorithm to solve

the SSCFLP. Their algorithm combines a

Lagrangian-based heuristic and an ant colony sys-

tem. The reader is referred to Galv

ao and Marianov

(2011) for a more comprehensive literature overview

on Lagrangian relaxation-based techniques for solv-

ing different FLP variants, including the SSCFLP.

Other heuristics have been proposed in the litera-

ture to solve the SSCFLP. Thus, Filho and Galv

(1998) proposed a tabu search metaheuristic, while

Delmaire, D



ıaz, Fern



andez, and Ortega (1999) pro-

posed a reactive GRASP, a tabu search, and two dif-

ferent hybrid approaches that combine elements of

the GRASP and the tabu search frameworks.

€

onnqvist, Tragantalerngsak, and Holt (1999) pro-

pose an approach based on a repeated matching

algorithm, which essentially solves a series of match-

ing problems until certain convergence criteria are

satisfied. A very large-scale neighbourhood search

algorithm for the SSCFLP is proposed in Ahuja,

Orlin, Pallottino, Scaparra, and Scutell



a(2004).

Contreras and D



ıaz (

2007) devise a scatter search

approach to provide upper bounds for the SSCFLP.

Finally, Guastaroba and Speranza (2014) propose a

kernel search framework that is applied to

the SSCFLP.

Exact methods have also been applied to the

SSCFLP. For instance, Holmberg, R

€

onnqvist, and

Yuan (1999) devise a repeated matching algorithm,

incorporated into a Lagrangian heuristic, which is

used as a primal heuristic to solve a series of match-

ing problems until certain convergence criteria are

satisfied. Finally, a branch-and-bound method,

based on the Lagrangian heuristic, is developed and

compared to the results provided by Cplex. D



ıaz

and Fern



andez (2002) develop an exact algorithm in

which a column generation procedure for finding

upper and lower bounds is incorporated within a

branch-and-price framework. In this case computa-

tional results are reported for instances with up to

30 facilities and 90 customers. Similarly, an exact

algorithm based on a cut-and-solve framework is

introduced by Yang et al. (2012) for the SSCFLP.

They solve to optimality instances with up to 80

facilities and 400 customers.

Finally, Albareda-Sambola, Landete, Monge, and

Sainz-Pardo (2017) analyze a FLP version in which

facilities can fail with some probability. These authors

introduce soft capacity constraints on the facilities,

i.e., small violations of these constraints are allowed

for the scenario with unreliable facilities.

3. Modelling the non-smooth SSCFP

This section starts by offering a mathematical model

for the SSCFLP. Then, it extends this basic model to

the non-smooth case.

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 1801

剩余17页未读，继续阅读

qq_38666245

粉丝: 0
资源: 2

偏倚随机算法解决带软约束的容量设施定位问题

设施选址问题的近似算法.pdf

论文研究-Electromagnetic Analysis for Tunable Miniaturized Patch Antennas with Self-Biased Magnetic Film.pdf

Biased Locking in HotSpot - Dave - 2006.pdf

A study on Biased Guidance Problem of the Space Flight Vehicle

Ranking-based biased learning swarm optimizer for .zip

invest-email-biased.csv

A 400MHz-2.4G randiation-tolerant self biased phase-locked loop

Generalized rotating-wave approximation to biased qubit-oscillator systems

matlab导入excel代码-Skill-Biased-Structural-Change---Replication-Package:基于

Enhanced asymmetrically clipped DC biased optical OFDM for intensity-modulated direct-detection systems

最新资源