Design of poset forest-based algorithms for the U-curve optimization problem
Models and algorithms for nonlinear mixed integer problems (MINLP)
| Full text | |
| Author(s): |
Total Authors: 2
|
| Affiliation: | [1] Univ Estadual Campinas, Inst Comp, Av Albert Einstein, 1251, Cidade Univ, BR-13083852 Campinas, SP - Brazil
Total Affiliations: 1
|
| Document type: | Journal article |
| Source: | JOURNAL OF COMBINATORIAL OPTIMIZATION; v. 36, n. 1, p. 131-141, JUL 2018. |
| Web of Science Citations: | 0 |
| Abstract | |
We consider the bus evacuation problem. Given a positive integer B, a bipartite graph G with parts S and in a metric space and functions and , one wishes to find a set of B walks in G. Every walk in B should start at r and finish in T and r must be visited only once. Also, among all walks, each vertex i of S must be visited at least times and each vertex j of T must be visited at most times. The objective is to find a solution that minimizes the length of the longest walk. This problem arises in emergency planning situations where the walks correspond to the routes of B buses that must transport each group of people in S to a shelter in T, and the objective is to evacuate the entire population in the minimum amount of time. In this paper, we prove that approximating this problem by less than a constant is -hard and present a 10.2-approximation algorithm. Further, for the uncapacitated BEP, in which is infinity for each j, we give a 4.2-approximation algorithm. (AU) | |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |