지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
이용수
초록· 키워드
오류제보하기
Given a tree network on which each node has its own demand and also stands for a candidate location of a potential facility, such as plant or warehouse, the p-median problem on the network (PMPOT) is to select less than or equal to p number of facility locations so that the whole demand on a node is satisfied from only facility and the total demand occurred on the network can be satisfied from those facilities with the minimum total cost, where the total cost is the sum of transportation costs and the fixed costs of establishing facilities.
Tamir(1996) developed an o(pn²) algorithm for PMPOT which is known to be the best algorithm in terms of the time complexity, where n is the number of nodes in the network, but he didn't make any comments or explanation about implementation details for finding the optimal solution. In contrast to Tamir's work, Kariv and Hakimi(1979) developed O(p²n²) algorithm for PMPOT and presented O(n²) algorithm for finding the optimal solution in detail.
In this paper, we not only develop another O(pn²) dynamic programming algorithm for PMPOT that is competitive to Tamir's algorithm in terms of the time complexity, but also present O(n) algorithm that is more efficient than Kariv and Hakimi's algorithm in finding the optimal solution. Finally, we implement our algorithm on a set of randomly generated problems and report the computational results.
Tamir(1996) developed an o(pn²) algorithm for PMPOT which is known to be the best algorithm in terms of the time complexity, where n is the number of nodes in the network, but he didn't make any comments or explanation about implementation details for finding the optimal solution. In contrast to Tamir's work, Kariv and Hakimi(1979) developed O(p²n²) algorithm for PMPOT and presented O(n²) algorithm for finding the optimal solution in detail.
In this paper, we not only develop another O(pn²) dynamic programming algorithm for PMPOT that is competitive to Tamir's algorithm in terms of the time complexity, but also present O(n) algorithm that is more efficient than Kariv and Hakimi's algorithm in finding the optimal solution. Finally, we implement our algorithm on a set of randomly generated problems and report the computational results.
목차
Abstract
1. 서론
2. PMPOT의 O-1 선형정수계획 모형
3. 동적계획 알고리듬
4. 계산실험
5. 결론
참고문헌
참고문헌 (14)
참고문헌 신청
[학술지(정기간행물)] - / 1988 / Probabilistic Analysis of a Relaxation for the K-median Problem 13 : 1 ~ 31
[학술지(정기간행물)] - / 2002 / A New Method for Solving Capacitated Location Problems Based on a Set Partitioning Approach 29 : 365 ~ 386
[학술지(정기간행물)] - / 1984 / P-median and Multi-medians 35 : 57 ~ 64
[학술지(정기간행물)] - / 2000 / 2- Medians in Trees with Pos/Neg Weights 105 : 51 ~ 71
[학술지(정기간행물)] - / 1986 / Network Location Problems with Continuous Link Demands：p-medians on a chain and 2- medians on a tree 23 : 246 ~ 255
[학술지(정기간행물)] - / 2002 / A New Method for Solving Capacitated Location Problems Based on a Set Partitioning Approach 29 : 365 ~ 386
[학술지(정기간행물)] - / 1984 / P-median and Multi-medians 35 : 57 ~ 64
[학술지(정기간행물)] - / 2000 / 2- Medians in Trees with Pos/Neg Weights 105 : 51 ~ 71
[학술지(정기간행물)] - / 1986 / Network Location Problems with Continuous Link Demands：p-medians on a chain and 2- medians on a tree 23 : 246 ~ 255
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
Optimal location of overwork-allowed facilities subject to choice of various equipment modes
한국경영과학회 학술대회논문집
2006 .11
-
나무구조를 갖는 네트워크 상에서의 제한용량이 없는 입지설정문제에 대한 효율적인 알고리즘
대한경영학회지
1998 .07
-
[Session C4. 일정계획(2); 인공지능] 최적 공간 배치 설계를 위한 개선된 유전 알고리즘에 관한 연구
한국경영과학회 학술대회논문집
2001 .04
-
네트워크 문제를 위한 새로운 진화 알고리즘에 대하여
한국경영과학회지
2007 .06
-
An Algorithm for the Robust Single Source Capacitated Facility Location Problem Under Demand Uncertainty
한국경영과학회 학술대회논문집
2017 .04
-
통신비용을 최소화하는 복제 웹컨텐츠 분배나무 구성을 위한 개선된 알고리즘
경영과학
2005 .11
-
A Neural Network-based Algorithm for Group Technology
한국경영과학회 학술대회논문집
1993 .01
-
다수제품의 수익성 최대화를 위한 설비입지선정 문제
한국경영과학회지
2006 .12
-
국방 전산망의 효율적인 설계를 위한 휴리스틱 알고리듬 개발
군사학연구
2003 .01
-
서울시의 활동여가시설의 입지유형에 관한 연구 : 강남구를 중심으로
지역연구
1994 .12
-
농업용 시설의 건축 및 이용 법령 개선연구
농촌계획
2013 .01
-
패킷 통신 네트워크 설계를 위한 시뮬레이티드 애닐링 방법에서 초기해와 후보해 생성방법
한국경영과학회지
2004 .09
-
대학 시설경영관리 능률향상을 위한 FM 항목분석
한국퍼실리티매니지먼트학회지
2018 .01
-
Determining Optimal Paths Between Fixed End-Points of a Moving Facility
한국경영과학회 학술대회논문집
1989 .01
-
Optimization of Transportation Problem in Dynamic Logistics Network
유통과학연구
2016 .01
-
Heuristics for the Access Network Design Problem in UMTS Mobile Communication Networks
경영과학
2010 .11
-
2 계층 공생 진화알고리듬을 이용한 다목적 최적화
한국경영과학회 학술대회논문집
2006 .11
-
순차적으로 선택된 특성과 유전 프로그래밍을 이용한 결정나무
경영과학
2006 .05
이 논문의 저자 정보
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2009-325-013787490