Finding an Optimal Location of Line Facility using Evolutionary Algorithm and Integer Program

Journal of Computational Science and Technology

Takenao TAJI¹  Atsushi TAKIZAWA¹  Naoki KATOH¹  Naoyuki KAMIYAMA¹  Shin-ichi TANIGAWA¹ 

[1] Department of Architecture and Architectural Engineering, Kyoto University

关键词: Line Facility Location;    Railway System;    Integer Program Minimum Communication Spanning Tree;    Evolutionary Algorithm;   

DOI  :  10.1299/jcst.2.362

学科分类：地球科学(综合)

来源: Japan Academy

【 摘 要 】

References(7)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.

【 授权许可】

Unknown