Proportion-based robust optimization and team orienteering problem with interval data
详细信息 查看全文
- 作者：Liangjun Ke ; kelj163@163.com ; Zongben Xu ; Zuren Feng ; Ke Shang ; Xueming Qian
- 关键词：Uncertainty modeling ; Robust optimization ; Combinatorial optimization ; Team orienteering problem ; Vehicle routing problem
- 刊名：European Journal of Operational Research
- 出版年：2013
- 出版时间：1 April, 2013
- 年：2013
- 卷：226
- 期：1
- 页码：19-31
- 全文大小：397 K
文摘
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.