사이트 선택 문제, 모델 및 알고리즘

배경음악 : Demons - Imagine Dragons

최근 위치 선정 문제를 연구하다가 그나저나 요약을 해봤습니다.

이 기사는 전통적인 통계 기반 사이트 선택에 관한 제1부입니다.

현대 사이트 선택 문제에 머신러닝과 딥러닝을 적용하는 방법에 대해서는 나중에 또 다른 기사가 나올 예정입니다.

Baidu에서 사이트 선택 문제는 운영 연구의 고전적인 문제 중 하나입니다. 부지선정 문제는 공장, 창고, 응급처치센터, 소방서, 쓰레기 처리장, 물류센터, 미사일 창고 등의 부지선정 등 생산과 생활, 물류는 물론 군에서도 널리 활용되고 있다. 입지 선정은 장기적으로 가장 중요한 결정 중 하나입니다. 입지 선정의 품질은 서비스 방법, 서비스 품질, 서비스 효율성, 서비스 비용 등에 직접적인 영향을 미쳐 수익과 시장 경쟁력에 영향을 미치고 심지어 기업의 운명을 결정하기도 합니다. . 좋은 입지 선정은 사람들의 삶을 편리하게 하고, 비용을 절감하며, 이익과 시장점유율을 확대하고, 서비스 효율성과 경쟁력을 향상시키게 됩니다. 잘못된 입지 선정은 종종 큰 불편과 손실을 가져오거나, 심지어 재난을 가져오기도 합니다. 경제적, 사회적, 군사적 중요성이 매우 크다.

소위 위치 문제는 최적의 목표를 달성하기 위해 계획 구역에서 하나 이상의 시설 위치를 선택하는 것을 말합니다.

추신: 이 '시설'은 공장이나 호텔 등의 개체일 수도 있습니다. 우리는 통일을 위해 모두 시설이라고 부릅니다.

정의에 따르면 시설, 계획면적, 위치(거리), 목표 등 4가지 요소를 하나씩 파악해 보자.

공간적 차원에 따라. 시설 구분에 따라 위치선정 문제는 다음과 같이 나눌 수 있다.

또한, 계획된 시설 수에 따라 위치선정 문제는 다음과 같이 나눌 수 있다.

계획지역의 구조에 따라 위치선정 문제는 다음과 같이 나눌 수 있다. 위치문제를 다음과 같이 나눈다.

시설의 위치를 ​​결정하는 목적은 시설물의 위치를 ​​결정하는 목적이기 때문에 아마도 거리가 더 적절할 것이다. 시설과 다른 수요 지점 사이의 거리.

시설물과 수요지점 위치의 관계에 따라 얻어야 할 거리는 다음과 같이 나눌 수 있다.

우리의 목표는 최적의 위치를 ​​찾는 것이므로 최적의 위치는 무엇인가? ? 즉, 이 목표를 어떻게 정량화할 것인가? 최단 거리, 최저 비용, 최대 이익 또는 기타 맞춤형 목표?

대상 수에 따라 위치 선택 문제는 다음과 같이 나눌 수 있습니다.

어쩌면 위 더미를 읽은 후에도 위치 선택에 대한 명확한 개념이 아직 없을 수도 있습니다. 문제가 있어서 정리했습니다. 세 가지 위치 문제 중 가장 기본적인 문제입니다. 현재 부지선정의 문제점 중 일부는 수용능력 제한이 없는 시설에 대한 부지선정의 문제 등 확장(또는 증설)이다.

연구: 대체 시설 세트에서 모든 수요 지점이 서비스되고 수요 지점에서 가장 가까운 시설까지의 가중 거리의 합이 최소화되도록 p 시설을 선택하는 방법.

이는 다음 정수 프로그래밍 모델로 표현될 수 있는 MinSum 문제입니다.

응용 시나리오: 물류 분야에서 널리 사용됩니다. 가중 거리는 운송을 나타냅니다. 비용이며 목표는 총 비용을 최소화하는 것입니다.

연구: 대체 시설 세트에서 모든 수요 지점이 서비스되고 각 수요 지점에서 가장 가까운 시설까지의 최대 거리가 최소화되도록 p 시설을 선택하는 방법.

이는 MinMax 문제로, 다음 정수 프로그래밍 모델로 표현될 수 있습니다(기호 설명은 위와 유사함).

응용 시나리오: 비상시설의 위치 선택, 경찰서, 소방서, 병원 등은 가능한 한 빨리 어떤 장소로든 이동해야 합니다.

커버리지 문제는 최대 커버리지 문제와 세트 커버리지 문제의 두 가지 범주로 나뉩니다.

적용 시나리오 : 이동 기지국 위치 선정, 물류센터 위치 선정 등 커버리지를 추구하는 시나리오.

알고리즘에 대한 설명은 늘 게으른 편이라 설명하기가 너무 번거로워서 그냥 요약해서 만들어서 관심있으시면 제가 직접 검색해보겠습니다.

해결 방법에 따라 다음과 같이 나눌 수 있다.

'정성적'은 이해하기 쉽고 통계적 유의성을 요구하지 않으나, 연구자의 경험과 관련 기술을 통해 이루어진다. , 연구 대상의 성격과 가능한 영향에 대한 통찰력을 효과적으로 얻을 수 있습니다.

일반적으로 단계는 다음과 같습니다.

일반적으로 사용되는 평가 방법에는 가중 요인 채점 방법, 퍼지 종합 평가 방법, 위험 기반 방법, 델파이 방법(Delphi)

정성적 방법에는 명백한 단점이 있습니다. 주관성에 큰 영향을 받습니다. 그러나 실제 과정에서는 정책이나 환경의 영향 등 많은 것을 정량화할 수 없기 때문에 정성적 분석은 매우 실질적인 의미를 가지며 정량적 분석을 보완하는 경우가 많습니다.

매우 효율적인 알고리즘을 소개하겠습니다. 반드시 최고는 아닐 수도 있지만, 많은 작가들이 이에 의존하여 일부 기사를 작성했습니다. 하하하~

목표는 N개의 대체 위치 중에서 시작하여 p개 위치를 선택하여 목표가 최적이 되도록 시설을 구축하는 것입니다.

이 알고리즘의 장점과 단점 :

시간이 너무 짧기 때문에 너무 깊이 공부할 시간이 없어서 다른 알고리즘은 최선을 다하지 않을 것입니다 ~

다음에 시도해 보세요. Python을 사용해 몇 가지 실제 문제를 해결해 보세요.