Finding an Optimal Location of Line Facility using Evolutionary Algorithm and Integer Program
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, we consider the problem for determining an optimal location of a line facility in a city such as railway system. A line facility is modeled as a spanning tree embedded on the plane whose vertices represent stations and edges represent the rails connecting two stations, and people can travel not only by walk but also by using the line facility quickly. Suppose there are a finite number of towns in a city, only in which people lives. Then, our problem is to find a location of the stations as well as a connection of the stations such that the sum of travel time between all pairs of towns is minimum. Tsukamoto, Katoh and Takizawa proposed a heuristic algorithm for the problem which consists of two phases as follows. In the first phase, fixing the position of stations, it determines the topology of the line facility. The second phase optimizes the position of stations while the topology is fixed. The algorithm alternately executes these two phases until a converged solution is obtained. Tsukamoto et al. determined the topology of the line facility by solving minimum spanning tree (MST) in the first phase. In this paper, we propose two methods for determining the topology of the line facility so that the sum of travel time is minimized hoping to improving the previous algorithm. The first proposed method heuristically determine the topology by using evolutionary algorithm (EA). In the second method, we reduce our problem to minimum communication spanning tree (MCST) problem by making a further assumption, and solve it by formulating the problem as an integer program. We show the effectiveness of our proposed algorithm through the numerical experiments.
論文 | ランダム
- プロトマー酵素と基質またはインヒビターとの結合 インヒビターの結合によるコンホメーション変化 (アロステリック効果(特集))
- リゾチームの立体構造と酵素活性 (リゾチーム(特集))
- 蛋白質の構造と環境
- 蛋白質の旋光度
- A New Spectrophotometric Method for the Determination of Tianeptine in Tablets Using Ion-Pair Reagents