leaflet에서 D3를 이용한 TSP(traveling salesman problem) 활용

Leaflet에서 D3를 이용한 TSP(Traveling Salesman Problem) 활용

> 서비스바로가기

 

Leaflet에서 D3 라이브러리를 이용하여 TSP를 구현 후, 지도상에 사용자가 지정한 위치를 단 한번만 방문하고 시작점으로 돌아오는 TSP를 구현하였다. 

1.TSP(traveling salesman problem)란?

 

여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을때, 모든 도시들을 단 한번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 것이다. 이는 조합 최적화 문제의 일종으로 이 문제는 NP-난해에 속하며, 흔히 계산 복잡도 이론에서 해를 구하기 어려운 문제의 대표적인 예로 많이 다룬다.

참조한 소스가 성능적으로 우수하지는 않습니다. 지도 조회 도구(Leaflet)과 시각화 라이브러리(D3)를 함께 사용하는 예시로 참조하십시오. 인터넷에는 TSP를 해결하는 다양한 응용 사례가 존재합니다.

(참조 : 위키백과 https://ko.wikipedia.org/wiki/%EC%99%B8%ED%8C%90%EC%9B%90_%EB%AC%B8%EC%A0%9C)

 

2. 구현

2.1 leaflet

leaflet을 이용한 웹페이지 지도 발행은 [꿀팁-OpenLayers, Leaflet] > [OpenLayers와 Leaflet에서 Vworld 배경지도 이용하기]을 참고하세요.

D3 라이브러리를 이용하기 위해 leaflet의 지도에 svg 추가가 필요합니다. 프로그웍스 Openlayers 및 Leaflet에서 제공하는 데이터 및 배경지도는  국가공간정보포털 오픈마켓 데이터 및 VWorld를 이용하고 있습니다. <script></script>부분은 아래와 같습니다.

• 3행 : leaflet 지도 불러오기
• 4행 : 배경지도 Vworld 활용
• 12행 : leaflet Map에 svg 추가(D3.js 라이브러리를 사용하기 위해 반드시 추가 필요)

 

<script type="text/javascript">
$(document).ready(function(){
    var    letMap = L.map('letMap').setView([37.52470308242787, 126.9234],12);
        L.tileLayer('http://xdworld.vworld.kr:8080/2d/Base/201802/{z}/{x}/{y}.png').addTo(letMap);
        letMap.options.minZoom = 12;
        letMap.options.maxZoom = 12;
        letMap.dragging.disable();
        letMap.touchZoom.disable();
        letMap.doubleClickZoom.disable();
        letMap.scrollWheelZoom.disable();
        
        L.svg().addTo(letMap);
            
});
</script>

 

2.2 D3(Data Drivened Document).js + TSP

D3(Data Drivened Document’).js는 웹에서 데이터를 표현하기에 적합한 도구로 특히, 인터랙티브 데이터 시각화에 많이 사용되고 있는 자바스크립트 기반 라이브러리입니다. D3.js는 HTML, SVG(Scalable Vector Graphics), CSS를 사용해 데이터를 시각적 결과물로 나타낸다. 위 leaflet <script></script> 12행에 leaflet Map에 svg를 추가한 이유가 D3.js 라이브러리를 이용하기 위함이었습니다.

다른방법을 알고 계신다면 알고계신 방법을 사용하셔도 무방하지만 저는 svg를 사용하겠습니다. 아래 <script></script>부분은 d3.js를 이용하여 TSP를 구현한 부분입니다. 소스가 상당히 길지만 정리된 내용을 보시면 금방 이해를 하실 수 있으실 겁니다.

D3.js 및 TSP분석을 위해 underscore.min.js 및 d3.v3.min.js파일을 추가합니다. leaflet map을 이용하기 위해서는 leaflet.js 및 .css파일로 추가하셔야합니다. (참고하기 : 

[꿀팁-OpenLayers, Leaflet] > [OpenLayers와 Leaflet에서 Vworld 배경지도 이용하기])

<link type="text/css" rel="stylesheet" href="<c:url value='/css/leaflet/leaflet.css'/>" />
 
<script src="<c:url value='/js/D3/d3.v3.min.js'/>"></script>
<script src="<c:url value='/js/leaflet/leaflet.js'/>"></script>
<script src="<c:url value='/js/TSP/underscore.min.js'/>"></script>

D3.js 및 TSP 구현부분을 확인하기 전 알아야 할 부분이 있다.

TSP는 NP-hard 문제에 속하는 것으로 완전 탐색 연결을 위해서는 0(N!)이라는 시간 복잡도가 나온다(Factorial). 이는 10개만 탐색해도 3,628,800개 라는 값이 나오며, 웹페이지에서 구현 시, 페이지가 멈추는 현상이 생긴다.... 그렇기 때문에 포인트 개수에 제한을 두고 개발하였다.(최대 9개 지점 선택 가능)

- 참조 : Factorial( https://ko.wikipedia.org/wiki/%EA%B3%84%EC%8A%B9 )

- NP-Hard란?

비 결정론적 튜링머신으로 다항시간 내에 풀 수 있는 문제로 특정 상태에서 움직일 수 있는 상태의 개수가 하나로 정해져 있지 않은 경우를 말한다.

지금부터 <script></script>부분을 살펴보겠습니다.

• 2행~12행 : d3.js에서 tsp를 구현하기 위해 사용한 변수 선언
• 14행 : d3.js를 이용한 TSP 구현 부분
• 23행 : leaflet map하위의 svg부분을 변수 svg에 선언
• 23행~42행 : marker와 path 부분 선언
• 44행 : d3 click 이벤트 선언
• 60행 : 지도 클릭에 따른 위치정보 추출 및 지도 위 포인트 표시 function 실행
• 65행 : TSP 실행(RUN)
• 81행 : TSP 초기화(RESET)
• 90행 : 지도 클릭에 따른 포인트 표시(시작점은 빨강/그외 지점은 검은색)
• 119행 : TSP 분석을 통한 path 그리기
• 137행~151행 : 선택된 위치를 이용한 TSP 비용 계산(Cost)
• 151행 : 배열에 담은 선택한 포인트를 랜덤으로 순서 생성 및 Cost 계산 function 실행
• 163행 : TSP 분석에 필요한 최소 비용 및 경로 추출 반복 횟수 만큼(팩토리얼:factorial) 새로운 방문 순서 및 비용 계산(RandomPath 및 Cost부분 function 실행)
• 176행 : TSP 옵션 정보를 이용한 path, cost 값 정의 및 TSP 완전 탐색이 진행되는 부분

• 214행~230행 : TSP 반복 횟수 지정 부분(완전탐색 횟수 지정 부분)

<script type="text/javascript">
    var tspCount,
        infoText,
        echoText,
        clickCoords,
        featureElement;
    var resultCost = [];    
    var checkRun = false;
    
    var dotscale = 12,
        nodes = []
        cities = [];
        
    (function (d3, _) {
        "use strict"
        
        drawFeatures();  
        
        function drawFeatures() {
            
            var path = d3.geo.path();
            var svg = d3.select("#letMap").select("svg");
            svg.append("svg:defs")
                .append("svg:marker")
                  .attr("id", "arrow")
                  .attr("viewBox", "0 0 10 10")
                  .attr("refX", 15)
                  .attr("refY", 5)
                  .attr("markerWidth", 6)
                  .attr("markerHeight", 6)
                  .attr("orient", "auto")
                .append("svg:path")
                  .attr("d", "M0,0L10,5L0,10");
    
              svg.append("rect")
                  .attr("class", "background")
                .attr("height","686")
                .attr("width","100%")
                  .on('click', clickMap);
              
              var g = svg.append("g")
                .attr("id", "baseSVG");
              
              function clickMap () {
                  if(checkRun == true){
                      cities = [];
                    tspCount = null;
                    $('#countInfo').html('0');
                    svg.selectAll('circle').remove();
                    svg.selectAll('path.connection').remove();
                    document.getElementById("echoText").value = "";
                    checkRun = false;
                  }
                  
                  if(cities.length >= 9){
                      alert("위치선택은 9개까지 가능합니다.");
                      return;
                  }
                  
                  cities.push(d3.mouse(this));
                clickCoords = d3.mouse(this);
                drawCities();
            }
              
              function run() {
                if(cities.length<2){
                    alert("2점 이상의 위치를 지도에 표시하세요.");
                    return;
                }
                
                  tspCount = null;
                $('#countInfo').html("TSP 0 번 분석");
                optsNum();
                svg.selectAll('path.connection').remove();
                var answer = sanTsp(cities, {});
                drawPaths(answer.initial.path);
                setTimeout(function () { drawPaths(answer.final.path); }, 1000);
                checkRun = true;
            }
              
            function reset () {
                cities = [];
                tspCount = null;
                $('#countInfo').html('0');
                svg.selectAll('circle').remove();
                svg.selectAll('path.connection').remove();
                document.getElementById("echoText").value = "";
            }
            
            function drawCities() {
                if($(".city").attr("cx") == null && $(".city").attr("cx") == null){
                    svg.selectAll('circle').data(cities).enter()
                    .append('circle')
                        .attr('cx', function (d) { return d[0]; })
                        .attr('cy', function (d) { return d[1]; })
                        .attr('r', dotscale)
                        .attr('fill','red')
                        .attr('stroke','black')
                        .attr('opacity','0.7')                        
                        .attr('class', 'city');
                }else{
                    
                    svg.selectAll('circle').data(cities).enter()
                        .append('circle')
                            .attr('cx', function (d) { return d[0]; })
                            .attr('cy', function (d) { return d[1]; })
                            .attr('r', dotscale)
                            .attr('fill','black')
                            .attr('stroke','black')
                            .attr('opacity','0.7')
                            .attr('class', 'city');
                }
                
                echoText = document.getElementById("echoText");
                
                echoText.value += cities.length+"번째 위치를 선택하였습니다. (위치정보"+clickCoords+") \n";
            }
            
            function drawPaths(ipath) {
                var paths = _.map(_.zip(ipath.slice(0,ipath.length-1), ipath.slice(1)), function (pair) {
                    return [cities[pair[0]], cities[pair[1]]]
                }).slice();
    
                svg.selectAll('path.connection').remove();
                svg.selectAll('path.connection').data(paths).enter()
                    .append('path')
                        .attr('d', function(d) {
                        var dx = d[1][0] - d[0][0],
                            dy = d[1][1] - d[0][1],
                            dr = Math.sqrt(dx * dx + dy * dy);
                        return "M" + d[0][0] + "," + d[0][1] + "A" + dr + "," + dr + " 0 0,1 " + d[1][0] + "," + d[1][1];
                      })
                        .attr('class', 'connection')
                        .attr("marker-end", "url(#arrow)");
            }
 
            function ccCost(c1, c2) {
                return Math.sqrt(Math.pow(c1[0] - c2[0], 2) + Math.pow(c1[1] - c2[1], 2));
            }
            function sum(arr) {
                return _.reduce(arr, function (x,y){ return x+y; }, 0);
            }
            function pathCost(path) {
                var zipped = _.zip(path.slice(0,path.length-1), path.slice(1));
                
                return sum(_.map(zipped, function (pair) {
                    return ccCost(cities[pair[0]], cities[pair[1]]);
                }));
            }
            
            function randomPath() {
                var n = cities.length
                    ,    path = [0] // wlog, begin with 0
                    , rest = _.range(1, n);
 
                while (rest.length > 0) {
                    var i = Math.floor(Math.random() * rest.length);
                    path.push(rest[i]);
                    rest.splice(i, 1);
                }
                return path.concat([0]);
            }
            function doRound(cur) {
                var newpath = randomPath(),
                    newcost = pathCost(newpath);
                if ((newcost < cur.cost)) {
                    return {
                        path: newpath,
                        cost: newcost
                    };
                } else {
                    return cur;
                }
            }
            
            function san(opts) {
                var path = randomPath(),
                    cost = pathCost(path),
                    cur = {
                        path: path,
                        cost: pathCost(path)
                    },
                    answer = {
                        initial: cur
                    },
                    i;
                
                console.log('Starting SAN-TPS', cur);
                var firstCur = cur
                
                if(cities.length == 9){
                    opts.N = opts.N*0.75;
                }
                for (i = 1; i <= opts.N; i++) {
                    
                    cur = doRound(cur);
                    if(cur.cost < firstCur.cost){
                        cur = cur;
                    }else{
                        cur = firstCur;
                    }
                    if(opts.N >= 40320){
                        opts.N = opts.N-100;
                    }
                    
                    document.getElementById("countInfo").innerHTML = "TSP " + i + "번 분석 ";
                }
                
                console.log('Finished SAN-TPS', cur);
                answer.final = cur;
                return answer;
            }
            
            function optsNum(){
                for (var i = cities.length; i >= 1; i--) {
                    if(tspCount == null){
                        tspCount = i;
                    }else{
                        tspCount = tspCount * i;
                    }
                }
            }
            
            function sanTsp(cities, opts) {
                opts = opts || {};
                opts.N = tspCount;
                return san(opts);
            }
    
            d3.select('#run').on('click', run);
            d3.select('#reset').on('click', reset);
    
            console.log('Loaded!');
            
        }
        
    })(d3, _);
</script>

 

2.3 Leaflet + D3(Data Drivened Document).js + TSP <Body></Body>부분

• 2행 : L.map에서 선언한 Id와 div태그에 사용한 아이디는 동일하여야 한다.

<body>
    <div id="letMap"></div>
    <h1>Location Info</h1>
    <div id ="countInfo">TSP 0 번 분석</div>
    <textarea id="echoText" rows="10" cols="310"></textarea>
    <button id="run">Run</button>
    <button id="reset">Reset</button>            
</body>

 

3. 테스트 및 결과

테스트 시나리오는 사용자가 임의의 지점은 선택하고 그에 따른 TSP 결과 도출로 진행

구현된 TSP는 별도의 가중치가 없으며, 오직 거리를 이용하여 TSP를 구현하였으며, 직선으로 거리를 표시하고 계산하였다.

3.1 테스트 

1. 임의지점 선택에 따른 위치정보 표시 및 선택 개수 제한 유무

(임의 지점 : 부천시청,.가톨릭대학교성심교정, 매봉산, 서울역, 동덕여자대학교, 한양대학교 서울캠퍼스, 대공원입구, 영등포역, 광명시청 총 9개 지점)  

2. TSP 실행 및 화면 표출

3. TSP 분석 횟수 표시

4. 초기화

 

3.2 결과화면