이 논문은 도로망을 주어진 개수의 조밀하고 연속적인 구역으로 분할하는 엣지 기반 연속 p-메디안(ECpM) 문제를 소개한다. 네트워크 거리를 반영한 두 가지 이진 계획 모델을 제시하는데, 첫째는 지수 개의 컷셋 기반 제약으로 연속성을 표현하며 분리 기법과 결합한 분기절단(B&C) 알고리즘을 쓰고, 둘째는 다항 개의 최단경로 제약으로 연속성을 표현해 상용 솔버로 풀 수 있다. 2,700개 이상의 노드와 3,400개에 가까운 엣지를 가진 도로망, 960만 개 이상의 이진 변수를 갖는 모델에서 실험한 결과, 최단경로 기반(SPC) 모델은 컷셋 기반 B&C 대비 최대 17배의 계산 속도 향상을 보였다. SPC 제약은 연속성이 요구되지 않는 단순화된 엣지 기반 p-메디안(EpM) 모델에 대해서도 초유효 부등식으로 작동해 일부 최적해를 배제할 수 있음이 확인됐다. 기존의 컷셋 기반 모델은 12시간 내에 어떤 테스트 인스턴스에서도 실행가능해를 찾지 못한 반면, SPC 기반 작업균형 모델은 대부분을 최적으로 해결했다.

• •도로망을 지정된 개수의 조밀·연속 구역으로 나누는 엣지 기반 p-메디안(ECpM) 문제와 두 이진계획 모델 제시
• •최단경로 기반(SPC) 제약 모델이 컷셋 기반 분기절단(B&C) 대비 최대 17배 빠른 계산 속도 달성
• •960만 개 이상 이진변수를 가진 2,700+ 노드 도로망 실험에서 성능 검증
• •기존 컷셋 기반 모델은 12시간 내 실행가능해를 못 찾은 반면 SPC 기반 모델은 대부분 최적해 도출