Informatica

We consider a geographical region with spatially separated customers, whose demand is currently served by some pre-existing facilities owned by different firms. An entering firm wants to compete for this market locating some new facilities. Trying to guarantee a future satisfactory captured demand for each new facility, the firm imposes a constraint over its possible locations (a finite set of candidates): a new facility will be opened only if a minimal market share is captured in the short-term. To check that, it is necessary to know the exact captured demand by each new facility. It is supposed that customers follow the partially binary choice rule to satisfy its demand. If there are several new facilities with maximal attraction for a customer, we consider that the proportion of demand captured by the entering firm will be equally distributed among such facilities (equity-based rule). This ties breaking rule involves that we will deal with a nonlinear constrained discrete competitive facility location problem. Moreover, minimal attraction conditions for customers and distances approximated by intervals have been incorporated to deal with a more realistic model. To solve this nonlinear model, we first linearize the model, which allows to solve small size problems because of its complexity, and then, for bigger size problems, a heuristic algorithm is proposed, which could also be used to solve other constrained problems.

A new heuristic algorithm for solution of bi-objective discrete competitive facility location problems is developed and experimentally investigated by solving different instances of a facility location problem for firm expansion. The proposed algorithm is based on ranking of candidate locations for the new facilities, where rank values are dynamically adjusted with respect to behaviour of the algorithm. Results of the experimental investigation show that the proposed algorithm is suitable for the latter facility location problems and provides good results in sense of accuracy of the approximation of the true Pareto front.

A multitude of heuristic stochastic optimization algorithms have been described in literature to obtain good solutions of the box-constrained global optimization problem often with a limit on the number of used function evaluations. In the larger question of which algorithms behave well on which type of instances, our focus is here on the benchmarking of the behavior of algorithms by applying experiments on test instances. We argue that a good minimum performance benchmark is due to pure random search; i.e. algorithms should do better. We introduce the concept of the cumulative distribution function of the record value as a measure with the benchmark of pure random search and the idea of algorithms being dominated by others. The concepts are illustrated using frequently used algorithms.