SpringBoot 與 JGraphT 整合，實現物流路徑優化系統

作者：Java知識日歷 2025-03-03 07:30:00

開發

通過使用圖論算法，我們可以將運輸網絡建模為一個圖，其中節點代表城市或倉庫，邊代表連接這些地點的道路或航線。然后，我們可以通過各種圖論算法來尋找最優路徑。

在物流行業中，合理的路線規劃可以減少運輸成本、提高效率，并且降低對環境的影響。通過使用圖論算法，我們可以將運輸網絡建模為一個圖，其中節點代表城市或倉庫，邊代表連接這些地點的道路或航線。然后，我們可以通過各種圖論算法來尋找最優路徑。

一、JGraphT

1. 開源且成熟

開源: JGraphT是一個完全開源的Java庫，遵循Apache License 2.0協議。這意味著你可以自由地使用、修改和分發該庫。
成熟: JGraphT已經存在多年，擁有大量的用戶基礎和社區支持。這確保了其穩定性和可靠性。

2. 功能豐富

多種圖類型: 支持有向圖、無向圖、加權圖等多種圖類型。
豐富的算法集: 提供了許多常用的圖論算法，包括最短路徑（Dijkstra、A*）、最小生成樹（Kruskal、Prim）、最大流等。
靈活的數據結構: 支持不同的頂點和邊數據結構，可以根據具體需求進行定制。

3. 易于集成

純Java實現: 完全用Java編寫，易于與其他Java項目集成。
良好的文檔: 提供詳細的API文檔和示例代碼，便于開發者快速上手。
活躍社區: 擁有一個活躍的社區，可以獲取及時的支持和幫助。

4. 高性能

高效的算法實現: JGraphT中的算法經過優化，能夠在大規模圖數據上高效運行。
內存管理: 有效的內存管理和數據結構設計，減少了不必要的開銷。

二、我們選擇JGraphT的理由

1. 快速開發

簡化復雜性: 使用JGraphT可以輕松實現復雜的圖論算法，無需從頭開始編寫底層代碼。
節省時間: 減少了開發周期，加快了產品上市速度。

2. 可靠性和可維護性

穩定的庫: JGraphT經過長期測試和優化，確保了系統的可靠性和穩定性。
清晰的架構: 代碼結構清晰，易于維護和擴展。

3. 成本效益

免費使用: 開源特性意味著無需支付額外費用。
高質量支持: 社區支持強大，出現問題時可以獲得及時的幫助。

三、代碼實操

<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;

/**
 * 城市模型類，表示圖中的節點。
 */
@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 = "權重必須非負")
    private double weight; // 表示距離或其他成本
}

六、運輸數據

package com.example.logistics.model;

import lombok.Data;

import javax.validation.Valid;
import javax.validation.constraints.NotEmpty;
import java.util.List;

/**
 * 運輸數據模型類，包含城市和道路的信息。
 */
@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);
    }
}

九、負責構建和管理圖模型

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;

/**
 * 交通網絡服務類，負責構建和管理圖模型。
 */
@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);
    }

    /**
     * 根據輸入的城市和道路信息構建圖模型。
     *
     * @param cities 城市列表
     * @param roads  道路列表
     */
    public void buildNetwork(List<City> cities, List<Road> roads) {
        logger.info("正在構建包含 {} 個城市和 {} 條道路的交通網絡", 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("重復的城市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());
        }
    }

    /**
     * 獲取當前構建的圖模型。
     *
     * @return 圖模型
     */
    public Graph<City, DefaultWeightedEdge> getGraph() {
        return graph;
    }

    /**
     * 根據城市ID查找城市對象。
     *
     * @param id 城市ID
     * @return 找到的城市對象
     * @throws ResourceNotFoundException 如果找不到對應的城市
     */
    public City findCityById(String id) {
        City city = cityMap.get(id);
        if (city == null) {
            throw new ResourceNotFoundException("未找到ID為 " + id + " 的城市");
        }
        return city;
    }
}

十、使用圖論算法計算最優路徑

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;

/**
 * 路徑優化服務類，使用圖論算法計算最優路徑。
 */
@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）

最小生成樹是指在一個加權無向圖中，選取一些邊組成一棵樹，使得該樹的所有頂點都屬于原圖，并且所有邊都在原圖中，同時這些邊的總權重最小。

Kruskal算法：

(1) 步驟：

將圖中的所有邊按權重從小到大排序。
依次取出每條邊，如果這條邊連接的兩個頂點不在同一個連通分量中，則將這條邊加入最小生成樹中，并合并這兩個連通分量。
重復上述過程直到形成一個包含所有頂點的樹。

(2) 優點: 算法簡單易懂，適合稀疏圖。

(3) 缺點: 對于稠密圖效率較低。

我們使用了JGraphT庫中的DijkstraShortestPath類來計算最短路徑。

2. 最短路徑（Shortest Path）

最短路徑是指在圖中尋找兩點之間的路徑，使得路徑上所有邊的權重之和最小。

Dijkstra算法:

(1) 步驟:

初始化：設置起點的距離為0，其他點的距離為無窮大；初始化優先隊列，將起點放入隊列。
取出隊列中距離最小的頂點u。
更新與u相鄰的所有頂點v的距離，如果通過u到達v的距離比之前記錄的小，則更新距離并將v加入隊列。
重復上述過程直到隊列為空。

(2) 優點: 能夠有效地解決單源最短路徑問題。

(3) 缺點: 不適用于有負權邊的圖。

十一、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;

    /**
     * 構建交通網絡。
     *
     * @param data 包含城市和道路信息的傳輸數據
     * @param bindingResult 綁定結果，用于驗證輸入數據
     * @return 成功響應
     * @throws BadRequestException 如果輸入數據無效
     */
    @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("交通網絡構建成功");
            return ResponseEntity.ok().build();
        } catch (Exception e) {
            logger.error("構建交通網絡時出錯: ", 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 如果找不到對應的源或目標城市
     */
    @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

十四、測試結果

1. 構建交通網絡

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-mst

Respons：

[
    {
        "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/C3

Respons：

{
    "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
        }
    ]
}

責任編輯：趙寧寧來源： Java知識日歷