논문 국내 국내일반학술지 A Study on the Solution Methed of Maximum Origin-Destination Flow Path in an Acgclic network Using Branch and Bound Method
- 학술지 구분 국내일반학술지
- 게재년월 1995-01
- 저자명 임준묵공동(제1),성기석
- 학술지명 Journal of the Korean OR/MS Society
- 발행처명 한국경영과학회
- 발행국가 국내
- 논문언어 외국어
- 전체저자수 2
홈페이지논문 초록 (Abstract)
This paper is concerned with the scheduling of Electrical Multiple Units (EMUs) under the condition of their utilization on one sector or within several interacting sectors. Based on the introduction of the train connection graph which describes the possible connection relationship between trains, the integer programming model of EMU circulation planning is constructed. In order to analyzing the resolution of the model, a heuristic which shares the characteristics with the existing methods is introduced first. This method consists of two stages: one is a greedy strategy to construct a feasible circulation plan fragment, and another is to apply a stochastic disturbance to it to generate a whole feasible solution or get a new feasible solution. Then, an exact branch and bound method which is based on graph designing is proposed. Due to the complexity, the lower bound is computed through a polynomial approximation algorithm which is a modification from the one solving the degree constraint minimum 1-tree problem. Then, a branching strategy is designed to cope with the maintenance constraints. Finally, we report extensive computational results on a railway corridor in which the sectors possess the basic feature of railway networks.