본 논문은 그래프의 볼록 집합에서 최단 경로 문제(SPP-GCS)에 대한 최적성 보장 및 근최적 경로를 찾기 위해 기존의 볼록 프로그래밍 기반 접근 방식과 휴리스틱 정보를 융합하는 새로운 알고리즘을 제시한다. A* 알고리즘에서 영감을 받은 이 방법은 지정된 정점 부분 집합에서 최초 우선 탐색과 같은 절차를 시작하여 더 이상의 확장이 불가능하거나 유익하지 않을 때까지 반복적으로 확장한다. 일반적으로 최적화 문제에 대한 경계가 있는 해를 구하려면 이완 문제를 풀고, 이완된 해를 실행 가능한 해로 수정한 다음, 두 해를 비교하여 경계를 설정하는 과정을 거친다. 그러나 SPP-GCS의 경우, 특히 유클리드 이동 비용이 있는 경우 이 과정을 역으로 수행하는 것이 더 유리함을 보여준다. 즉, 우선 A를 사용하여 SPP-GCS에 대한 실행 가능한 해를 찾은 다음, A에 의해 탐색된 정점으로 제한된 볼록 이완 문제를 풀어 이완된 해를 구하고, 마지막으로 두 해를 비교하여 경계를 도출한다. 볼록 프로그램의 크기 및 계산 시간 측면에서 기존 접근 방식에 비해 알고리즘의 장점을 강조하는 수치 결과를 제시한다.
