Article ID: | iaor2013403 |
Volume: | 226 |
Issue: | 1 |
Start Page Number: | 19 |
End Page Number: | 31 |
Publication Date: | Apr 2013 |
Journal: | European Journal of Operational Research |
Authors: | Xu Zongben, Feng Zuren, Ke Liangjun, Shang Ke, Qian Xueming |
Keywords: | orienteering, robust optimization, branch and price |
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.