연속 공간에 대한 시설 위치 문제
시설 위치 문제 (FLP) 문헌을 검토하고 있습니다. 여기에서 Daskin과 Dean (2004) 은 이산 공간 FLP에 대한 짧은 문헌을 제공하여 다양한 목적을 가진 다양한 유형의 모델을 구별하는 데 유용했습니다. Chopra와 Meindl (2013)은 "공급망 관리 : 전략, 계획 및 운영"이라는 책에서 중력 위치 모델 이라고 부르는 단일 시설 선택으로 연속 공간에 대한 FLP의 작은 예를 보여주었습니다 .
리뷰 논문을 찾거나 여러 시설을 선택한 연속 공간에 FLP를 공식화 한 논문을 선택합니다. 또한 Chopra and Meindl (2013)에서는 수요 노드와 가능한 시설 좌표 사이의 유클리드 거리를 고려했기 때문에 문제가 비선형 모델로 공식화되었습니다 . 선형 모델의 문제를 공식화하는 논문을 접한 적이 있습니까? 이것이 가능할까요?
문제를 더 잘 설명하기 위해 다 항적 크기의 수요 노드 집합이 있다고 가정하고 시설 및 서비스 비용을 최소화하면서 수요 를 완전히 충족 할 수있는 시설을 찾고자 합니다. 각 시설에는 순환 서비스 범위가 있으며 시설 비용은 위치에 따라 동일합니다. 시설에는 용량이 제한되어 있지 않고 다른 시설에서 수요의 일부를 충족 할 인센티브가 없기 때문에 각 수요 노드가 가장 가까운 시설에서 완전히 서비스 될 것이라고 가정 할 수 있으며 그 결과는 관심이 없습니다. 또한 유클리드 거리가 서비스 비용 계산의 주요 동인이라고 가정 할 수 있습니다.
또한 위에서 설명한 문제의 이산 간격 시설 버전에도 관심이 있습니다. 특히, 합리적인 계산 시간 (예 : 하루 미만)에 최대 2 백만 개의 수요 노드를 처리 할 수있는 알고리즘을 찾고 있습니다. 그렇지 않으면 Daskin과 Dean (2004)에 제시된 모델은 구축 할 합리적인 스케치를 제공합니다.
답변
찾고있는 위치 문제의 유형은 Weber 문제와 다중 Weber 문제가 가장 잘 알려진 (그리고 가장 단순한) 평면 위치 문제 입니다. Drezner 는 문제에 대한 멋진 개요와 "Weizfeld의 절차"라는 솔루션 절차를 제공합니다. 다중 Weber 문제 의 경우 " 쿠퍼의 위치 할당 휴리스틱 "(또는 그 라인을 따라있는 어떤 것) 이라고하는 간단하고 다소 유명한 휴리스틱이 있습니다.
다중 Weber 문제를 비선형 혼합 정수 프로그램과 볼록 최적화 문제의 차이로 공식화 할 수 있다는 것을 알고 있습니다. 그러나 선형 프로그램으로 공식화 할 수 없습니다.$\mathcal{P=NP}$) 그대로 $\mathcal{NP}$-하드 최적화 문제.
내가 올바르게 이해한다면 수요 노드 세트가 주어지고 각 수요 노드와 할당 된 시설 사이의 거리 합계를 최소화하기 위해 평면 어디에서나 유한 한 수의 시설을 찾고 싶습니까?
시설 위치 문제에 대한 문헌 외에도 클러스터링 방법 (예 : K- 평균 알고리즘 및 유사)에서 유용한 도구와 Steiner 트리 문제를 찾을 수 있습니다.
K- 평균 알고리즘은 각 클러스터의 중심이있는 클러스터를 계산하여 클러스터의 점에 대한 거리 제곱의 합을 최소화합니다. 거리가 제곱되지 않은 유사한 버전은 p- 중앙값 문제입니다. 두 가지 모두에 대해 일부 열 생성 기반 접근 방식이 제안되었습니다 (예 : 이 문서 참조) .
유클리드 스타이너 트리 문제는 정확히 언급하는 문제가 아니라, 예를 들어,이 문헌에서 유용한 모델링 트릭이있을 수 있습니다 본 논문 .