Elements of simulated annealing in Pareto front search

Determination of the Pareto front of location problem solutions represents one of the very complex and computational time demanding tasks, when solved by exact means of mathematical programming. This paper is motivated by possible application of the metaheuristic simulated annealing to the process of obtaining a close approximation of the Pareto front by a set of non-dominated solutions of the p-location problem. Contrary to the other approaches, the suggested method is based on minimization of non-dominated solution set area, which directly describes quality of the approximation. Elements of the simulated annealing method are used for random breaking some limits imposed on local characteristics of the improving process. The presented results of the numerical experiments give an insight to relations among the simulated annealing parameters and optimization process efficiency.

discrete location problems, bi-criteria decisionmaking, Pareto front, simulated annealing

1. Ahmadi-Javid, A., Seyedi, P. et al. (2017). A survey of healthcare facility location, Computers & Operations Research, 79, pp. 223-263.

2. Arroyo, J. E. C., dos Santos, P. M., Soares, M. S. and Santos, A. G. (2010). A Multi-Objective Genetic Algorithm with Path Relinking for the p-Median Problem. In: Proceedings of the 12th Ibero-American Conference on Advances in Artificial Intelligence, 2010, pp. 70–79.

3. Avella, P., Sassano, A., Vasil'ev, I. (2007). Computational study of large scale p-median problems. Mathematical Programming 109, pp. 89-114.

4. Brotcorne, L, Laporte, G, Semet, F. (2003). Ambulance location and relocation models. Eur. Journal of Oper.Research, 147, pp. 451-463.

5.Buzna, Ľ., Koháni, M., Janáček, J. (2013). Proportionally Fairer Public Service Systems Design. In: Communications - Scientific Letters of the University of Žilina 15(1), pp. 14-18.

6. Current, J., Daskin, M. and Schilling, D. (2002). Discrete network location models, Drezner Z. et al. (ed) Facility location: Applications and theory, Springer, pp. 81-118.

7. Doerner, K. F., Gutjahr, W. J., Hartl, R. F., Karall, M. and Reimann, M. (2005). Heuristic Solution of an Extended Double-Coverage Ambulance Location Problem for Austria. Central European Journal of Operations Research, 13(4), pp. 325-340.

8. Drezner, T., Drezner, Z. (2007). The gravity p-median model. European Journal of Operational Research 179, pp. 1239-1251.

9. Gopal, G. (2013). Hybridization in Genetic Algorithms. International Journal of Advanced Research in Computer Science and Software Engineering, vol. 3, pp. 403–409.

10. Grygar, D., Fabricius, R. (2019). An efficient adjustment of genetic algorithm for Pareto front determination. In: TRANSCOM 2019: conference proceedings, Amsterdam: Elsevier Science, pp. 1335-1342.

...