SpringBoot 與 JGraphT 整合，實現(xiàn)物流路徑優(yōu)化系統(tǒng)
作者：Java知識日歷
通過使用圖論算法，我們可以將運輸網(wǎng)絡(luò)建模為一個圖，其中節(jié)點代表城市或倉庫，邊代表連接這些地點的道路或航線。然后，我們可以通過各種圖論算法來尋找最優(yōu)路徑。
在物流行業(yè)中，合理的路線規(guī)劃可以減少運輸成本、提高效率，并且降低對環(huán)境的影響。通過使用圖論算法，我們可以將運輸網(wǎng)絡(luò)建模為一個圖，其中節(jié)點代表城市或倉庫，邊代表連接這些地點的道路或航線。然后，我們可以通過各種圖論算法來尋找最優(yōu)路徑。
一、JGraphT
1. 開源且成熟
- 開源: JGraphT是一個完全開源的Java庫，遵循Apache License 2.0協(xié)議。這意味著你可以自由地使用、修改和分發(fā)該庫。
- 成熟: JGraphT已經(jīng)存在多年，擁有大量的用戶基礎(chǔ)和社區(qū)支持。這確保了其穩(wěn)定性和可靠性。
2. 功能豐富
- 多種圖類型: 支持有向圖、無向圖、加權(quán)圖等多種圖類型。
- 豐富的算法集: 提供了許多常用的圖論算法，包括最短路徑（Dijkstra、A*）、最小生成樹（Kruskal、Prim）、最大流等。
- 靈活的數(shù)據(jù)結(jié)構(gòu): 支持不同的頂點和邊數(shù)據(jù)結(jié)構(gòu)，可以根據(jù)具體需求進行定制。
3. 易于集成
- 純Java實現(xiàn): 完全用Java編寫，易于與其他Java項目集成。
- 良好的文檔: 提供詳細的API文檔和示例代碼，便于開發(fā)者快速上手。
- 活躍社區(qū): 擁有一個活躍的社區(qū)，可以獲取及時的支持和幫助。
4. 高性能
- 高效的算法實現(xiàn): JGraphT中的算法經(jīng)過優(yōu)化，能夠在大規(guī)模圖數(shù)據(jù)上高效運行。
- 內(nèi)存管理: 有效的內(nèi)存管理和數(shù)據(jù)結(jié)構(gòu)設(shè)計，減少了不必要的開銷。
二、我們選擇JGraphT的理由
1. 快速開發(fā)
- 簡化復(fù)雜性: 使用JGraphT可以輕松實現(xiàn)復(fù)雜的圖論算法，無需從頭開始編寫底層代碼。
- 節(jié)省時間: 減少了開發(fā)周期，加快了產(chǎn)品上市速度。
2. 可靠性和可維護性
- 穩(wěn)定的庫: JGraphT經(jīng)過長期測試和優(yōu)化，確保了系統(tǒng)的可靠性和穩(wěn)定性。
- 清晰的架構(gòu): 代碼結(jié)構(gòu)清晰，易于維護和擴展。
3. 成本效益
- 免費使用: 開源特性意味著無需支付額外費用。
- 高質(zhì)量支持: 社區(qū)支持強大，出現(xiàn)問題時可以獲得及時的幫助。
三、代碼實操
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-web</artifactId>
</dependency>
<dependency>
<groupId>org.jgrapht</groupId>
<artifactId>jgrapht-core</artifactId>
<version>1.5.2</version>
</dependency>
<dependency>
<groupId>org.projectlombok</groupId>
<artifactId>lombok</artifactId>
<optional>true</optional>
</dependency>
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-validation</artifactId>
</dependency>四、城市類
package com.example.logistics.model;
import lombok.Data;
import javax.validation.constraints.NotBlank;
import javax.validation.constraints.NotNull;
/**
* 城市模型類，表示圖中的節(jié)點。
*/
@Data
public class City {
@NotBlank(message = "城市ID不能為空")
private String id;
@NotBlank(message = "城市名稱不能為空")
private String name;
}五、道路類
package com.example.logistics.model;
import lombok.Data;
import javax.validation.constraints.Min;
import javax.validation.constraints.NotNull;
/**
* 道路模型類，表示圖中的邊。
*/
@Data
public class Road {
@NotNull(message = "源城市ID不能為空")
private String sourceId;
@NotNull(message = "目標城市ID不能為空")
private String targetId;
@Min(value = 0, message = "權(quán)重必須非負")
private double weight; // 表示距離或其他成本
}六、運輸數(shù)據(jù)
package com.example.logistics.model;
import lombok.Data;
import javax.validation.Valid;
import javax.validation.constraints.NotEmpty;
import java.util.List;
/**
* 運輸數(shù)據(jù)模型類，包含城市和道路的信息。
*/
@Data
public class TransportData {
@NotEmpty(message = "城市列表不能為空")
@Valid
private List<City> cities;
@NotEmpty(message = "道路列表不能為空")
@Valid
private List<Road> roads;
}七、處理無效請求的異常
package com.example.logistics.exception;
import org.springframework.http.HttpStatus;
import org.springframework.web.bind.annotation.ResponseStatus;
/**
* 自定義異常類，用于處理無效請求的情況。
*/
@ResponseStatus(HttpStatus.BAD_REQUEST)
public class BadRequestException extends RuntimeException {
public BadRequestException(String message) {
super(message);
}
}八、處理資源未找到的異常
package com.example.logistics.exception;
import org.springframework.http.HttpStatus;
import org.springframework.web.bind.annotation.ResponseStatus;
/**
* 自定義異常類，用于處理資源未找到的情況。
*/
@ResponseStatus(HttpStatus.NOT_FOUND)
public class ResourceNotFoundException extends RuntimeException {
public ResourceNotFoundException(String message) {
super(message);
}
}九、負責(zé)構(gòu)建和管理圖模型
package com.example.logistics.service;
import com.example.logistics.exception.ResourceNotFoundException;
import com.example.logistics.model.City;
import com.example.logistics.model.Road;
import org.jgrapht.Graph;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleWeightedGraph;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.stereotype.Service;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* 交通網(wǎng)絡(luò)服務(wù)類，負責(zé)構(gòu)建和管理圖模型。
*/
@Service
public class TransportationNetworkService {
private final Logger logger = LoggerFactory.getLogger(TransportationNetworkService.class);
private Map<String, City> cityMap = new HashMap<>();
private Graph<City, DefaultWeightedEdge> graph;
/**
* 初始化圖對象。
*/
public TransportationNetworkService() {
this.graph = new SimpleWeightedGraph<>(DefaultWeightedEdge.class);
}
/**
* 根據(jù)輸入的城市和道路信息構(gòu)建圖模型。
*
* @param cities 城市列表
* @param roads 道路列表
*/
public void buildNetwork(List<City> cities, List<Road> roads) {
logger.info("正在構(gòu)建包含 {} 個城市和 {} 條道路的交通網(wǎng)絡(luò)", cities.size(), roads.size());
for (City city : cities) {
if (!cityMap.containsKey(city.getId())) {
graph.addVertex(city);
cityMap.put(city.getId(), city);
} else {
throw new BadRequestException("重復(fù)的城市ID: " + city.getId());
}
}
for (Road road : roads) {
City source = cityMap.get(road.getSourceId());
City target = cityMap.get(road.getTargetId());
if (source == null || target == null) {
throw new BadRequestException("無效的道路連接城市: " + road.getSourceId() + " 和 " + road.getTargetId());
}
DefaultWeightedEdge edge = graph.addEdge(source, target);
graph.setEdgeWeight(edge, road.getWeight());
}
}
/**
* 獲取當前構(gòu)建的圖模型。
*
* @return 圖模型
*/
public Graph<City, DefaultWeightedEdge> getGraph() {
return graph;
}
/**
* 根據(jù)城市ID查找城市對象。
*
* @param id 城市ID
* @return 找到的城市對象
* @throws ResourceNotFoundException 如果找不到對應(yīng)的城市
*/
public City findCityById(String id) {
City city = cityMap.get(id);
if (city == null) {
throw new ResourceNotFoundException("未找到ID為 " + id + " 的城市");
}
return city;
}
}十、使用圖論算法計算最優(yōu)路徑
package com.example.logistics.service;
import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
import org.jgrapht.alg.spanning.KruskalMinimumSpanningTree;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;
import java.util.Set;
/**
* 路徑優(yōu)化服務(wù)類，使用圖論算法計算最優(yōu)路徑。
*/
@Service
public class PathOptimizer {
private final Logger logger = LoggerFactory.getLogger(PathOptimizer.class);
@Autowired
private TransportationNetworkService networkService;
/**
* 計算最小生成樹（MST）。
*
* @return 最小生成樹的邊集合
*/
public Set<DefaultWeightedEdge> computeMST() {
logger.info("正在計算最小生成樹（MST）");
KruskalMinimumSpanningTree<City, DefaultWeightedEdge> mstAlg =
new KruskalMinimumSpanningTree<>(networkService.getGraph());
return mstAlg.getSpanningTree();
}
/**
* 使用Dijkstra算法計算最短路徑。
*
* @param source 源城市
* @param target 目標城市
* @return 最短路徑對象
*/
public DijkstraShortestPath<City, DefaultWeightedEdge> computeShortestPath(City source, City target) {
logger.info("正在計算從 {} 到 {} 的最短路徑", source.getName(), target.getName());
DijkstraShortestPath<City, DefaultWeightedEdge> dijkstraAlg =
new DijkstraShortestPath<>(networkService.getGraph());
return dijkstraAlg.getPath(source, target);
}
}我們使用了JGraphT庫中的KruskalMinimumSpanningTree類來計算最小生成樹。
1. 最小生成樹（Minimum Spanning Tree - MST）
最小生成樹是指在一個加權(quán)無向圖中，選取一些邊組成一棵樹，使得該樹的所有頂點都屬于原圖，并且所有邊都在原圖中，同時這些邊的總權(quán)重最小。
Kruskal算法：
(1) 步驟：
- 將圖中的所有邊按權(quán)重從小到大排序。
- 依次取出每條邊，如果這條邊連接的兩個頂點不在同一個連通分量中，則將這條邊加入最小生成樹中，并合并這兩個連通分量。
- 重復(fù)上述過程直到形成一個包含所有頂點的樹。
(2) 優(yōu)點: 算法簡單易懂，適合稀疏圖。
(3) 缺點: 對于稠密圖效率較低。
我們使用了JGraphT庫中的DijkstraShortestPath類來計算最短路徑。
2. 最短路徑（Shortest Path）
最短路徑是指在圖中尋找兩點之間的路徑，使得路徑上所有邊的權(quán)重之和最小。
Dijkstra算法:
(1) 步驟:
- 初始化：設(shè)置起點的距離為0，其他點的距離為無窮大；初始化優(yōu)先隊列，將起點放入隊列。
- 取出隊列中距離最小的頂點u。
- 更新與u相鄰的所有頂點v的距離，如果通過u到達v的距離比之前記錄的小，則更新距離并將v加入隊列。
- 重復(fù)上述過程直到隊列為空。
(2) 優(yōu)點: 能夠有效地解決單源最短路徑問題。
(3) 缺點: 不適用于有負權(quán)邊的圖。
十一、Controller
package com.example.logistics.controller;
import com.example.logistics.exception.BadRequestException;
import com.example.logistics.model.City;
import com.example.logistics.model.TransportData;
import com.example.logistics.service.PathOptimizer;
import com.example.logistics.service.TransportationNetworkService;
import org.jgrapht.alg.shortestpath.DijkstraShortestPath;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.http.ResponseEntity;
import org.springframework.validation.BindingResult;
import org.springframework.web.bind.annotation.*;
import javax.validation.Valid;
import java.util.Set;
/**
* 傳輸控制器類，提供RESTful API接口。
*/
@RestController
@RequestMapping("/api/transport")
public class TransportController {
private final Logger logger = LoggerFactory.getLogger(TransportController.class);
@Autowired
private TransportationNetworkService networkService;
@Autowired
private PathOptimizer pathOptimizer;
/**
* 構(gòu)建交通網(wǎng)絡(luò)。
*
* @param data 包含城市和道路信息的傳輸數(shù)據(jù)
* @param bindingResult 綁定結(jié)果，用于驗證輸入數(shù)據(jù)
* @return 成功響應(yīng)
* @throws BadRequestException 如果輸入數(shù)據(jù)無效
*/
@PostMapping("/build-network")
public ResponseEntity<Void> buildNetwork(@Valid @RequestBody TransportData data, BindingResult bindingResult) {
if (bindingResult.hasErrors()) {
logger.error("驗證錯誤: {}", bindingResult.getAllErrors());
throw new BadRequestException(bindingResult.getAllErrors().toString());
}
try {
networkService.buildNetwork(data.getCities(), data.getRoads());
logger.info("交通網(wǎng)絡(luò)構(gòu)建成功");
return ResponseEntity.ok().build();
} catch (Exception e) {
logger.error("構(gòu)建交通網(wǎng)絡(luò)時出錯: ", e);
throw new BadRequestException(e.getMessage());
}
}
/**
* 計算最小生成樹（MST）。
*
* @return 最小生成樹的邊集合
*/
@GetMapping("/compute-mst")
public ResponseEntity<Set<DefaultWeightedEdge>> computeMST() {
Set<DefaultWeightedEdge> mstEdges = pathOptimizer.computeMST();
logger.info("計算得到的MST邊集: {}", mstEdges);
return ResponseEntity.ok(mstEdges);
}
/**
* 計算最短路徑。
*
* @param sourceId 源城市ID
* @param targetId 目標城市ID
* @return 最短路徑對象
* @throws ResourceNotFoundException 如果找不到對應(yīng)的源或目標城市
*/
@GetMapping("/shortest-path/{sourceId}/{targetId}")
public ResponseEntity<DijkstraShortestPath<City, DefaultWeightedEdge>> computeShortestPath(
@PathVariable String sourceId,
@PathVariable String targetId) {
City source = networkService.findCityById(sourceId);
City target = networkService.findCityById(targetId);
DijkstraShortestPath<City, DefaultWeightedEdge> path = pathOptimizer.computeShortestPath(source, target);
logger.info("計算得到的最短路徑: {}", path);
return ResponseEntity.ok(path);
}
}十二、LogisticsApplication.java
package com.example.logistics;
import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;
@SpringBootApplication
public class LogisticsApplication {
public static void main(String[] args) {
SpringApplication.run(LogisticsApplication.class, args);
}
}十三、配置文件 (application.properties)
server.port=8080
logging.level.org.springframework.web=INFO
logging.level.com.example.logistics=DEBUG十四、測試結(jié)果
1. 構(gòu)建交通網(wǎng)絡(luò)
curl -X POST http://localhost:8080/api/transport/build-network \
-H "Content-Type: application/json" \
-d '{
"cities": [
{"id": "C1", "name": "City1"},
{"id": "C2", "name": "City2"},
{"id": "C3", "name": "City3"}
],
"roads": [
{"sourceId": "C1", "targetId": "C2", "weight": 10},
{"sourceId": "C2", "targetId": "C3", "weight": 15},
{"sourceId": "C1", "targetId": "C3", "weight": 20}
]
}'Respons：
{}2. 計算最小生成樹（MST）
curl -X GET http://localhost:8080/api/transport/compute-mstRespons：
[
{
"source": {"id": "C1", "name": "City1"},
"target": {"id": "C2", "name": "City2"},
"weight": 10
},
{
"source": {"id": "C2", "name": "City2"},
"target": {"id": "C3", "name": "City3"},
"weight": 15
}
]3. 計算最短路徑
curl -X GET http://localhost:8080/api/transport/shortest-path/C1/C3Respons：
{
"startVertex": {"id": "C1", "name": "City1"},
"endVertex": {"id": "C3", "name": "City3"},
"length": 25,
"edgeList": [
{
"source": {"id": "C1", "name": "City1"},
"target": {"id": "C2", "name": "City2"},
"weight": 10
},
{
"source": {"id": "C2", "name": "City2"},
"target": {"id": "C3", "name": "City3"},
"weight": 15
}
]
}責(zé)任編輯：趙寧寧
來源：
Java知識日歷
