×

Proportion-based robust optimization and team orienteering problem with interval data. (English) Zbl 1292.90249

Summary: In this paper, a proportion-based robust optimization approach is developed to deal with uncertain combinatorial optimization problems. This approach assumes that a certain proportion of uncertain coefficients in each solution are allowed to change and optimizes a deterministic model so as to achieve a trade-off between optimality and feasibility when the coefficients change. We apply this approach on team orienteering problem with interval data (TOPID), a variant of vehicle routing problem, which has not yet been studied before. A branch and price algorithm is proposed to solve the robust counterpart by using two novel dominance relations. Finally, numerical study is performed. The results show the usefulness of the proposed robust optimization approach and the effectiveness of our algorithm.

MSC:

90C27 Combinatorial optimization
90B06 Transportation, logistics and supply chain management
90C10 Integer programming
90C31 Sensitivity, stability, parametric optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI