首先区分各种场景
从配送源区分为
单源正权值最短路径
多源正权值最短路径
从配送场景区分
单源正权值配送时效最短路径
多源正权值配送时效最短路径
针对单源正权值最短路径有了基本代码,亲测5000 客户用时7043ms,时间复杂度O(N*(N-1))。代码如下
代码语言：javascript复制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）
论文纯英文
代码语言：javascript复制paper（A Two-Stage Fast Heuristic for Food Delivery Route Planning Problem）
https://s3plus.meituan.net/v1/mss_e63d09aec75b41879dcb3069234793ac/file/学术论文篇.pdf待续...
