TY - JOUR

T1 - A Forward–Backward Simheuristic for the Stochastic Capacitated Dispersion Problem

AU - Gomez, Juan F.

AU - Martínez-Gavara, Anna

AU - Panadero, Javier

AU - Juan, Angel A.

AU - Martí, Rafael

N1 - Publisher Copyright:
© 2024 by the authors.

PY - 2024/3/20

Y1 - 2024/3/20

N2 - In an effort to balance the distribution of services across a given territory, dispersion and diversity models typically aim to maximize the minimum distance between any pair of facilities. Specifically, in the capacitated dispersion problem (CDP), each facility has an associated capacity or level of service, and the objective is to select a set of facilities so that the minimum distance between any pair of them (dispersion) is maximized, while ensuring a user-defined level of service. This problem can be formulated as a linear integer model, where the sum of the capacities of the selected facilities must match or exceed the total demand in the network. Real-life applications often necessitate considering the levels of uncertainty affecting the capacity of the nodes. Failure to account for this uncertainty could lead to low-quality or infeasible solutions in practical scenarios. However, research addressing the stochastic version of the CDP is scarce. This paper introduces two models for the CDP with stochastic capacities, incorporating soft constraints and penalty costs for violating the total capacity constraint. The first model includes a probabilistic constraint to ensure the required level of service with a certain probability, while the second model introduces a soft constraint with penalty costs for violations. To solve both variants of the model, a forward–backward simheuristic algorithm is proposed. Our approach combines a metaheuristic algorithm with Monte Carlo simulation, enabling the efficient handling of the random behavior of node capacities and obtaining reliable solutions regardless of their probability distribution.

AB - In an effort to balance the distribution of services across a given territory, dispersion and diversity models typically aim to maximize the minimum distance between any pair of facilities. Specifically, in the capacitated dispersion problem (CDP), each facility has an associated capacity or level of service, and the objective is to select a set of facilities so that the minimum distance between any pair of them (dispersion) is maximized, while ensuring a user-defined level of service. This problem can be formulated as a linear integer model, where the sum of the capacities of the selected facilities must match or exceed the total demand in the network. Real-life applications often necessitate considering the levels of uncertainty affecting the capacity of the nodes. Failure to account for this uncertainty could lead to low-quality or infeasible solutions in practical scenarios. However, research addressing the stochastic version of the CDP is scarce. This paper introduces two models for the CDP with stochastic capacities, incorporating soft constraints and penalty costs for violating the total capacity constraint. The first model includes a probabilistic constraint to ensure the required level of service with a certain probability, while the second model introduces a soft constraint with penalty costs for violations. To solve both variants of the model, a forward–backward simheuristic algorithm is proposed. Our approach combines a metaheuristic algorithm with Monte Carlo simulation, enabling the efficient handling of the random behavior of node capacities and obtaining reliable solutions regardless of their probability distribution.

KW - dispersion problem

KW - metaheuristics

KW - simulation

KW - stochastic optimization problems

UR - http://www.scopus.com/inward/record.url?scp=85188958564&partnerID=8YFLogxK

UR - https://www.mendeley.com/catalogue/f79fbe9c-f675-3907-a157-b2f356f0e4e5/

U2 - 10.3390/math12060909

DO - 10.3390/math12060909

M3 - Article

AN - SCOPUS:85188958564

SN - 2227-7390

VL - 12

JO - Mathematics

JF - Mathematics

IS - 6

M1 - 909

ER -