From 71a5ae03389119dc6975d7cfb87e63601f3c5305 Mon Sep 17 00:00:00 2001
From: Junjie <fallin.jie@qq.com>
Date: 星期四, 02 四月 2026 16:52:22 +0800
Subject: [PATCH] #算法优化
---
src/main/java/com/zy/core/thread/impl/ZyStationV5Thread.java | 46 +++
src/main/java/com/zy/asrs/service/impl/BasMapEditorServiceImpl.java | 17 +
src/test/java/com/zy/common/utils/NavigatePerformanceBenchmarkTest.java | 354 +++++++++++++++++++++++++++
src/main/java/com/zy/core/config/NavigateMapCacheInitializer.java | 31 ++
src/main/java/com/zy/common/model/NavigateNode.java | 3
src/main/java/com/zy/asrs/controller/BasMapController.java | 20 +
src/main/java/com/zy/core/enums/RedisKeyType.java | 1
src/main/java/com/zy/common/utils/NavigateSolution.java | 271 ++++++++++++++++----
8 files changed, 687 insertions(+), 56 deletions(-)
diff --git a/src/main/java/com/zy/asrs/controller/BasMapController.java b/src/main/java/com/zy/asrs/controller/BasMapController.java
index a26a4b3..a3ed90e 100644
--- a/src/main/java/com/zy/asrs/controller/BasMapController.java
+++ b/src/main/java/com/zy/asrs/controller/BasMapController.java
@@ -13,6 +13,7 @@
import com.core.common.BaseRes;
import com.core.common.Cools;
import com.core.common.R;
+import com.zy.common.utils.NavigateSolution;
import com.zy.common.web.BaseController;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.*;
@@ -71,16 +72,29 @@
@ManagerAuth
public R add(BasMap basMap) {
basMapService.save(basMap);
+ if (basMap != null && basMap.getLev() != null) {
+ NavigateSolution.refreshMapCache(basMap.getLev());
+ }
return R.ok();
}
- @RequestMapping(value = "/basMap/update/auth")
+ @RequestMapping(value = "/basMap/update/auth")
@ManagerAuth
public R update(BasMap basMap){
if (Cools.isEmpty(basMap) || null==basMap.getId()){
return R.error();
}
+ BasMap oldBasMap = basMapService.getById(basMap.getId());
basMapService.updateById(basMap);
+ if (oldBasMap != null && oldBasMap.getLev() != null) {
+ NavigateSolution.clearMapCache(oldBasMap.getLev());
+ }
+ Integer refreshLev = basMap.getLev() != null
+ ? basMap.getLev()
+ : oldBasMap == null ? null : oldBasMap.getLev();
+ if (refreshLev != null) {
+ NavigateSolution.refreshMapCache(refreshLev);
+ }
return R.ok();
}
@@ -88,7 +102,11 @@
@ManagerAuth
public R delete(@RequestParam(value="ids[]") Integer[] ids){
for (Integer id : ids){
+ BasMap basMap = basMapService.getById(id);
basMapService.removeById(id);
+ if (basMap != null && basMap.getLev() != null) {
+ NavigateSolution.clearMapCache(basMap.getLev());
+ }
}
return R.ok();
}
diff --git a/src/main/java/com/zy/asrs/service/impl/BasMapEditorServiceImpl.java b/src/main/java/com/zy/asrs/service/impl/BasMapEditorServiceImpl.java
index 77f6936..193d7f6 100644
--- a/src/main/java/com/zy/asrs/service/impl/BasMapEditorServiceImpl.java
+++ b/src/main/java/com/zy/asrs/service/impl/BasMapEditorServiceImpl.java
@@ -19,6 +19,7 @@
import com.zy.asrs.service.BasStationService;
import com.zy.asrs.service.DeviceConfigService;
import com.zy.asrs.utils.MapExcelUtils;
+import com.zy.common.utils.NavigateSolution;
import com.zy.common.utils.RedisUtil;
import com.zy.core.enums.RedisKeyType;
import com.zy.core.enums.SlaveType;
@@ -111,7 +112,7 @@
persistFloorMap(lev, storedData, toFreeEditorDoc(lev, storedData));
}
rebuildDeviceAndStationSync();
- clearMapCaches();
+ clearMapCaches(levList);
}
@Override
@@ -121,7 +122,7 @@
List<List<HashMap<String, Object>>> storedData = compileToStoredMapData(normalizedDoc);
persistFloorMap(normalizedDoc.getLev(), storedData, normalizedDoc);
rebuildDeviceAndStationSync();
- clearMapCaches();
+ clearMapCaches(Collections.singletonList(normalizedDoc.getLev()));
}
private void persistFloorMap(Integer lev,
@@ -977,9 +978,19 @@
return JSON.toJSONString(list, SerializerFeature.DisableCircularReferenceDetect);
}
- private void clearMapCaches() {
+ private void clearMapCaches(List<Integer> levList) {
redisUtil.del(RedisKeyType.LOC_MAP_BASE.key);
redisUtil.del(RedisKeyType.LOC_MAST_MAP_LIST.key);
+ if (levList == null || levList.isEmpty()) {
+ return;
+ }
+ LinkedHashSet<Integer> distinctLevSet = new LinkedHashSet<>(levList);
+ for (Integer lev : distinctLevSet) {
+ if (lev == null) {
+ continue;
+ }
+ NavigateSolution.refreshMapCache(lev);
+ }
}
private String normalizeType(String type) {
diff --git a/src/main/java/com/zy/common/model/NavigateNode.java b/src/main/java/com/zy/common/model/NavigateNode.java
index 63f2136..e35bbf9 100644
--- a/src/main/java/com/zy/common/model/NavigateNode.java
+++ b/src/main/java/com/zy/common/model/NavigateNode.java
@@ -27,6 +27,9 @@
private String nodeValue;//鑺傜偣鏁版嵁
private String nodeType;//鑺傜偣绫诲瀷
+ public NavigateNode() {
+ }
+
public NavigateNode(int x, int y) {
this.x = x;
this.y = y;
diff --git a/src/main/java/com/zy/common/utils/NavigateSolution.java b/src/main/java/com/zy/common/utils/NavigateSolution.java
index adf527f..211fd98 100644
--- a/src/main/java/com/zy/common/utils/NavigateSolution.java
+++ b/src/main/java/com/zy/common/utils/NavigateSolution.java
@@ -2,20 +2,27 @@
import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.JSONObject;
+import com.alibaba.fastjson.TypeReference;
import com.baomidou.mybatisplus.core.conditions.query.QueryWrapper;
import com.core.common.SpringUtils;
import com.core.exception.CoolException;
import com.zy.asrs.entity.BasMap;
import com.zy.asrs.service.BasMapService;
import com.zy.common.model.NavigateNode;
+import com.zy.core.enums.RedisKeyType;
import com.zy.core.enums.MapNodeType;
import java.util.*;
+import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;
/**
* A*绠楁硶瀹炵幇绫�
*/
public class NavigateSolution {
+
+ private static final long REDIS_MAP_CACHE_TTL_SECONDS = 60 * 60 * 24L;
+ private static final long MAP_CACHE_TTL_MS = 5000L;
+ private static final Map<String, CachedNavigateMap> NAVIGATE_MAP_CACHE = new ConcurrentHashMap<>();
// Open琛ㄧ敤浼樺厛闃熷垪
public PriorityQueue<NavigateNode> Open = new PriorityQueue<NavigateNode>();
@@ -25,6 +32,101 @@
Map<String, Integer> bestGMap = new HashMap<>();
public List<List<NavigateNode>> getStationMap(int lev) {
+ return cloneNavigateMap(loadCachedNavigateMap("station", lev));
+ }
+
+ public List<List<NavigateNode>> getRgvTrackMap(int lev) {
+ return cloneNavigateMap(loadCachedNavigateMap("rgv", lev));
+ }
+
+ private List<List<NavigateNode>> loadCachedNavigateMap(String mapType, int lev) {
+ String cacheKey = mapType + ":" + lev;
+ long now = System.currentTimeMillis();
+ CachedNavigateMap cachedNavigateMap = NAVIGATE_MAP_CACHE.get(cacheKey);
+ if (cachedNavigateMap != null && now - cachedNavigateMap.cacheAtMs <= MAP_CACHE_TTL_MS) {
+ return cachedNavigateMap.navigateMap;
+ }
+
+ List<List<NavigateNode>> redisNavigateMap = loadNavigateMapFromRedis(mapType, lev);
+ if (isValidNavigateMap(redisNavigateMap)) {
+ NAVIGATE_MAP_CACHE.put(cacheKey, new CachedNavigateMap(now, redisNavigateMap));
+ return redisNavigateMap;
+ }
+ clearMapCache(lev);
+
+ List<List<NavigateNode>> navigateNodeList = buildNavigateMap(mapType, lev);
+ cacheNavigateMap(cacheKey, mapType, lev, navigateNodeList, now);
+ return navigateNodeList;
+ }
+
+ public static void refreshAllMapCaches() {
+ BasMapService basMapService = SpringUtils.getBean(BasMapService.class);
+ List<Integer> levList = basMapService.getLevList();
+ if (levList == null || levList.isEmpty()) {
+ NAVIGATE_MAP_CACHE.clear();
+ return;
+ }
+ LinkedHashSet<Integer> distinctLevSet = new LinkedHashSet<>(levList);
+ for (Integer lev : distinctLevSet) {
+ if (lev == null) {
+ continue;
+ }
+ refreshMapCache(lev);
+ }
+ }
+
+ public static void refreshMapCache(Integer lev) {
+ if (lev == null) {
+ return;
+ }
+ long now = System.currentTimeMillis();
+ NavigateSolution navigateSolution = new NavigateSolution();
+ List<List<NavigateNode>> stationMap = navigateSolution.buildNavigateMap("station", lev);
+ navigateSolution.cacheNavigateMap("station:" + lev, "station", lev, stationMap, now);
+ List<List<NavigateNode>> rgvMap = navigateSolution.buildNavigateMap("rgv", lev);
+ navigateSolution.cacheNavigateMap("rgv:" + lev, "rgv", lev, rgvMap, now);
+ }
+
+ public static void clearMapCache(Integer lev) {
+ if (lev == null) {
+ return;
+ }
+ NAVIGATE_MAP_CACHE.remove("station:" + lev);
+ NAVIGATE_MAP_CACHE.remove("rgv:" + lev);
+ RedisUtil redisUtil = SpringUtils.getBean(RedisUtil.class);
+ redisUtil.del(buildRedisCacheKey("station", lev), buildRedisCacheKey("rgv", lev));
+ }
+
+ private void cacheNavigateMap(String localCacheKey,
+ String mapType,
+ int lev,
+ List<List<NavigateNode>> navigateNodeList,
+ long cacheAtMs) {
+ RedisUtil redisUtil = SpringUtils.getBean(RedisUtil.class);
+ redisUtil.set(buildRedisCacheKey(mapType, lev),
+ JSON.toJSONString(navigateNodeList),
+ REDIS_MAP_CACHE_TTL_SECONDS);
+ NAVIGATE_MAP_CACHE.put(localCacheKey, new CachedNavigateMap(cacheAtMs, navigateNodeList));
+ }
+
+ private List<List<NavigateNode>> loadNavigateMapFromRedis(String mapType, int lev) {
+ RedisUtil redisUtil = SpringUtils.getBean(RedisUtil.class);
+ Object cachedValue = redisUtil.get(buildRedisCacheKey(mapType, lev));
+ if (!(cachedValue instanceof String) || ((String) cachedValue).trim().isEmpty()) {
+ return null;
+ }
+ try {
+ return JSON.parseObject((String) cachedValue, new TypeReference<List<List<NavigateNode>>>() {});
+ } catch (Exception ignore) {
+ return null;
+ }
+ }
+
+ private static String buildRedisCacheKey(String mapType, int lev) {
+ return RedisKeyType.NAVIGATE_MAP_TEMPLATE_.key + mapType + "_" + lev;
+ }
+
+ private List<List<NavigateNode>> buildNavigateMap(String mapType, int lev) {
BasMapService basMapService = SpringUtils.getBean(BasMapService.class);
BasMap basMap = basMapService.getOne(new QueryWrapper<BasMap>().eq("lev", lev));
if (basMap == null) {
@@ -32,7 +134,6 @@
}
List<List<JSONObject>> dataList = JSON.parseObject(basMap.getData(), List.class);
-
List<List<NavigateNode>> navigateNodeList = new ArrayList<>();
for (int i = 0; i < dataList.size(); i++) {
List<JSONObject> row = dataList.get(i);
@@ -41,26 +142,33 @@
JSONObject map = row.get(j);
NavigateNode navigateNode = new NavigateNode(i, j);
- String mergeType = map.getString("mergeType");
String nodeType = map.getString("type");
+ String mergeType = map.getString("mergeType");
String nodeValue = map.getString("value");
if(nodeType == null) {
navigateNode.setValue(MapNodeType.DISABLE.id);
- }else if(nodeType.equals("devp") || (nodeType.equals("merge") && mergeType.equals("devp"))) {
+ } else if ("station".equals(mapType)
+ && (nodeType.equals("devp") || (nodeType.equals("merge") && "devp".equals(mergeType)))) {
navigateNode.setValue(MapNodeType.NORMAL_PATH.id);
-
- JSONObject valueObj = JSON.parseObject(map.getString("value"));
- List<String> directionList = valueObj.getJSONArray("direction").toJavaList(String.class);
+ JSONObject valueObj = JSON.parseObject(nodeValue);
+ List<String> directionList = valueObj == null || valueObj.getJSONArray("direction") == null
+ ? new ArrayList<>()
+ : valueObj.getJSONArray("direction").toJavaList(String.class);
navigateNode.setDirectionList(directionList);
- } else if (nodeType.equals("rgv")) {
+ } else if ("station".equals(mapType) && nodeType.equals("rgv")) {
navigateNode.setValue(MapNodeType.NORMAL_PATH.id);
- JSONObject valueObj = JSON.parseObject(map.getString("value"));
-
JSONObject newNodeValue = new JSONObject();
newNodeValue.put("rgvCalcFlag", 1);
nodeValue = JSON.toJSONString(newNodeValue);
- //RGV鏆備笉鎺у埗琛岃蛋鏂瑰悜锛岄粯璁や笂涓嬪乏鍙抽兘鍙蛋
+ List<String> directionList = new ArrayList<>();
+ directionList.add("top");
+ directionList.add("bottom");
+ directionList.add("left");
+ directionList.add("right");
+ navigateNode.setDirectionList(directionList);
+ } else if ("rgv".equals(mapType) && nodeType.equals("rgv")) {
+ navigateNode.setValue(MapNodeType.NORMAL_PATH.id);
List<String> directionList = new ArrayList<>();
directionList.add("top");
directionList.add("bottom");
@@ -77,53 +185,103 @@
}
navigateNodeList.add(navigateNodeRow);
}
-
- return navigateNodeList;
+ return cropNavigateMap(navigateNodeList);
}
- public List<List<NavigateNode>> getRgvTrackMap(int lev) {
- BasMapService basMapService = SpringUtils.getBean(BasMapService.class);
- BasMap basMap = basMapService.getOne(new QueryWrapper<BasMap>().eq("lev", lev));
- if (basMap == null) {
- throw new CoolException("鍦板浘涓嶅瓨鍦�");
- }
-
- List<List<JSONObject>> dataList = JSON.parseObject(basMap.getData(), List.class);
-
- List<List<NavigateNode>> navigateNodeList = new ArrayList<>();
- for (int i = 0; i < dataList.size(); i++) {
- List<JSONObject> row = dataList.get(i);
- List<NavigateNode> navigateNodeRow = new ArrayList<>();
- for (int j = 0; j < row.size(); j++) {
- JSONObject map = row.get(j);
- NavigateNode navigateNode = new NavigateNode(i, j);
-
- String nodeType = map.getString("type");
- if(nodeType == null) {
- navigateNode.setValue(MapNodeType.DISABLE.id);
- }else if(nodeType.equals("rgv")){
- navigateNode.setValue(MapNodeType.NORMAL_PATH.id);
- JSONObject valueObj = JSON.parseObject(map.getString("value"));
-
- //RGV鏆備笉鎺у埗琛岃蛋鏂瑰悜锛岄粯璁や笂涓嬪乏鍙抽兘鍙蛋
- List<String> directionList = new ArrayList<>();
- directionList.add("top");
- directionList.add("bottom");
- directionList.add("left");
- directionList.add("right");
- navigateNode.setDirectionList(directionList);
- }else {
- navigateNode.setValue(MapNodeType.DISABLE.id);
- }
-
- navigateNode.setNodeType(nodeType);
- navigateNode.setNodeValue(map.getString("value"));
- navigateNodeRow.add(navigateNode);
+ private List<List<NavigateNode>> cloneNavigateMap(List<List<NavigateNode>> sourceMap) {
+ List<List<NavigateNode>> cloneMap = new ArrayList<>();
+ for (List<NavigateNode> row : sourceMap) {
+ List<NavigateNode> cloneRow = new ArrayList<>();
+ for (NavigateNode node : row) {
+ cloneRow.add(node == null ? null : node.clone());
}
- navigateNodeList.add(navigateNodeRow);
+ cloneMap.add(cloneRow);
+ }
+ return cloneMap;
+ }
+
+ private boolean isValidNavigateMap(List<List<NavigateNode>> navigateMap) {
+ if (navigateMap == null || navigateMap.isEmpty() || navigateMap.get(0) == null || navigateMap.get(0).isEmpty()) {
+ return false;
}
- return navigateNodeList;
+ int activeNodeCount = 0;
+ for (List<NavigateNode> row : navigateMap) {
+ if (row == null || row.isEmpty()) {
+ return false;
+ }
+ for (NavigateNode node : row) {
+ if (node == null) {
+ return false;
+ }
+ if (node.getValue() == MapNodeType.DISABLE.id) {
+ continue;
+ }
+ activeNodeCount++;
+ if (node.getNodeType() == null) {
+ return false;
+ }
+ if (node.getDirectionList() == null || node.getDirectionList().isEmpty()) {
+ return false;
+ }
+ }
+ }
+ return activeNodeCount > 0;
+ }
+
+ /**
+ * 鍙繚鐣欏弬涓庤矾寰勮绠楃殑浜岀淮鍖哄煙锛屽幓鎺変笂涓嬪乏鍙虫暣鐗囨棤鏁堢┖鐧藉尯銆�
+ */
+ private List<List<NavigateNode>> cropNavigateMap(List<List<NavigateNode>> navigateMap) {
+ if (navigateMap == null || navigateMap.isEmpty() || navigateMap.get(0) == null || navigateMap.get(0).isEmpty()) {
+ return navigateMap;
+ }
+
+ int minX = Integer.MAX_VALUE;
+ int maxX = Integer.MIN_VALUE;
+ int minY = Integer.MAX_VALUE;
+ int maxY = Integer.MIN_VALUE;
+ boolean hasActiveNode = false;
+ for (int x = 0; x < navigateMap.size(); x++) {
+ List<NavigateNode> row = navigateMap.get(x);
+ if (row == null) {
+ continue;
+ }
+ for (int y = 0; y < row.size(); y++) {
+ NavigateNode node = row.get(y);
+ if (node == null || node.getValue() == MapNodeType.DISABLE.id) {
+ continue;
+ }
+ hasActiveNode = true;
+ minX = Math.min(minX, x);
+ maxX = Math.max(maxX, x);
+ minY = Math.min(minY, y);
+ maxY = Math.max(maxY, y);
+ }
+ }
+
+ if (!hasActiveNode) {
+ return navigateMap;
+ }
+
+ List<List<NavigateNode>> croppedMap = new ArrayList<>();
+ for (int x = minX; x <= maxX; x++) {
+ List<NavigateNode> sourceRow = navigateMap.get(x);
+ List<NavigateNode> croppedRow = new ArrayList<>();
+ for (int y = minY; y <= maxY; y++) {
+ NavigateNode sourceNode = sourceRow.get(y);
+ NavigateNode targetNode = new NavigateNode(x - minX, y - minY);
+ targetNode.setValue(sourceNode.getValue());
+ targetNode.setNodeType(sourceNode.getNodeType());
+ targetNode.setNodeValue(sourceNode.getNodeValue());
+ targetNode.setDirectionList(sourceNode.getDirectionList() == null
+ ? null
+ : new ArrayList<>(sourceNode.getDirectionList()));
+ croppedRow.add(targetNode);
+ }
+ croppedMap.add(croppedRow);
+ }
+ return croppedMap;
}
public NavigateNode astarSearchJava(List<List<NavigateNode>> map, NavigateNode start, NavigateNode end) {
@@ -609,4 +767,13 @@
//------------------A*鍚彂鍑芥暟-end------------------//
+ private static class CachedNavigateMap {
+ private final long cacheAtMs;
+ private final List<List<NavigateNode>> navigateMap;
+
+ private CachedNavigateMap(long cacheAtMs, List<List<NavigateNode>> navigateMap) {
+ this.cacheAtMs = cacheAtMs;
+ this.navigateMap = navigateMap;
+ }
+ }
}
diff --git a/src/main/java/com/zy/core/config/NavigateMapCacheInitializer.java b/src/main/java/com/zy/core/config/NavigateMapCacheInitializer.java
new file mode 100644
index 0000000..e8781b2
--- /dev/null
+++ b/src/main/java/com/zy/core/config/NavigateMapCacheInitializer.java
@@ -0,0 +1,31 @@
+package com.zy.core.config;
+
+import com.zy.common.utils.NavigateSolution;
+import org.apache.logging.log4j.LogManager;
+import org.apache.logging.log4j.Logger;
+import org.springframework.context.ApplicationContext;
+import org.springframework.context.ApplicationListener;
+import org.springframework.context.event.ContextRefreshedEvent;
+import org.springframework.stereotype.Component;
+
+@Component
+public class NavigateMapCacheInitializer implements ApplicationListener<ContextRefreshedEvent> {
+
+ private static final Logger logger = LogManager.getLogger(NavigateMapCacheInitializer.class);
+
+ @Override
+ public void onApplicationEvent(ContextRefreshedEvent event) {
+ ApplicationContext parent = event.getApplicationContext().getParent();
+ if (parent != null) {
+ return;
+ }
+
+ long start = System.currentTimeMillis();
+ try {
+ NavigateSolution.refreshAllMapCaches();
+ logger.info("鍦板浘缂撳瓨鍒锋柊瀹屾垚锛宑ost={}ms", System.currentTimeMillis() - start);
+ } catch (Exception e) {
+ logger.error("鍦板浘缂撳瓨鍒锋柊澶辫触", e);
+ }
+ }
+}
diff --git a/src/main/java/com/zy/core/enums/RedisKeyType.java b/src/main/java/com/zy/core/enums/RedisKeyType.java
index c4c9cfc..19199f7 100644
--- a/src/main/java/com/zy/core/enums/RedisKeyType.java
+++ b/src/main/java/com/zy/core/enums/RedisKeyType.java
@@ -16,6 +16,7 @@
LOG_LIMIT("log_limit_"),
SYSTEM_CONFIG_MAP("system_config_map"),
FAKE_TASK_NO_AREA("fake_task_no_area"),
+ NAVIGATE_MAP_TEMPLATE_("navigate_map_template_"),
IN_STATION_ROUTE_CACHE("in_station_route_cache_"),
OUT_STATION_ROUTE_CACHE("out_station_route_cache_"),
STATION_REACHABLE_CACHE("station_reachable_cache_"),
diff --git a/src/main/java/com/zy/core/thread/impl/ZyStationV5Thread.java b/src/main/java/com/zy/core/thread/impl/ZyStationV5Thread.java
index 0f8f76c..09e1b79 100644
--- a/src/main/java/com/zy/core/thread/impl/ZyStationV5Thread.java
+++ b/src/main/java/com/zy/core/thread/impl/ZyStationV5Thread.java
@@ -197,10 +197,12 @@
return getCommand(StationCommandType.MOVE, taskNo, stationId, targetStationId, palletSize, pathLenFactor);
}
+ long startNs = System.nanoTime();
StationTaskLoopService taskLoopService = loadStationTaskLoopService();
StationTaskLoopService.LoopEvaluation loopEvaluation = taskLoopService == null
? new StationTaskLoopService.LoopEvaluation(taskNo, stationId, StationTaskLoopService.LoopIdentitySnapshot.empty(), 0, 0, false)
: taskLoopService.evaluateLoop(taskNo, stationId, true);
+ long loopEvalNs = System.nanoTime();
log.info("杈撻�佺嚎鍫靛閲嶈鍒掔幆绾胯瘑鍒紝taskNo={}, stationId={}, scopeType={}, localStationCount={}, sourceLoopStationCount={}",
taskNo,
stationId,
@@ -208,6 +210,7 @@
loopEvaluation.getLoopIdentity().getLocalStationCount(),
loopEvaluation.getLoopIdentity().getSourceLoopStationCount());
List<List<NavigateNode>> candidatePathList = calcCandidatePathNavigateNodes(taskNo, stationId, targetStationId, pathLenFactor);
+ long candidatePathNs = System.nanoTime();
List<StationCommand> candidateCommandList = new ArrayList<>();
for (List<NavigateNode> candidatePath : candidatePathList) {
StationCommand rerouteCommand = buildMoveCommand(taskNo, stationId, targetStationId, palletSize, candidatePath);
@@ -216,6 +219,7 @@
}
candidateCommandList.add(rerouteCommand);
}
+ long buildCommandNs = System.nanoTime();
StationV5RunBlockReroutePlanner.PlanResult planResult = runBlockReroutePlanner.plan(
taskNo,
@@ -223,6 +227,17 @@
loopEvaluation,
candidateCommandList
);
+ long planNs = System.nanoTime();
+ logRunBlockRerouteCost(taskNo,
+ stationId,
+ targetStationId,
+ candidatePathList == null ? 0 : candidatePathList.size(),
+ candidateCommandList.size(),
+ startNs,
+ loopEvalNs,
+ candidatePathNs,
+ buildCommandNs,
+ planNs);
if (candidateCommandList.isEmpty()) {
log.warn("杈撻�佺嚎鍫靛閲嶈鍒掑け璐ワ紝鍊欓�夎矾寰勪负绌猴紝taskNo={}, planCount={}, stationId={}, targetStationId={}",
taskNo, planResult.getPlanCount(), stationId, targetStationId);
@@ -423,4 +438,35 @@
return null;
}
}
+
+ private void logRunBlockRerouteCost(Integer taskNo,
+ Integer stationId,
+ Integer targetStationId,
+ int candidatePathCount,
+ int candidateCommandCount,
+ long startNs,
+ long loopEvalNs,
+ long candidatePathNs,
+ long buildCommandNs,
+ long planNs) {
+ long totalMs = nanosToMillis(planNs - startNs);
+ if (totalMs < 1000L) {
+ return;
+ }
+ log.warn("杈撻�佺嚎鍫靛閲嶈鍒掕�楁椂杈冮暱, taskNo={}, stationId={}, targetStationId={}, total={}ms, loopEval={}ms, candidatePath={}ms, buildCommand={}ms, planner={}ms, candidatePathCount={}, candidateCommandCount={}",
+ taskNo,
+ stationId,
+ targetStationId,
+ totalMs,
+ nanosToMillis(loopEvalNs - startNs),
+ nanosToMillis(candidatePathNs - loopEvalNs),
+ nanosToMillis(buildCommandNs - candidatePathNs),
+ nanosToMillis(planNs - buildCommandNs),
+ candidatePathCount,
+ candidateCommandCount);
+ }
+
+ private long nanosToMillis(long nanos) {
+ return nanos <= 0L ? 0L : nanos / 1_000_000L;
+ }
}
diff --git a/src/test/java/com/zy/common/utils/NavigatePerformanceBenchmarkTest.java b/src/test/java/com/zy/common/utils/NavigatePerformanceBenchmarkTest.java
new file mode 100644
index 0000000..9735b59
--- /dev/null
+++ b/src/test/java/com/zy/common/utils/NavigatePerformanceBenchmarkTest.java
@@ -0,0 +1,354 @@
+package com.zy.common.utils;
+
+import com.alibaba.fastjson.JSON;
+import com.alibaba.fastjson.JSONObject;
+import com.zy.asrs.service.impl.BasMapEditorServiceImpl;
+import com.zy.asrs.utils.MapExcelUtils;
+import com.zy.common.model.NavigateNode;
+import com.zy.core.enums.MapNodeType;
+import org.junit.jupiter.api.Assumptions;
+import org.junit.jupiter.api.Test;
+import org.springframework.test.util.ReflectionTestUtils;
+
+import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.LinkedHashMap;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Locale;
+import java.util.Map;
+import java.util.Set;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+import static org.junit.jupiter.api.Assertions.assertFalse;
+
+class NavigatePerformanceBenchmarkTest {
+
+ private static final int CALC_MAX_DEPTH = 120;
+ private static final int CALC_MAX_PATHS = 500;
+ private static final int CALC_MAX_COST = 300;
+
+ @Test
+ void benchmarkExcelMaps() throws Exception {
+ // 鎵嬪伐鍘嬫祴鍏ュ彛锛岄伩鍏嶉粯璁ゆ祴璇曞浠惰鎬ц兘娴嬭瘯鎷栨參銆�
+ Assumptions.assumeTrue(Boolean.getBoolean("manualBench"));
+
+ Path mapDir = Path.of("src/main/resources/map");
+ List<Path> mapFileList;
+ try (Stream<Path> stream = Files.list(mapDir)) {
+ mapFileList = stream
+ .filter(path -> path.getFileName().toString().endsWith(".xlsx"))
+ .sorted(Comparator.comparing(path -> path.getFileName().toString()))
+ .collect(Collectors.toList());
+ }
+
+ List<String> reportLineList = new ArrayList<>();
+ for (Path mapFile : mapFileList) {
+ reportLineList.addAll(benchmarkMapFile(mapFile));
+ }
+
+ reportLineList.forEach(System.out::println);
+ assertFalse(reportLineList.isEmpty(), "鏈敓鎴愪换浣曞湴鍥炬�ц兘鎶ュ憡");
+ }
+
+ private List<String> benchmarkMapFile(Path mapFile) throws IOException {
+ MapExcelUtils mapExcelUtils = new MapExcelUtils();
+ BasMapEditorServiceImpl editorService = new BasMapEditorServiceImpl();
+
+ HashMap<Integer, List<List<HashMap<String, Object>>>> rawDataMap = mapExcelUtils.readExcel(mapFile.toString());
+ List<Integer> levList = rawDataMap.keySet().stream().sorted().collect(Collectors.toList());
+
+ List<String> reportLineList = new ArrayList<>();
+ for (Integer lev : levList) {
+ @SuppressWarnings("unchecked")
+ List<List<HashMap<String, Object>>> storedData =
+ (List<List<HashMap<String, Object>>>) ReflectionTestUtils.invokeMethod(
+ editorService,
+ "convertRawExcelData",
+ rawDataMap.get(lev)
+ );
+ List<List<NavigateNode>> stationMap = buildStationMap(storedData);
+ Map<Integer, NavigateNode> stationNodeMap = collectStationNodeMap(stationMap);
+ if (stationNodeMap.size() < 2) {
+ continue;
+ }
+
+ BenchmarkSummary summary = benchmarkStationPairs(stationMap, stationNodeMap);
+ reportLineList.add(summary.format(mapFile.getFileName().toString(), lev));
+ }
+ return reportLineList;
+ }
+
+ private BenchmarkSummary benchmarkStationPairs(List<List<NavigateNode>> stationMap,
+ Map<Integer, NavigateNode> stationNodeMap) {
+ NavigateSolution navigateSolution = new NavigateSolution();
+ List<Integer> stationIdList = new ArrayList<>(stationNodeMap.keySet());
+ stationIdList.sort(Integer::compareTo);
+
+ BenchmarkSummary summary = new BenchmarkSummary(stationIdList.size());
+ warmup(navigateSolution, stationMap, stationNodeMap, stationIdList);
+
+ for (int i = 0; i < stationIdList.size(); i++) {
+ for (int j = i + 1; j < stationIdList.size(); j++) {
+ Integer startStationId = stationIdList.get(i);
+ Integer endStationId = stationIdList.get(j);
+
+ NavigateNode startNode = stationNodeMap.get(startStationId);
+ NavigateNode endNode = stationNodeMap.get(endStationId);
+ if (startNode == null || endNode == null) {
+ continue;
+ }
+
+ resetMapSearchState(stationMap);
+ long astarStartNs = System.nanoTime();
+ NavigateNode astarResult = navigateSolution.astarSearchJava(stationMap, startNode, endNode);
+ long astarElapsedNs = System.nanoTime() - astarStartNs;
+ int astarPathLen = calcBacktrackPathLength(astarResult, stationMap);
+
+ long allPathsStartNs = System.nanoTime();
+ List<List<NavigateNode>> candidatePathList = navigateSolution.allSimplePaths(
+ stationMap,
+ startNode,
+ endNode,
+ CALC_MAX_DEPTH,
+ CALC_MAX_PATHS,
+ CALC_MAX_COST
+ );
+ long allPathsElapsedNs = System.nanoTime() - allPathsStartNs;
+
+ summary.record(
+ startStationId,
+ endStationId,
+ astarElapsedNs,
+ allPathsElapsedNs,
+ astarPathLen,
+ candidatePathList == null ? 0 : candidatePathList.size()
+ );
+ }
+ }
+ return summary;
+ }
+
+ private void warmup(NavigateSolution navigateSolution,
+ List<List<NavigateNode>> stationMap,
+ Map<Integer, NavigateNode> stationNodeMap,
+ List<Integer> stationIdList) {
+ int warmupPairCount = Math.min(5, Math.max(0, stationIdList.size() - 1));
+ for (int i = 0; i < warmupPairCount; i++) {
+ Integer startStationId = stationIdList.get(i);
+ Integer endStationId = stationIdList.get(stationIdList.size() - 1 - i);
+ NavigateNode startNode = stationNodeMap.get(startStationId);
+ NavigateNode endNode = stationNodeMap.get(endStationId);
+ if (startNode == null || endNode == null) {
+ continue;
+ }
+ resetMapSearchState(stationMap);
+ navigateSolution.astarSearchJava(stationMap, startNode, endNode);
+ navigateSolution.allSimplePaths(
+ stationMap,
+ startNode,
+ endNode,
+ CALC_MAX_DEPTH,
+ CALC_MAX_PATHS,
+ CALC_MAX_COST
+ );
+ }
+ }
+
+ private Map<Integer, NavigateNode> collectStationNodeMap(List<List<NavigateNode>> stationMap) {
+ NavigateSolution navigateSolution = new NavigateSolution();
+ Set<Integer> stationIdSet = new LinkedHashSet<>();
+ for (List<NavigateNode> row : stationMap) {
+ for (NavigateNode node : row) {
+ Integer stationId = extractStationId(node);
+ if (stationId != null) {
+ stationIdSet.add(stationId);
+ }
+ }
+ }
+
+ Map<Integer, NavigateNode> stationNodeMap = new LinkedHashMap<>();
+ for (Integer stationId : stationIdSet) {
+ NavigateNode node = navigateSolution.findStationNavigateNode(stationMap, stationId);
+ if (node != null) {
+ stationNodeMap.put(stationId, node);
+ }
+ }
+ return stationNodeMap;
+ }
+
+ private Integer extractStationId(NavigateNode node) {
+ if (node == null || node.getNodeValue() == null || node.getNodeValue().trim().isEmpty()) {
+ return null;
+ }
+ try {
+ JSONObject valueObject = JSON.parseObject(node.getNodeValue());
+ return valueObject == null ? null : valueObject.getInteger("stationId");
+ } catch (Exception ignore) {
+ return null;
+ }
+ }
+
+ private void resetMapSearchState(List<List<NavigateNode>> stationMap) {
+ for (List<NavigateNode> row : stationMap) {
+ for (NavigateNode node : row) {
+ node.setFather(null);
+ node.setF(0);
+ node.setG(0);
+ node.setH(0);
+ node.setIsInflectionPoint(false);
+ node.setDirection(null);
+ }
+ }
+ }
+
+ private int calcBacktrackPathLength(NavigateNode endNode, List<List<NavigateNode>> stationMap) {
+ if (endNode == null) {
+ return 0;
+ }
+ int maxDepth = stationMap.size() * stationMap.get(0).size() + 5;
+ int length = 0;
+ Set<String> visited = new LinkedHashSet<>();
+ NavigateNode current = endNode;
+ while (current != null && visited.add(current.getX() + "_" + current.getY()) && length < maxDepth) {
+ length++;
+ current = current.getFather();
+ }
+ return length;
+ }
+
+ private List<List<NavigateNode>> buildStationMap(List<List<HashMap<String, Object>>> storedData) {
+ List<List<NavigateNode>> stationMap = new ArrayList<>();
+ for (int rowIndex = 0; rowIndex < storedData.size(); rowIndex++) {
+ List<HashMap<String, Object>> row = storedData.get(rowIndex);
+ List<NavigateNode> navigateNodeRow = new ArrayList<>();
+ for (int colIndex = 0; colIndex < row.size(); colIndex++) {
+ HashMap<String, Object> cell = row.get(colIndex);
+ NavigateNode node = new NavigateNode(rowIndex, colIndex);
+ String nodeType = cell == null ? null : stringValue(cell.get("type"));
+ String mergeType = cell == null ? null : stringValue(cell.get("mergeType"));
+ String nodeValue = cell == null ? null : stringValue(cell.get("value"));
+
+ if ("devp".equals(nodeType) || ("merge".equals(nodeType) && "devp".equals(mergeType))) {
+ node.setValue(MapNodeType.NORMAL_PATH.id);
+ JSONObject valueObject = JSON.parseObject(nodeValue);
+ node.setDirectionList(valueObject == null
+ ? new ArrayList<>()
+ : valueObject.getJSONArray("direction").toJavaList(String.class));
+ } else {
+ node.setValue(MapNodeType.DISABLE.id);
+ }
+
+ node.setNodeType(nodeType);
+ node.setNodeValue(nodeValue);
+ navigateNodeRow.add(node);
+ }
+ stationMap.add(navigateNodeRow);
+ }
+ return stationMap;
+ }
+
+ private String stringValue(Object value) {
+ return value == null ? null : String.valueOf(value);
+ }
+
+ private static class BenchmarkSummary {
+ private final int stationCount;
+ private int pairCount;
+ private long astarTotalNs;
+ private long allPathsTotalNs;
+ private final List<Long> astarElapsedNsList = new ArrayList<>();
+ private final List<Long> allPathsElapsedNsList = new ArrayList<>();
+ private int maxCandidateCount;
+ private int maxAstarPathLen;
+ private int worstAstarStartStationId;
+ private int worstAstarEndStationId;
+ private long worstAstarElapsedNs;
+ private int worstAllPathsStartStationId;
+ private int worstAllPathsEndStationId;
+ private long worstAllPathsElapsedNs;
+ private int worstAllPathsCandidateCount;
+
+ private BenchmarkSummary(int stationCount) {
+ this.stationCount = stationCount;
+ }
+
+ private void record(int startStationId,
+ int endStationId,
+ long astarElapsedNs,
+ long allPathsElapsedNs,
+ int astarPathLen,
+ int candidateCount) {
+ pairCount++;
+ astarTotalNs += astarElapsedNs;
+ allPathsTotalNs += allPathsElapsedNs;
+ astarElapsedNsList.add(astarElapsedNs);
+ allPathsElapsedNsList.add(allPathsElapsedNs);
+ maxCandidateCount = Math.max(maxCandidateCount, candidateCount);
+ maxAstarPathLen = Math.max(maxAstarPathLen, astarPathLen);
+
+ if (astarElapsedNs > worstAstarElapsedNs) {
+ worstAstarElapsedNs = astarElapsedNs;
+ worstAstarStartStationId = startStationId;
+ worstAstarEndStationId = endStationId;
+ }
+ if (allPathsElapsedNs > worstAllPathsElapsedNs) {
+ worstAllPathsElapsedNs = allPathsElapsedNs;
+ worstAllPathsStartStationId = startStationId;
+ worstAllPathsEndStationId = endStationId;
+ worstAllPathsCandidateCount = candidateCount;
+ }
+ }
+
+ private String format(String mapFileName, Integer lev) {
+ return String.format(
+ Locale.ROOT,
+ "map=%s lev=%d stations=%d pairs=%d | A*=avg %.3fms p95 %.3fms max %.3fms pair=%d->%d | allSimplePaths=avg %.3fms p95 %.3fms max %.3fms pair=%d->%d candidates=%d | maxPathLen=%d maxCandidates=%d",
+ mapFileName,
+ lev,
+ stationCount,
+ pairCount,
+ toMillis(avg(astarTotalNs, pairCount)),
+ toMillis(percentile(astarElapsedNsList, 0.95d)),
+ toMillis(worstAstarElapsedNs),
+ worstAstarStartStationId,
+ worstAstarEndStationId,
+ toMillis(avg(allPathsTotalNs, pairCount)),
+ toMillis(percentile(allPathsElapsedNsList, 0.95d)),
+ toMillis(worstAllPathsElapsedNs),
+ worstAllPathsStartStationId,
+ worstAllPathsEndStationId,
+ worstAllPathsCandidateCount,
+ maxAstarPathLen,
+ maxCandidateCount
+ );
+ }
+
+ private double avg(long totalNs, int count) {
+ if (count <= 0) {
+ return 0.0d;
+ }
+ return (double) totalNs / count;
+ }
+
+ private double percentile(List<Long> valueList, double percentile) {
+ if (valueList == null || valueList.isEmpty()) {
+ return 0.0d;
+ }
+ List<Long> sortedList = new ArrayList<>(valueList);
+ sortedList.sort(Long::compareTo);
+ int index = (int) Math.ceil(percentile * sortedList.size()) - 1;
+ index = Math.max(0, Math.min(index, sortedList.size() - 1));
+ return sortedList.get(index);
+ }
+
+ private double toMillis(double nanos) {
+ return nanos / 1_000_000.0d;
+ }
+ }
+}
--
Gitblit v1.9.1