From 1c6d2b037844239b907adfe3882d2cc41a99a3d3 Mon Sep 17 00:00:00 2001
From: Junjie <fallin.jie@qq.com>
Date: 星期三, 06 五月 2026 17:18:16 +0800
Subject: [PATCH] #dfs
---
src/main/java/com/zy/common/utils/NavigateUtils.java | 305 ++++++++++++++++++++++++++++++++++++++++++++------
1 files changed, 267 insertions(+), 38 deletions(-)
diff --git a/src/main/java/com/zy/common/utils/NavigateUtils.java b/src/main/java/com/zy/common/utils/NavigateUtils.java
index 5614e6c..733a2ab 100644
--- a/src/main/java/com/zy/common/utils/NavigateUtils.java
+++ b/src/main/java/com/zy/common/utils/NavigateUtils.java
@@ -27,6 +27,8 @@
import com.zy.asrs.service.StationCycleCapacityService;
import com.zy.asrs.service.StationPathPolicyService;
import com.zy.core.News;
+import lombok.extern.slf4j.Slf4j;
+import org.springframework.scheduling.annotation.Scheduled;
import com.zy.core.model.StationObjModel;
import com.zy.core.model.command.StationCommand;
import com.zy.core.enums.StationCommandType;
@@ -52,6 +54,7 @@
import java.util.LinkedHashMap;
@Component
+@Slf4j
public class NavigateUtils {
private static final long STATION_PATH_SLOW_LOG_THRESHOLD_MS = 500L;
@@ -77,8 +80,23 @@
@Autowired
private StationTaskTraceRegistry stationTaskTraceRegistry;
- private final Object runtimeSnapshotLock = new Object();
private volatile CachedStationPathRuntimeSnapshot cachedRuntimeSnapshot;
+
+ private volatile CachedLoopMergeGuardContext cachedLoopMergeGuardContext;
+
+ @Scheduled(fixedDelay = 1500, initialDelay = 3000)
+ public void refreshStationPathCaches() {
+ try {
+ BaseRuntimeSnapshot snapshot = buildBaseRuntimeSnapshot(null);
+ cachedRuntimeSnapshot = new CachedStationPathRuntimeSnapshot(System.currentTimeMillis(), snapshot);
+ } catch (Exception ignore) {
+ }
+ try {
+ LoopMergeGuardContext context = buildLoopMergeGuardContext();
+ cachedLoopMergeGuardContext = new CachedLoopMergeGuardContext(System.currentTimeMillis(), context);
+ } catch (Exception ignore) {
+ }
+ }
public List<NavigateNode> calcOptimalPathByStationId(Integer startStationId,
Integer endStationId,
@@ -95,29 +113,74 @@
Integer endStationId,
Integer currentTaskNo,
Double pathLenFactor) {
- StationPathResolvedPolicy resolvedPolicy = resolveStationPathPolicy(startStationId, endStationId);
- StationPathRuntimeSnapshot runtimeSnapshot = loadStationPathRuntimeSnapshot(currentTaskNo);
- StationPathSearchContext context = buildStationPathSearchContext(
- startStationId,
- endStationId,
- resolvedPolicy,
- StationPathCalcMode.REROUTE,
- runtimeSnapshot
- );
- if (context.allList.isEmpty()) {
- return new ArrayList<>();
- }
+ long totalStartNs = System.nanoTime();
+ log.info("绔欑偣璺緞鍊欓�夎绠楀叆鍙ｏ紝startStationId={}锛宔ndStationId={}锛宼askNo={}锛宲athLenFactor={}",
+ startStationId, endStationId, currentTaskNo, pathLenFactor);
+ try {
+ StationPathResolvedPolicy resolvedPolicy = resolveStationPathPolicy(startStationId, endStationId);
+ log.info("绔欑偣璺緞鍊欓�夌瓥鐣ヨВ鏋愬畬鎴愶紝startStationId={}锛宔ndStationId={}锛宼askNo={}锛宮atchedRule={}锛宺uleCode={}锛宲rofileCode={}锛宑ostMs={}",
+ startStationId,
+ endStationId,
+ currentTaskNo,
+ resolvedPolicy != null && resolvedPolicy.matchedRule(),
+ resolvedPolicy == null || resolvedPolicy.getRuleEntity() == null ? null : resolvedPolicy.getRuleEntity().getRuleCode(),
+ resolvedPolicy == null ? null : resolvedPolicy.getDefaultProfileCode(),
+ elapsedMillis(totalStartNs));
+ StationPathRuntimeSnapshot runtimeSnapshot = loadStationPathRuntimeSnapshot(currentTaskNo);
+ List<NavigateNode> shortFallbackPath = buildRerouteShortFallbackPath(
+ startStationId,
+ endStationId,
+ currentTaskNo,
+ resolvedPolicy,
+ runtimeSnapshot
+ );
+ StationPathSearchContext context = buildStationPathSearchContext(
+ startStationId,
+ endStationId,
+ resolvedPolicy,
+ StationPathCalcMode.REROUTE,
+ runtimeSnapshot
+ );
+ if (context.allList.isEmpty()) {
+ List<List<NavigateNode>> fallbackCandidateList = normalizeCandidatePaths(Collections.singletonList(shortFallbackPath));
+ log.warn("绔欑偣璺緞鍊欓�夎绠楃粨鏉燂紝鍘熷洜=empty_search_context锛宻tartStationId={}锛宔ndStationId={}锛宼askNo={}锛宖allbackCandidateCount={}锛宖allbackPath={}锛宼otalCostMs={}",
+ startStationId,
+ endStationId,
+ currentTaskNo,
+ fallbackCandidateList.size(),
+ JSON.toJSONString(extractStationIdList(shortFallbackPath)),
+ elapsedMillis(totalStartNs));
+ return fallbackCandidateList;
+ }
- List<List<NavigateNode>> orderedPathList = orderStationPathCandidates(
- context.allList,
- context.resolvedPolicy,
- currentTaskNo,
- pathLenFactor,
- startStationId,
- endStationId,
- runtimeSnapshot
- );
- return normalizeCandidatePaths(orderedPathList);
+ long orderStartNs = System.nanoTime();
+ List<List<NavigateNode>> orderedPathList = orderStationPathCandidates(
+ context.allList,
+ context.resolvedPolicy,
+ currentTaskNo,
+ pathLenFactor,
+ startStationId,
+ endStationId,
+ runtimeSnapshot
+ );
+ List<List<NavigateNode>> candidatePathList = appendShortFallbackCandidate(orderedPathList, shortFallbackPath);
+ List<List<NavigateNode>> normalizedPathList = normalizeCandidatePaths(candidatePathList);
+ log.info("绔欑偣璺緞鍊欓�夎绠楃粨鏉燂紝startStationId={}锛宔ndStationId={}锛宼askNo={}锛宺awCandidateCount={}锛宱rderedPathCount={}锛宖allbackPathLen={}锛宯ormalizedPathCount={}锛宱rderCostMs={}锛宼otalCostMs={}",
+ startStationId,
+ endStationId,
+ currentTaskNo,
+ context.allList.size(),
+ orderedPathList == null ? null : orderedPathList.size(),
+ shortFallbackPath == null ? 0 : shortFallbackPath.size(),
+ normalizedPathList.size(),
+ elapsedMillis(orderStartNs),
+ elapsedMillis(totalStartNs));
+ return normalizedPathList;
+ } catch (Exception e) {
+ log.error("绔欑偣璺緞鍊欓�夎绠楀紓甯革紝startStationId={}锛宔ndStationId={}锛宼askNo={}锛宲athLenFactor={}锛宑ostMs={}",
+ startStationId, endStationId, currentTaskNo, pathLenFactor, elapsedMillis(totalStartNs), e);
+ throw e;
+ }
}
public Map<Integer, Set<Integer>> loadUndirectedStationGraphSnapshot() {
@@ -397,6 +460,54 @@
return new DirectPathSearchResult(degradedPath, includeWaypoint, false);
}
return DirectPathSearchResult.empty(includeWaypoint, includeSoftPreference);
+ }
+
+ private List<NavigateNode> buildRerouteShortFallbackPath(Integer startStationId,
+ Integer endStationId,
+ Integer currentTaskNo,
+ StationPathResolvedPolicy resolvedPolicy,
+ StationPathRuntimeSnapshot runtimeSnapshot) {
+ long startNs = System.nanoTime();
+ try {
+ List<NavigateNode> path = findStationDirectPath(
+ startStationId,
+ endStationId,
+ currentTaskNo,
+ 0.0d,
+ StationPathCalcMode.OPTIMAL,
+ resolvedPolicy,
+ runtimeSnapshot
+ );
+ List<NavigateNode> normalizedPath = normalizeStationPath(path);
+ log.info("绔欑偣璺緞鍫靛閲嶈鍒掔煭璺緞淇濆簳璁＄畻瀹屾垚锛宻tartStationId={}锛宔ndStationId={}锛宼askNo={}锛宲athLen={}锛宲ath={}锛宑ostMs={}",
+ startStationId,
+ endStationId,
+ currentTaskNo,
+ normalizedPath.size(),
+ JSON.toJSONString(extractStationIdList(normalizedPath)),
+ elapsedMillis(startNs));
+ return normalizedPath;
+ } catch (Exception e) {
+ log.warn("绔欑偣璺緞鍫靛閲嶈鍒掔煭璺緞淇濆簳璁＄畻澶辫触锛宻tartStationId={}锛宔ndStationId={}锛宼askNo={}锛宑ostMs={}锛宔rror={}",
+ startStationId,
+ endStationId,
+ currentTaskNo,
+ elapsedMillis(startNs),
+ e.toString());
+ return new ArrayList<>();
+ }
+ }
+
+ private List<List<NavigateNode>> appendShortFallbackCandidate(List<List<NavigateNode>> orderedPathList,
+ List<NavigateNode> shortFallbackPath) {
+ List<List<NavigateNode>> candidatePathList = new ArrayList<>();
+ if (orderedPathList != null && !orderedPathList.isEmpty()) {
+ candidatePathList.addAll(orderedPathList);
+ }
+ if (shortFallbackPath != null && !shortFallbackPath.isEmpty()) {
+ candidatePathList.add(shortFallbackPath);
+ }
+ return candidatePathList;
}
private List<NavigateNode> searchDirectPath(DirectStationPathContext context,
@@ -1688,22 +1799,21 @@
}
return cachedSnapshot.baseRuntimeSnapshot.toCacheHitSnapshot();
}
- synchronized (runtimeSnapshotLock) {
- cachedSnapshot = cachedRuntimeSnapshot;
- if (cachedSnapshot != null && now - cachedSnapshot.cacheAtMs <= STATION_PATH_RUNTIME_SNAPSHOT_TTL_MS) {
- if (stepCostMap != null) {
- stepCostMap.put("baseSnapshotCacheHit", 0L);
- }
- return cachedSnapshot.baseRuntimeSnapshot.toCacheHitSnapshot();
- }
- long stepStartNs = System.nanoTime();
- BaseRuntimeSnapshot baseRuntimeSnapshot = buildBaseRuntimeSnapshot(stepCostMap);
+ // 缂撳瓨杩囨湡锛氱敤杩囨湡缂撳瓨鍏滃簳锛園Scheduled 瀹氭椂浠诲姟浼氬緢蹇埛鏂帮級锛岄伩鍏嶅绾跨▼闃诲
+ if (cachedSnapshot != null) {
if (stepCostMap != null) {
- stepCostMap.put("buildBaseSnapshot", elapsedMillis(stepStartNs));
+ stepCostMap.put("baseSnapshotStale", 0L);
}
- cachedRuntimeSnapshot = new CachedStationPathRuntimeSnapshot(System.currentTimeMillis(), baseRuntimeSnapshot);
- return baseRuntimeSnapshot;
+ return cachedSnapshot.baseRuntimeSnapshot.toCacheHitSnapshot();
}
+ // 鏋佺鎯呭喌锛氫粠鏈湁杩囩紦瀛橈紙鍚姩棣栨璋冪敤锛夛紝鍚屾鏋勫缓
+ long stepStartNs = System.nanoTime();
+ BaseRuntimeSnapshot baseRuntimeSnapshot = buildBaseRuntimeSnapshot(stepCostMap);
+ if (stepCostMap != null) {
+ stepCostMap.put("buildBaseSnapshot", elapsedMillis(stepStartNs));
+ }
+ cachedRuntimeSnapshot = new CachedStationPathRuntimeSnapshot(System.currentTimeMillis(), baseRuntimeSnapshot);
+ return baseRuntimeSnapshot;
}
private BaseRuntimeSnapshot buildBaseRuntimeSnapshot(Map<String, Long> stepCostMap) {
@@ -1766,6 +1876,22 @@
}
private LoopMergeGuardContext loadLoopMergeGuardContext() {
+ long now = System.currentTimeMillis();
+ CachedLoopMergeGuardContext cached = cachedLoopMergeGuardContext;
+ if (cached != null && now - cached.cacheAtMs <= STATION_PATH_RUNTIME_SNAPSHOT_TTL_MS) {
+ return new LoopMergeGuardContext(cached.context);
+ }
+ // 缂撳瓨杩囨湡锛氱敤杩囨湡缂撳瓨鍏滃簳锛園Scheduled 瀹氭椂浠诲姟浼氬緢蹇埛鏂帮級
+ if (cached != null) {
+ return new LoopMergeGuardContext(cached.context);
+ }
+ // 鏋佺鎯呭喌锛氫粠鏈湁杩囩紦瀛橈紝鍚屾鏋勫缓
+ LoopMergeGuardContext context = buildLoopMergeGuardContext();
+ cachedLoopMergeGuardContext = new CachedLoopMergeGuardContext(System.currentTimeMillis(), context);
+ return new LoopMergeGuardContext(context);
+ }
+
+ private LoopMergeGuardContext buildLoopMergeGuardContext() {
LoopMergeGuardContext context = new LoopMergeGuardContext();
try {
if (stationCycleCapacityService == null) {
@@ -2165,7 +2291,7 @@
}
}
long stepStartNs = System.nanoTime();
- Map<Integer, StationTaskTraceVo> fallbackTraceMap = loadFallbackActiveTraceMap(null, statusMap, traceMap.keySet());
+ Map<Integer, StationTaskTraceVo> fallbackTraceMap = buildProtocolFallbackTraceMap(statusMap, traceMap.keySet());
if (stepCostMap != null) {
stepCostMap.put("loadFallbackTraces", elapsedMillis(stepStartNs));
}
@@ -2183,6 +2309,55 @@
return StationTaskTraceRegistry.STATUS_WAITING.equals(status)
|| StationTaskTraceRegistry.STATUS_RUNNING.equals(status)
|| StationTaskTraceRegistry.STATUS_REROUTED.equals(status);
+ }
+
+ private Map<Integer, StationTaskTraceVo> buildProtocolFallbackTraceMap(Map<Integer, StationProtocol> statusMap,
+ Set<Integer> existingTaskNoSet) {
+ if (statusMap == null || statusMap.isEmpty()) {
+ return Collections.emptyMap();
+ }
+ Map<Integer, StationTaskTraceVo> result = new LinkedHashMap<>();
+ for (StationProtocol protocol : statusMap.values()) {
+ if (protocol == null || protocol.getTaskNo() == null || protocol.getTaskNo() <= 0) {
+ continue;
+ }
+ if (!Boolean.TRUE.equals(protocol.isLoading())) {
+ continue;
+ }
+ if (existingTaskNoSet != null && existingTaskNoSet.contains(protocol.getTaskNo())) {
+ continue;
+ }
+ Integer stationId = protocol.getStationId();
+ Integer targetStaNo = protocol.getTargetStaNo();
+ if (stationId == null || targetStaNo == null || stationId.equals(targetStaNo)) {
+ continue;
+ }
+ List<Integer> path = new ArrayList<>();
+ path.add(stationId);
+ path.add(targetStaNo);
+ List<Integer> pendingStationIds = new ArrayList<>();
+ pendingStationIds.add(targetStaNo);
+ StationTaskTraceVo vo = new StationTaskTraceVo();
+ vo.setTaskNo(protocol.getTaskNo());
+ vo.setThreadImpl("PROTOCOL_FALLBACK");
+ vo.setStatus(StationTaskTraceRegistry.STATUS_RUNNING);
+ vo.setTraceVersion(1);
+ vo.setStartStationId(stationId);
+ vo.setCurrentStationId(stationId);
+ vo.setFinalTargetStationId(targetStaNo);
+ vo.setFullPathStationIds(path);
+ vo.setIssuedStationIds(path);
+ vo.setPassedStationIds(Collections.emptyList());
+ vo.setPendingStationIds(pendingStationIds);
+ vo.setLatestIssuedSegmentPath(path);
+ vo.setSegmentList(Collections.emptyList());
+ vo.setIssuedSegmentCount(0);
+ vo.setTotalSegmentCount(1);
+ vo.setUpdatedAt(System.currentTimeMillis());
+ vo.setEvents(Collections.emptyList());
+ result.put(protocol.getTaskNo(), vo);
+ }
+ return result;
}
private Map<Integer, StationTaskTraceVo> loadFallbackActiveTraceMap(Integer currentTaskNo,
@@ -2605,6 +2780,8 @@
}
Integer lev = startStation.getStationLev();
stepCostMap.put("loadStartStation", elapsedMillis(stepStartNs));
+ log.info("绔欑偣璺緞鎼滅储涓婁笅鏂囧姞杞借捣鐐瑰畬鎴愶紝startStationId={}锛宔ndStationId={}锛宮ode={}锛宭ev={}锛宑ostMs={}",
+ startStationId, endStationId, calcMode, lev, stepCostMap.get("loadStartStation"));
stepStartNs = System.nanoTime();
NavigateSolution navigateSolution = new NavigateSolution();
@@ -2621,6 +2798,16 @@
throw new CoolException("鏈壘鍒拌 缁堢偣 瀵瑰簲鐨勮妭鐐�");
}
stepCostMap.put("loadStationMapAndNode", elapsedMillis(stepStartNs));
+ log.info("绔欑偣璺緞鎼滅储涓婁笅鏂囧姞杞藉湴鍥惧畬鎴愶紝startStationId={}锛宔ndStationId={}锛宮ode={}锛宮apRows={}锛宻tartNode=({},{})锛宔ndNode=({},{})锛宑ostMs={}",
+ startStationId,
+ endStationId,
+ calcMode,
+ stationMap.size(),
+ startNode.getX(),
+ startNode.getY(),
+ endNode.getX(),
+ endNode.getY(),
+ stepCostMap.get("loadStationMapAndNode"));
stepStartNs = System.nanoTime();
StationPathProfileConfig profileConfig = resolvedPolicy.getProfileConfig() == null
@@ -2634,9 +2821,17 @@
endStationId,
calcMode == null ? "" : calcMode.name());
int calcMaxDepth = safeInt(profileConfig.getCalcMaxDepth(), 120);
- int calcMaxPaths = safeInt(profileConfig.getCalcMaxPaths(), 500);
+ int calcMaxPaths = safeInt(profileConfig.getCalcMaxPaths(), 50);
int calcMaxCost = safeInt(profileConfig.getCalcMaxCost(), 300);
List<Integer> guideStationSequence = buildGuideStationSequence(startStationId, endStationId, resolvedPolicy.getRuleConfig());
+ log.info("绔欑偣璺緞鍊欓�夋灇涓惧紑濮嬶紝startStationId={}锛宔ndStationId={}锛宮ode={}锛宑alcMaxDepth={}锛宑alcMaxPaths={}锛宑alcMaxCost={}锛実uideStationSequence={}",
+ startStationId,
+ endStationId,
+ calcMode,
+ calcMaxDepth,
+ calcMaxPaths,
+ calcMaxCost,
+ JSON.toJSONString(guideStationSequence));
stepStartNs = System.nanoTime();
List<List<NavigateNode>> allList = navigateSolution.allSimplePaths(
stationMap,
@@ -2649,6 +2844,12 @@
);
stepCostMap.put("allSimplePaths", elapsedMillis(stepStartNs));
rawCandidateCount = allList.size();
+ log.info("绔欑偣璺緞鍊欓�夋灇涓惧畬鎴愶紝startStationId={}锛宔ndStationId={}锛宮ode={}锛宺awCandidateCount={}锛宑ostMs={}",
+ startStationId,
+ endStationId,
+ calcMode,
+ rawCandidateCount,
+ stepCostMap.get("allSimplePaths"));
if (allList.isEmpty()) {
logStationPathSearchContextSlow(startStationId, endStationId, calcMode, lev, rawCandidateCount, filteredCandidateCount, stepCostMap, totalStartNs);
return StationPathSearchContext.empty(resolvedPolicy);
@@ -2658,6 +2859,14 @@
allList = filterNonAutoStationPaths(allList, statusMap);
stepCostMap.put("filterNonAutoStation", elapsedMillis(stepStartNs));
filteredCandidateCount = allList.size();
+ log.info("绔欑偣璺緞鍊欓�夎嚜鍔ㄧ姸鎬佽繃婊ゅ畬鎴愶紝startStationId={}锛宔ndStationId={}锛宮ode={}锛宺awCandidateCount={}锛宖ilteredCandidateCount={}锛宻tatusCount={}锛宑ostMs={}",
+ startStationId,
+ endStationId,
+ calcMode,
+ rawCandidateCount,
+ filteredCandidateCount,
+ statusMap.size(),
+ stepCostMap.get("filterNonAutoStation"));
if (allList.isEmpty()) {
News.info("[WCS Debug] 绔欑偣璺緞鍊欓�夊叏閮ㄨ杩囨护锛屽瓨鍦ㄩ潪鑷姩绔欑偣,startStationId={},endStationId={}", startStationId, endStationId);
logStationPathSearchContextSlow(startStationId, endStationId, calcMode, lev, rawCandidateCount, filteredCandidateCount, stepCostMap, totalStartNs);
@@ -3034,6 +3243,16 @@
}
}
+ private static class CachedLoopMergeGuardContext {
+ private final long cacheAtMs;
+ private final LoopMergeGuardContext context;
+
+ private CachedLoopMergeGuardContext(long cacheAtMs, LoopMergeGuardContext context) {
+ this.cacheAtMs = cacheAtMs;
+ this.context = context;
+ }
+ }
+
private static class PathCandidateMetrics {
private List<NavigateNode> path;
private int pathLen;
@@ -3087,6 +3306,16 @@
private static class LoopMergeGuardContext {
private final Set<Integer> loopStationIdSet = new HashSet<>();
private final Map<Integer, Set<Integer>> loopNeighborMap = new HashMap<>();
+
+ private LoopMergeGuardContext() {
+ }
+
+ private LoopMergeGuardContext(LoopMergeGuardContext source) {
+ this.loopStationIdSet.addAll(source.loopStationIdSet);
+ for (Map.Entry<Integer, Set<Integer>> entry : source.loopNeighborMap.entrySet()) {
+ this.loopNeighborMap.put(entry.getKey(), new LinkedHashSet<>(entry.getValue()));
+ }
+ }
}
private static class LoopMergeEntry {
--
Gitblit v1.9.1