算法:关于外卖配送最短路径问题

首先区分各种场景

从配送源区分为

单源正权值最短路径

多源正权值最短路径

从配送场景区分

单源正权值配送时效最短路径

多源正权值配送时效最短路径

针对单源正权值最短路径有了基本代码,亲测5000+客户用时7043ms,时间复杂度O(N*(N-1))。代码如下

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

        HashMap<String, BigDecimal> hashMap = new HashMap<>();
        BigDecimal temp = BigDecimal.ZERO;
        if (map.isEmpty()) {
            return;
        } else {
            for (Map.Entry<String, String> entry : map.entrySet()) {

                Random random = new Random();
                BigDecimal db = new BigDecimal(random.nextInt(100));

                BigDecimal baseKilometreNum = db.setScale(2,BigDecimal.ROUND_DOWN);
                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());
                list1.add(entry1.getKey());
                log.info("开始送达至->{}",entry1.getKey());
            }

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

    }

面对多源正权值最短路径时，首先考虑外卖员自身距离商家的位置，然后按照最短路径来看把每个商家也视为客户,这样就是先去第一个最近的商家取餐,然后看下一个距离最近的点，有可能是客户点，有可能是商家，但最终就转化为第一种情况了,如果加入权重为配送时效的话就不一样了，从距离优先转化为最近时效问题。

涉及算法如下

动态规划（dynamic programming ）、

列生成算法（column generation）、

分支切割（branch-and-cut）、

分支切割定价（branch-and-cut-and-price）等精确计算算法，

禁忌搜索（tabu search）、

模拟退火（simulated annealing algorithm）、

基于插入搜索的算法（insertion-based heuristic）、

自适应大邻域搜索（adaptive large neighborhood search）、

变深度搜索（variable-depth search algorithm）

以及启发式算法（Two-Stage Fast Heuristic）

论文纯英文

paper（A Two-Stage Fast Heuristic for Food Delivery Route Planning Problem）
https://s3plus.meituan.net/v1/mss_e63d09aec75b41879dcb3069234793ac/file/%E5%AD%A6%E6%9C%AF%E8%AE%BA%E6%96%87%E7%AF%87.pdf

待续…