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.
論文 | ランダム
- 森林--西と東 (ユフロ〔国際林業研究機関連合〕世界大会)
- 森林文化 (一五〇〇号記念特集 わが国林業の半世紀)
- 森と人 「森林文化」を支えるには(これからの課題)
- 森と人 「森林文化」を支えた人たち(一九四五年前後)
- 戦後の森林法律の変遷