您的位置 首页 java

java 外卖最短路径问题

当同一个商家面对N个客户订单时,如何规划一个科学送餐路线是一个常见问题,面对类比最短路径问题,实际项目中该如何解决?

假设商家接单5个客户,ABCDE,每次客户距离是需要计算,但也可以当客户下单那一刻就计算出当前客户到仓库的距离,这样能够尽快算出最短路径,但是客户与客户之间的距离是不能够避免实时计算的。

如图

每次送达的一个客户即视为新的起点,一开始我想用滑动窗口去解决,但是每次其实遍历的集合都是动态重组的,窗口不好确定,如果N个客户遍历的时间复杂度是N*(N-1),每次以起点计算距离最短的客户,即总距离最短。

代码实现如下:

  public  static   void  test2() {
         HashMap <String,  String > map = new  hashMap <>();
        map.put("A", "26.058414172615348,119.34194296172531");
        map.put("B", "26.103149931615339,119.29926188348196");
        map.put("C", "26.150459342276882,119.34021969660213");
        map.put("D", "26.079434976522675,119.18654236526695");
        String warehouse = String.format("%s,%s", "26.006096", "119.287713");
        backTracking(map, warehouse);
    }

     private  static void backTracking(HashMap<String, String> map, String warehouse) {

        HashMap<String,  BigDecimal > hashMap = new HashMap<>();
        BigDecimal temp = BigDecimal.ZERO;
        if (map.isEmpty()) {
            return;
        } else {
            for (Map.Entry<String, String> entry : map.entrySet()) {
//伪代码部分
                BigDecimal baseKilometreNum = Utils.getCarDistance(String origins, String destinations);
                if (temp.compareTo(BigDecimal.ZERO) == 0) {
                    temp = baseKilometreNum;
                    hashMap.put(entry.getKey(), baseKilometreNum);
                } else {
                     boolean  flag = true;
                    for (Map.Entry<String, BigDecimal> entry1 : hashMap.entrySet()) {
                        flag = entry1.getValue().compareTo(baseKilometreNum) > 0 ? true : false;
                    }
                    if (flag) {
                        hashMap.clear();
                        hashMap.put(entry.getKey(), baseKilometreNum);
                    }
                }
            }
            for (Map.Entry<String, BigDecimal> entry1 : hashMap.entrySet()) {
                warehouse = map.get(entry1.getKey());
                map.remove(entry1.getKey());
                log.info("开始送达致->{}",entry1.getValue());
            }

        }
        //移除此元素,且最短距离设置为下一次仓库
        backTracking(map, warehouse);

    }  

如果需要计算距离部分代码,我这边有百度API的免费key可以一样调用。

文章来源:智云一二三科技

文章标题:java 外卖最短路径问题

文章地址:https://www.zhihuclub.com/190422.shtml

关于作者: 智云科技

热门文章

网站地图