From 96f987b030f4c961a985f07079ba12abd865fdb2 Mon Sep 17 00:00:00 2001
From: Junjie <DELL@qq.com>
Date: 星期三, 17 十二月 2025 08:12:24 +0800
Subject: [PATCH] #
---
src/main/java/com/zy/common/utils/NavigateUtils.java | 175 +++++++++++++++++++++++++++++++----
src/main/java/com/zy/common/utils/NavigateSolution.java | 111 ++++++++++++++++++++++
2 files changed, 266 insertions(+), 20 deletions(-)
diff --git a/src/main/java/com/zy/common/utils/NavigateSolution.java b/src/main/java/com/zy/common/utils/NavigateSolution.java
index e6cb942..e189e68 100644
--- a/src/main/java/com/zy/common/utils/NavigateSolution.java
+++ b/src/main/java/com/zy/common/utils/NavigateSolution.java
@@ -10,6 +10,8 @@
import com.zy.common.model.NavigateNode;
import com.zy.core.enums.MapNodeType;
import java.util.*;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.function.BiFunction;
/**
* A*绠楁硶瀹炵幇绫�
@@ -157,6 +159,115 @@
return null;
}
+ public List<List<NavigateNode>> allSimplePaths(
+ List<List<NavigateNode>> map,
+ NavigateNode start,
+ NavigateNode end,
+ int maxDepth, // 鏈�澶ф鏁�(杈规暟). 寤鸿锛�50/100/200锛�<=0 琛ㄧず涓嶉檺鍒讹紙涓嶅缓璁級
+ int maxPaths, // 鏈�澶ц繑鍥炴潯鏁�. 寤鸿锛�100/500/2000锛�<=0 琛ㄧず涓嶉檺鍒讹紙涓嶅缓璁級
+ int maxCost // 鏈�澶ф�讳唬浠�(鍚嫄鐐规儵缃�). <=0 琛ㄧず涓嶉檺鍒�
+ ) {
+ List<List<NavigateNode>> results = new ArrayList<>();
+ if (map == null || map.isEmpty() || map.get(0).isEmpty()) return results;
+ if (start == null || end == null) return results;
+ if (start.getValue() == MapNodeType.DISABLE.id || end.getValue() == MapNodeType.DISABLE.id) return results;
+
+ // visited 鐢ㄥ潗鏍� key锛岄伩鍏� NavigateNode equals/hashCode 涓嶅彲闈犲鑷撮噸澶嶅垽鏂け鏁�
+ Set<String> visited = new HashSet<>(map.size() * map.get(0).size() * 2);
+ LinkedList<NavigateNode> path = new LinkedList<>();
+
+ String startKey = keyOf(start);
+ visited.add(startKey);
+ path.add(start);
+
+ AtomicInteger pathCount = new AtomicInteger(0);
+
+ dfsAllSimplePaths(map, start, end,
+ visited, path, results,
+ 0, // depth
+ 0, // cost
+ maxDepth, maxPaths, maxCost,
+ pathCount
+ );
+
+ return results;
+ }
+
+ /**
+ * DFS + 鍥炴函锛氭灇涓炬墍鏈夌畝鍗曡矾寰勶紙璺緞涓笉鍏佽閲嶅鑺傜偣锛�
+ */
+ private void dfsAllSimplePaths(
+ List<List<NavigateNode>> map,
+ NavigateNode current,
+ NavigateNode end,
+ Set<String> visited,
+ LinkedList<NavigateNode> path,
+ List<List<NavigateNode>> results,
+ int depth, // 褰撳墠姝ユ暟锛堣竟鏁帮級
+ int cost, // 褰撳墠鎬讳唬浠凤紙浣犲彲浠ヨ涓烘槸 g锛�
+ int maxDepth,
+ int maxPaths,
+ int maxCost,
+ AtomicInteger pathCount
+ ) {
+ // 闃茬垎锛氭潯鏁伴檺鍒�
+ if (maxPaths > 0 && pathCount.get() >= maxPaths) return;
+
+ // 鍒拌揪缁堢偣锛氭敹闆嗚矾寰�
+ if (current.getX() == end.getX() && current.getY() == end.getY()) {
+ results.add(new ArrayList<>(path));
+ pathCount.incrementAndGet();
+ return;
+ }
+
+ // 闃茬垎锛氭繁搴﹂檺鍒讹紙depth 琛ㄧず宸茶蛋鐨勮竟鏁帮級
+ if (maxDepth > 0 && depth >= maxDepth) return;
+
+ // 鎵╁睍閭诲眳锛堜弗鏍煎鐢ㄤ綘鑷繁鐨勫彲琛岃蛋鏂瑰悜瑙勫垯锛�
+ ArrayList<NavigateNode> neighbors = extend_current_node(map, current);
+ if (neighbors == null || neighbors.isEmpty()) return;
+
+ for (NavigateNode next : neighbors) {
+ // 闃茬垎锛氭潯鏁伴檺鍒�
+ if (maxPaths > 0 && pathCount.get() >= maxPaths) return;
+
+ if (next == null) continue;
+ if (next.getValue() == MapNodeType.DISABLE.id) continue;
+
+ String nk = keyOf(next);
+
+ // 绠�鍗曡矾寰勶細涓嶅厑璁搁噸澶嶈妭鐐�
+ if (visited.contains(nk)) continue;
+
+ // 浣犵殑浠ｄ环瑙勫垯锛氭瘡姝� 1 + 鎷愮偣鎯╃綒
+ int stepCost = 1 + calcNodeExtraCost(current, next, end);
+ int newCost = cost + stepCost;
+
+ // 闃茬垎锛氭�讳唬浠烽檺鍒�
+ if (maxCost > 0 && newCost > maxCost) continue;
+
+ // 杩涘叆
+ visited.add(nk);
+ path.addLast(next);
+
+ dfsAllSimplePaths(map, next, end,
+ visited, path, results,
+ depth + 1,
+ newCost,
+ maxDepth, maxPaths, maxCost,
+ pathCount
+ );
+
+ // 鍥炴函
+ path.removeLast();
+ visited.remove(nk);
+ }
+ }
+
+ private String keyOf(NavigateNode n) {
+ return n.getX() + "_" + n.getY();
+ }
+
public ArrayList<NavigateNode> extend_current_node(List<List<NavigateNode>> map, NavigateNode current_node) {
//鑾峰彇褰撳墠缁撶偣鐨剎, y
int x = current_node.getX();
diff --git a/src/main/java/com/zy/common/utils/NavigateUtils.java b/src/main/java/com/zy/common/utils/NavigateUtils.java
index 2e210a5..1a20b54 100644
--- a/src/main/java/com/zy/common/utils/NavigateUtils.java
+++ b/src/main/java/com/zy/common/utils/NavigateUtils.java
@@ -2,16 +2,28 @@
import java.util.ArrayList;
import java.util.Collections;
+import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
+import java.util.Map;
import com.zy.core.News;
import org.springframework.stereotype.Component;
import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.JSONObject;
+import com.baomidou.mybatisplus.mapper.EntityWrapper;
+import com.core.common.SpringUtils;
import com.core.exception.CoolException;
import com.zy.common.model.NavigateNode;
+import com.zy.asrs.entity.DeviceConfig;
+import com.zy.asrs.service.DeviceConfigService;
+import com.zy.core.cache.SlaveConnection;
+import com.zy.core.enums.SlaveType;
+import com.zy.core.model.protocol.StationProtocol;
+import com.zy.core.thread.StationThread;
+import com.zy.system.entity.Config;
+import com.zy.system.service.ConfigService;
@Component
public class NavigateUtils {
@@ -32,31 +44,19 @@
long startTime = System.currentTimeMillis();
News.info("[WCS Debug] 绔欑偣璺緞寮�濮嬭绠�,startStationId={},endStationId={}", startStationId, endStationId);
- NavigateNode res_node = navigateSolution.astarSearchJava(stationMap, startNode, endNode);
- if (res_node == null) {
+ List<List<NavigateNode>> allList = navigateSolution.allSimplePaths(stationMap, startNode, endNode, 120, 500, 300);
+ if (allList.isEmpty()) {
throw new CoolException("鏈壘鍒拌璺緞");
}
News.info("[WCS Debug] 绔欑偣璺緞璁＄畻瀹屾垚锛岃�楁椂锛歿}ms", System.currentTimeMillis() - startTime);
- ArrayList<NavigateNode> list = new ArrayList<>();
- // 浣跨敤 visited 闆嗗悎闃叉鐖堕摼鍑虹幇鐜鑷存寰幆锛屽悓鏃惰缃畨鍏ㄦ鏁颁笂闄�
- HashSet<NavigateNode> visited = new HashSet<>();
- int maxSteps = stationMap.size() * stationMap.get(0).size() + 5; // 瀹夊叏涓婇檺
- int steps = 0;
- while (res_node != null && visited.add(res_node) && steps++ < maxSteps) {
- list.add(res_node);
- res_node = res_node.getFather();//杩唬鎿嶄綔
+ if (allList.size() > 1) {
+ System.out.println(JSON.toJSONString(allList));
}
- if (steps >= maxSteps) {
- throw new CoolException("璺緞鍥炴函瓒呭嚭瀹夊叏涓婇檺锛岀枒浼煎瓨鍦ㄧ埗閾惧惊鐜�");
- }
- Collections.reverse(list);
- //灏嗘瘡涓妭鐐归噷闈㈢殑fatherNode鑷充负null(鏂逛究鍚庣画璁＄畻鏃剁埗鑺傜偣杩囧瀵艰嚧鏄剧ず鐨勮妭鐐瑰お澶�)
- for (NavigateNode navigateNode : list) {
- //鐖惰妭鐐硅缃负null锛屼笉褰卞搷璁＄畻缁撴灉锛屼笉褰卞搷鍚庣画鎿嶄綔銆�
- //姝ゆ搷浣滀粎涓哄悗缁帓鏌ュ鐞嗘彁渚涜瑙夋柟渚裤��
- navigateNode.setFather(null);
- }
+
+ News.info("[WCS Debug] 绔欑偣璺緞鏉冮噸寮�濮嬪垎鏋�,startStationId={},endStationId={}", startStationId, endStationId);
+ List<NavigateNode> list = findStationBestPath(allList);
+ News.info("[WCS Debug] 绔欑偣璺緞鏉冮噸鍒嗘瀽缁撴潫,startStationId={},endStationId={}", startStationId, endStationId);
//鍘婚噸
HashSet<Integer> set = new HashSet<>();
@@ -152,4 +152,139 @@
return liftStationList;
}
+
+ public synchronized List<NavigateNode> findStationBestPath(List<List<NavigateNode>> allList) {
+ if (allList == null || allList.isEmpty()) {
+ return new ArrayList<>();
+ }
+
+ Map<Integer, StationProtocol> statusMap = new HashMap<>();
+ try {
+ DeviceConfigService deviceConfigService = SpringUtils.getBean(DeviceConfigService.class);
+ if (deviceConfigService != null) {
+ List<DeviceConfig> devpList = deviceConfigService.selectList(new EntityWrapper<DeviceConfig>()
+ .eq("device_type", String.valueOf(SlaveType.Devp)));
+ for (DeviceConfig deviceConfig : devpList) {
+ StationThread stationThread = (StationThread) SlaveConnection.get(SlaveType.Devp, deviceConfig.getDeviceNo());
+ if (stationThread == null) {
+ continue;
+ }
+ Map<Integer, StationProtocol> m = stationThread.getStatusMap();
+ if (m != null && !m.isEmpty()) {
+ statusMap.putAll(m);
+ }
+ }
+ }
+ } catch (Exception ignore) {}
+
+ List<List<NavigateNode>> candidates = new ArrayList<>();
+ List<Integer> lens = new ArrayList<>();
+ List<Integer> tasksList = new ArrayList<>();
+ List<Double> congs = new ArrayList<>();
+
+ for (List<NavigateNode> path : allList) {
+ if (path == null || path.isEmpty()) {
+ continue;
+ }
+ int len = path.size();
+ int tasks = 0;
+ HashSet<Integer> stationIdSet = new HashSet<>();
+ for (NavigateNode node : path) {
+ JSONObject value = null;
+ try {
+ value = JSON.parseObject(node.getNodeValue());
+ } catch (Exception ignore) {}
+ if (value == null) {
+ continue;
+ }
+ Integer stationId = value.getInteger("stationId");
+ if (stationId == null) {
+ continue;
+ }
+ if (!stationIdSet.add(stationId)) {
+ continue;
+ }
+ StationProtocol protocol = statusMap.get(stationId);
+ if (protocol != null && protocol.getTaskNo() != null && protocol.getTaskNo() > 0) {
+ tasks++;
+ }
+ }
+ double cong = len <= 0 ? 0.0 : (double) tasks / (double) len;
+ candidates.add(path);
+ lens.add(len);
+ tasksList.add(tasks);
+ congs.add(cong);
+ }
+
+ if (candidates.isEmpty()) {
+ return allList.get(0);
+ }
+
+ int minLen = Integer.MAX_VALUE;
+ int maxLen = Integer.MIN_VALUE;
+ double minCong = Double.MAX_VALUE;
+ double maxCong = -Double.MAX_VALUE;
+ for (int i = 0; i < candidates.size(); i++) {
+ int l = lens.get(i);
+ double c = congs.get(i);
+ if (l < minLen) minLen = l;
+ if (l > maxLen) maxLen = l;
+ if (c < minCong) minCong = c;
+ if (c > maxCong) maxCong = c;
+ }
+
+ //闀垮害鏉冮噸鐧惧垎姣�
+ double lenWeightPercent = 50.0;
+ //鎷ュ牭鏉冮噸鐧惧垎姣�
+ double congWeightPercent = 50.0;
+ try {
+ ConfigService configService = SpringUtils.getBean(ConfigService.class);
+ if (configService != null) {
+ Config cfgLen = configService.selectOne(new EntityWrapper<Config>().eq("code", "stationPathLenWeightPercent"));
+ if (cfgLen != null && cfgLen.getValue() != null) {
+ String v = cfgLen.getValue().trim();
+ if (v.endsWith("%")) v = v.substring(0, v.length() - 1);
+ try { lenWeightPercent = Double.parseDouble(v); } catch (Exception ignore) {}
+ }
+ Config cfgCong = configService.selectOne(new EntityWrapper<Config>().eq("code", "stationPathCongWeightPercent"));
+ if (cfgCong != null && cfgCong.getValue() != null) {
+ String v = cfgCong.getValue().trim();
+ if (v.endsWith("%")) v = v.substring(0, v.length() - 1);
+ try { congWeightPercent = Double.parseDouble(v); } catch (Exception ignore) {}
+ }
+ }
+ } catch (Exception ignore) {}
+
+ double weightSum = lenWeightPercent + congWeightPercent;
+ double lenW = weightSum <= 0 ? 0.5 : lenWeightPercent / weightSum;
+ double congW = weightSum <= 0 ? 0.5 : congWeightPercent / weightSum;
+
+ List<NavigateNode> best = null;
+ double bestCost = Double.MAX_VALUE;
+ int bestTasks = Integer.MAX_VALUE;
+ int bestLen = Integer.MAX_VALUE;
+ for (int i = 0; i < candidates.size(); i++) {
+ int l = lens.get(i);
+ int t = tasksList.get(i);
+ double c = congs.get(i);
+ //褰掍竴鍖�
+ double lenNorm = (maxLen - minLen) <= 0 ? 0.0 : (l - minLen) / (double) (maxLen - minLen);
+ double congNorm = (maxCong - minCong) <= 0 ? 0.0 : (c - minCong) / (double) (maxCong - minCong);
+ //鑾峰彇鏉冮噸
+ double cost = lenNorm * lenW + congNorm * congW;
+ if (cost < bestCost
+ || (cost == bestCost && t < bestTasks)
+ || (cost == bestCost && t == bestTasks && l < bestLen)) {
+ best = candidates.get(i);
+ bestCost = cost;
+ bestTasks = t;
+ bestLen = l;
+ }
+ }
+
+ if (best == null) {
+ return allList.get(0);
+ }
+ return best;
+ }
}
--
Gitblit v1.9.1