算法

引言 路线优化是TMS的核心技术之一,直接影响运输成本和配送效率。据统计,优化后的配送路线可以减少20-30%的行驶里程,节省大量燃油成本。 本文将深入探讨路线优化的两大经典问题——TSP(旅行商问题)和VRP(车辆路径问题),并提供Java实现代码和地图服务对接方案。 1. TSP问题(旅行商问题) 1.1 问题定义 TSP(Traveling Salesman Problem)： 一个销售员要访问n个城市,每个城市只访问一次,最后回到起点,求最短路径。 数学描述： 给定: - N个城市: C = {c1, c2, ..., cn} - 距离矩阵: D[i][j] = 城市i到城市j的距离 求: - 一条路径 P = {ci1, ci2, ..., cin} - 使得总距离最小: sum(D[cik][cik+1]) + D[cin][ci1] 约束: - 每个城市访问且仅访问一次 示例： 城市: A, B, C, D 距离矩阵: A B C D A 0 10 15 20 B 10 0 35 25 C 15 35 0 30 D 20 25 30 0 可能的路径: - A → B → C → D → A: 10 + 35 + 30 + 20 = 95 - A → B → D → C → A: 10 + 25 + 30 + 15 = 80 ✓ (最优) - A → C → B → D → A: 15 + 35 + 25 + 20 = 95 1.2 算法选型 穷举法 原理：枚举所有可能的路径,选择最短的。 ...

核心观点: 限流算法不是单纯的技术选择，而是业务需求与技术约束的权衡。本文从一个真实需求的演进过程出发，深度剖析5种限流算法的设计思路、实现细节和适用场景。 引子：一个API接口的限流需求演进 需求背景 你是某电商平台的后端工程师，负责维护商品查询接口 /api/products/{id}。 初始状态（无限流）: @RestController public class ProductController { @Autowired private ProductService productService; @GetMapping("/api/products/{id}") public Result getProduct(@PathVariable Long id) { Product product = productService.getById(id); return Result.success(product); } } 系统运行良好，日常流量500 QPS，数据库和服务器完全可以承受。 第一次危机：流量突增 某天，运营部门做了一个促销活动，流量突然涨到5000 QPS（10倍）。 后果: 10:00:00 - 活动开始，流量5000 QPS 10:00:30 - 数据库连接池耗尽（最大连接数100） 10:01:00 - 响应时间从50ms暴增到5秒 10:01:30 - 服务器CPU 100%，系统崩溃 CTO找你谈话: “给这个接口加个限流，最多支持1000 QPS。” 你的第一反应：计数器！ 需求演进1：固定窗口计数器 需求: 每秒最多1000个请求。 你快速实现了一个固定窗口计数器： public class FixedWindowRateLimiter { private final int maxRequests; private final AtomicInteger counter = new AtomicInteger(0); private volatile long windowStart = System.currentTimeMillis(); public FixedWindowRateLimiter(int maxRequests) { this.maxRequests = maxRequests; } public boolean tryAcquire() { long now = System.currentTimeMillis(); // 新窗口，重置计数器 if (now - windowStart >= 1000) { synchronized (this) { if (now - windowStart >= 1000) { counter.set(0); windowStart = now; } } } // 当前窗口未超限 return counter.incrementAndGet() <= maxRequests; } } 部署上线，问题解决！系统稳定运行。 ...