کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
479307 | 1445986 | 2016 | 7 صفحه PDF | دانلود رایگان |
• Considered the minimax regret 1-sink location problem with accessibility in dynamic general networks.
• Computed the values of T(opt(s), s) in O(m2n3) time.
• Got the minimax regret sink x* in O(mn4) time after known the values of T(opt(s), s).
In this study, we consider the minimax regret 1-sink location problem with accessibility, where all of the weights should always evacuate to the nearest sink point along the shortest path in a dynamic general network with positive edge lengths and uniform edge capacity. Let G=(V,E)G=(V,E) be an undirected connected simple graph with n vertices and m edges. Each vertex has a weight that is not known exactly but the interval to which it belongs is given. A particular assignment of a weight to each vertex is called a scenario. The problem requires that a point x should be found as the sink on the graph and all the weights evacuate to x such that the maximum regret for all possible scenarios is minimized. We present an O(m2n3) time algorithm to solve this problem.
Journal: European Journal of Operational Research - Volume 250, Issue 2, 16 April 2016, Pages 360–366