Dynamic programming for spanning tree problems: application to the multi-objective case

作者：Pugliese Luigi Di Puglia; Guerriero Francesca^*; Santos Jose Luis

来源：Optimization Letters, 2015, 9(3): 437-450.

DOI：10.1007/s11590-014-0759-1

• Dynamic programming
• Spanning tree problems
• Multiple objective programming
• Pareto front

The aim of this paper is to provide a dynamic programming formulation for the spanning tree problem (), which allows several instances of the classical to be addressed. The spanning tree structure is modelled with states and transition between states, defining a state-space. Several properties are shown and optimality conditions are given. Once the theoretical fundamentals of the proposed formulation are derived, the multi-objective spanning tree problem () is addressed. This problem arises in the telecommunications and transportation sectors. In these contexts, handling different criteria simultaneously plays a crucial role. The scientific literature provides several works that focus on the bi-objective version of the considered problem, in which only two criteria are taken into account. To the best of our knowledge, no works provide optimal methods to address the with an arbitrary number of objective functions. In this paper we extend the proposed dynamic programming formulation to model and solve the with criteria.

• 出版日期2015-3