고 덕 지도 노선 계획 - 스쿨버스 운행 의 최 적 화 된 노선 알고리즘 획득

최근 에 스쿨버스 운행 노선 계획 의 개발 임 무 를 하고 있 습 니 다. 가장 좋 은 노선 을 얻 기 위해 저 는 모든 사이트 가 구성 할 수 있 는 노선 을 나열 한 다음 에 이런 조합 한 노선 의 총 거 리 를 계산 하고 마지막 으로 전체 거리 가 가장 짧 은 것 이 바로 최종 적 인 최 적 노선 입 니 다.

       :
1.               ,             ,             
2.    ,      18   (    +16     +    )
3.  API                  ,         
4.    A、B、C    ,    A->B、B->A 、A->C、C->A、B->C、C->B         ,         n*(n-1)

두 사이트 간 거리의 bean

@Data
public class SiteDistance {
    private Long startId;	//    Id
    private Long endId;		//    Id
    private Double distance;//     
}

다음은 스쿨버스 운행 의 가장 좋 은 경 로 를 얻 기 위 한 알고리즘 입 니 다.

/**
 * @Description siteIds List            ,siteDistances List                 
 * @Param
 * @return
 * @Date 2019/2/25 9:48
 **/
public Map getBestRoute(List siteIds,  List siteDistances){
    //     , "startId-endId" key,distance value   map 
    Map distanceMap = new HashMap<>();
    for (SiteDistance siteDistance: siteDistances) {
        distanceMap.put(siteDistance.getStartId()+"-"+siteDistance.getEndId(), siteDistance.getDistance());
    }
    //              
    List> idCombine = new ArrayList<>();
    perm(siteIds, 1,siteIds.size()-1, idCombine);
    //            
    return getMinDistanceRoute(idCombine, distanceMap);
}

/**
 * @Description            
 * @Date 2019/2/25 8:46
 **/
public Map getMinDistanceRoute(List> idCombine, Map distanceMap){
    Map result = new HashMap<>();
    Double minTotal = null;//    
    int minIndex = 0;//    
    for (int i=0;i routeSites = new ArrayList<>();
        routeSites.addAll(idCombine.get(i));
        routeSites.add(routeSites.get(0));
        //          
        Double totalDistance = getTotalDistance(routeSites, distanceMap);
        if(null == minTotal || totalDistance < minTotal){
            minTotal = totalDistance;//         
            minIndex = i;//         
        }
    }
    //               
    List routeSites = new ArrayList<>();
    routeSites.addAll(idCombine.get(minIndex));
    routeSites.add(routeSites.get(0));
    result.put("routeSites", routeSites);
    result.put("totalDistance", minTotal);
    return result;
}

//          
public double getTotalDistance(List routeSites, Map distanceMap){
    Double totalDistance = 0d;
    for(int i = 1;i end
 */
public static void perm(List list,int begin,int end, List> result){
    //       ,                ，     ，       
    if(begin==end){
        result.add(list);
        List arr = new ArrayList<>();
        for(int i=0;i<=end;i++){
            arr.add(list.get(i));
            //System.out.print(list.get(i) + " ");
        }
        //System.out.println();
        result.add(arr);
        return;
    }else{
        //for   begin -> end        begin    ，      
        for(int j=begin;j<=end;j++){
            swap(list,begin,j);  //for   begin -> end        begin    
            perm(list,begin+1,end, result); //  begin    ，   begin+1 -> end         
            swap(list,begin,j); //          
        }
    }
}
public static void swap(List list,int i,int j){
    Long temp=list.get(i);
    list.set(i, list.get(j));
    list.set(j, temp);
}