簡介一套基于Java SpringBoot與GraphHopper庫構(gòu)建的多途徑點(diǎn)路徑規(guī)劃系統(tǒng)源碼面向有一定Java后端基礎(chǔ)、需要實(shí)現(xiàn)物流配送、多點(diǎn)導(dǎo)航或巡檢路線優(yōu)化等場景的開發(fā)者。壓縮包共23個(gè)文件主要包含4個(gè)Java源文件、2個(gè)OSM地圖數(shù)據(jù)文件、Maven構(gòu)建配置pom.xml及mvnw腳本、GraphHopper運(yùn)行所需的索引與圖數(shù)據(jù)文件如nodes、edges、location_index等以及若干配置說明文檔整體約31.72MB。當(dāng)前已有325人學(xué)習(xí)下載。這套源碼完整展示了SpringBoot集成GraphHopper的關(guān)鍵流程從OSM地圖數(shù)據(jù)加載、路網(wǎng)圖構(gòu)建到多途經(jīng)點(diǎn)查詢接口的封裝同時(shí)給出了路徑計(jì)算所需的核心參數(shù)配置與圖數(shù)據(jù)持久化方案。開發(fā)者可直接參考項(xiàng)目結(jié)構(gòu)理解各文件在路徑規(guī)劃鏈路中的具體作用并基于現(xiàn)有代碼擴(kuò)展業(yè)務(wù)邏輯、調(diào)整路徑算法策略或接入新的地圖數(shù)據(jù)源適合作為二次開發(fā)、畢業(yè)設(shè)計(jì)或課程設(shè)計(jì)的基礎(chǔ)工程。1. 多途徑點(diǎn)路徑規(guī)劃不是地圖 API 的活GraphHopper SpringBoot 能自己干接到一個(gè)配送調(diào)度需求某快遞站每天有三十多個(gè)派件點(diǎn)車輛從站點(diǎn)出發(fā)送完所有點(diǎn)再回站之前一直用地圖廠商的路線 API 挨個(gè)算相鄰點(diǎn)耗時(shí)再人工排順序排一次要半小時(shí)高峰時(shí)根本排不過來。我接手后第一反應(yīng)是找路線規(guī)劃 SDK對比了一圈發(fā)現(xiàn)自托管的 GraphHopper 是投入產(chǎn)出比最高的方案——它是純 Java 寫的開源路由引擎能直接嵌進(jìn) SpringBoot 工程吃 OpenStreetMap 格式的道路數(shù)據(jù)本地就能批量算兩點(diǎn)間耗時(shí)多點(diǎn)順序規(guī)劃則是在它提供的耗時(shí)矩陣接口之上再套一層優(yōu)化算法把“先算距離再排順序”兩步徹底自動化。這套東西打通之后排三十個(gè)點(diǎn)的路線從半小時(shí)壓縮到幾秒不用為每次調(diào)度付 API 調(diào)用費(fèi)也沒有外網(wǎng)依賴數(shù)據(jù)全在本地。核心組件只有三個(gè)GraphHopper 負(fù)責(zé)路網(wǎng)圖構(gòu)建和單點(diǎn)路由計(jì)算、SpringBoot 負(fù)責(zé)把引擎包成 HTTP 服務(wù)、TSP 順序優(yōu)化算法負(fù)責(zé)把多途徑點(diǎn)排序。適用對象很明確自建配送調(diào)度、外勤巡檢、農(nóng)機(jī)田間路徑規(guī)劃這類需要批量、反復(fù)計(jì)算多點(diǎn)路線的系統(tǒng)。看完這篇你能把最小可跑的 GraphHopper 服務(wù)嵌進(jìn)自己的 SpringBoot 工程并親手實(shí)現(xiàn)一個(gè)多途徑點(diǎn)順序規(guī)劃接口。2. GraphHopper 選型與數(shù)據(jù)準(zhǔn)備為什么是它而不是別家路由引擎2.1 自托管路由引擎的定位先搞清楚 GraphHopper 能干什么GraphHopper 是一個(gè) Java 實(shí)現(xiàn)的開源路由引擎核心能力有三塊解析道路數(shù)據(jù)、構(gòu)建路網(wǎng)圖、按不同交通方式計(jì)算兩點(diǎn)或多點(diǎn)之間的路線與耗時(shí)。它不是在線服務(wù)而是一個(gè)嵌入式的 Jar 包你的 SpringBoot 進(jìn)程啟動時(shí)調(diào)用它的 API 就能完成路網(wǎng)加載之后每次路由請求都在本地內(nèi)存里計(jì)算不走任何外呼。選它之前我對比過幾種方案。純調(diào)用在線地圖廠商的路線 API 當(dāng)然最省事但多途徑點(diǎn)場景下要反復(fù)調(diào)用批量接口費(fèi)用和配額都是問題而且有些業(yè)務(wù)數(shù)據(jù)不能出內(nèi)網(wǎng)。另一類是自建 OSRM 服務(wù)它性能很強(qiáng)但有獨(dú)立的 C 進(jìn)程和 HTTP 服務(wù)和 Java 工程是兩套體系部署運(yùn)維要多管一個(gè)組件。GraphHopper 和 SpringBoot 是同語言、同進(jìn)程路網(wǎng)和路由邏輯全在一個(gè) JVM 里對單機(jī)幾千點(diǎn)規(guī)模以內(nèi)的業(yè)務(wù)足夠用部署也最簡單。架構(gòu)上它把“路網(wǎng)數(shù)據(jù)文件”和“內(nèi)存中的圖對象”分開處理啟動時(shí)一次性讀取.osm.pbf格式的道路數(shù)據(jù)解析后構(gòu)建十字路口節(jié)點(diǎn)和路段邊組成的圖路由請求時(shí)在這個(gè)圖上做雙向 Dijkstra 或 A* 搜索。這里說的圖是圖論里的圖不是圖片存儲結(jié)構(gòu)和檢索效率直接決定路由耗時(shí)。你的 SpringBoot 服務(wù)里只需持有 GraphHopper 單例所有請求線程共享同一個(gè)圖對象這也是它嵌入式用法高效的原因。2.2 道路數(shù)據(jù)怎么落到本地從 .osm.pbf 到 GraphHopper 圖GraphHopper 要跑起來第一步是準(zhǔn)備道路數(shù)據(jù)。最常見的數(shù)據(jù)格式是.osm.pbf它是 OpenStreetMap 數(shù)據(jù)的二進(jìn)制壓縮格式體積比同內(nèi)容的 XML 小好幾倍解析也更快。國內(nèi)大區(qū)級路網(wǎng)數(shù)據(jù)通常幾百 MB全國級需要幾個(gè) GB不要一上來就想全量加載按業(yè)務(wù)覆蓋范圍裁剪數(shù)據(jù)更務(wù)實(shí)。數(shù)據(jù)來源渠道有幾種但不要下載整個(gè)國家的文件塞進(jìn)內(nèi)存啟動時(shí)構(gòu)建圖會非常慢且吃內(nèi)存。我一般先按城市或省份邊界裁剪用 osmium 這類命令行工具可以把大區(qū)域切成小區(qū)域只保留業(yè)務(wù)涉及的范圍。GraphHopper 雖然自帶數(shù)據(jù)處理工具但裁剪在數(shù)據(jù)準(zhǔn)備階段做更靈活后面改業(yè)務(wù)邊界也不用重新構(gòu)建整個(gè)圖。拿到.osm.pbf后GraphHopper 需要把它“導(dǎo)入”并構(gòu)建成自己的圖存儲格式。運(yùn)行時(shí)配置解析器會讀取道路標(biāo)簽等級、限速、單行道等然后做節(jié)點(diǎn)合并和邊緣計(jì)算。這個(gè)構(gòu)建過程耗時(shí)取決于數(shù)據(jù)量一個(gè)城市級文件通常在幾十秒到幾分鐘區(qū)域級可能要幾個(gè)小時(shí)。構(gòu)建好的圖會寫到本地目錄下次啟動如果目錄存在且數(shù)據(jù)沒變就直接加載序列化后的圖啟動時(shí)間從幾分鐘降到幾秒。2.3 圖構(gòu)建的三個(gè)核心參數(shù)圖存儲目錄、交通方式、內(nèi)存映射模式GraphHopper 的初始化參數(shù)直接決定內(nèi)存占用和路由準(zhǔn)確性。第一個(gè)是圖存儲目錄指定后引擎會把構(gòu)建好的圖落盤重啟不用重新解析原始道路數(shù)據(jù)。第二個(gè)是交通方式GraphHopper 的每種交通方式對應(yīng)一套道路可走性與速度配置汽車模式跳過步行道、走機(jī)動車道步行模式則是另一套規(guī)則選錯(cuò)模式會導(dǎo)致路線完全不同。內(nèi)存映射有兩種模式RAM_STORE把整個(gè)圖載入堆外內(nèi)存路由最快但數(shù)據(jù)量大時(shí)占用偏高M(jìn)MAP是內(nèi)存映射文件按需加載適合圖較大而內(nèi)存有限的環(huán)境。單機(jī)并發(fā)不高、圖在 500 MB 以內(nèi)用 RAM_STORE圖超過 1 GBMMAP 更穩(wěn)妥能省下大量內(nèi)存。我通常會關(guān)閉CHContraction Hierarchies預(yù)處理——預(yù)計(jì)算會讓單點(diǎn)路由快一個(gè)數(shù)量級但對多途徑點(diǎn)的矩陣批量計(jì)算場景CH 加速效果并不明顯反而增加構(gòu)建時(shí)間和內(nèi)存。多途徑點(diǎn)規(guī)劃的核心是頻繁調(diào)用路徑替代算法算矩陣用不帶 CH 的普通圖更直接?？匆幌碌湫偷某跏蓟渲么a在用 SpringBoot 之前先在獨(dú)立方法里驗(yàn)證參數(shù)是否合理// 初始化 GraphHopper 引擎核心配置項(xiàng) public GraphHopper initGraphHopper() { GraphHopper hopper new GraphHopper(); // 數(shù)據(jù)目錄存放 .osm.pbf 原始數(shù)據(jù) hopper.setOSMFile(/data/osm/beijing-latest.osm.pbf); // 圖存儲目錄構(gòu)建后的圖落盤位置 hopper.setGraphHopperLocation(/data/graph-cache/beijing); // 編碼方式支持汽車、步行等多種方式逗號分隔 hopper.setEncodedValuesString(car,foot); // 內(nèi)存映射模式有 RAM_STORE 和 MMAP 兩種可選 hopper.setMemoryMapped(false); // 不啟用 CH 預(yù)處理降低構(gòu)建開銷 hopper.setCHEnabled(false); hopper.importOrLoad(); return hopper; }代碼里setEncodedValuesString定義圖里預(yù)計(jì)算哪些編碼屬性car 和 foot 是兩種最常見的編碼方式對應(yīng)不同道路通行能力。importOrLoad()是關(guān)鍵方法數(shù)據(jù)沒導(dǎo)入過就執(zhí)行導(dǎo)入并保存導(dǎo)入過就直接加載。這個(gè)過程會打印詳細(xì)的日志第一次運(yùn)行觀察日志里的導(dǎo)入進(jìn)度和耗時(shí)能幫你判斷數(shù)據(jù)量級是否匹配當(dāng)前機(jī)器配置。3. SpringBoot 里把 GraphHopper 跑起來從配置類到可調(diào)用的路由接口3.1 依賴與 Bean 初始化讓引擎隨應(yīng)用生命周期啟動SpringBoot 工程引入 GraphHopper 很簡單核心就一個(gè)依賴com.graphhopper:graphhopper-core。版本要和你下載的源碼對應(yīng)這一點(diǎn)容易翻車GraphHopper 的 Java 版本要求偏高JDK 8 在較新版本上會直接運(yùn)行失敗建議 JDK 11 或 17。另一個(gè)隱蔽問題GraphHopper 依賴了若干第三方庫如果你的工程里也用了低版本沖突庫會出現(xiàn)NoSuchMethodError啟動時(shí)注意看異常棧優(yōu)先調(diào)整 GraphHopper 傳遞依賴的版本即可。Bean 初始化上用Configuration定義一個(gè)GraphHopper單例Bean(initMethod importOrLoad)讓它隨 Spring 容器啟動自動完成圖加載。不要每次請求都 new 一個(gè) GraphHopper那等于每次重新加載路網(wǎng)內(nèi)存會爆。下面是標(biāo)準(zhǔn)的初始化配置類Configuration public class GraphHopperConfig { Value(${graphhopper.osm-file}) private String osmFile; Value(${graphhopper.graph-location}) private String graphLocation; Bean(initMethod importOrLoad, destroyMethod close) public GraphHopper graphHopper() { GraphHopper hopper new GraphHopper(); hopper.setOSMFile(osmFile); hopper.setGraphHopperLocation(graphLocation); hopper.setEncodedValuesString(car); hopper.setMemoryMapped(true); hopper.setCHEnabled(false); return hopper; } }配置項(xiàng)被拆分到了application.yml便于不同環(huán)境切換數(shù)據(jù)目錄。注意destroyMethod close應(yīng)用停機(jī)時(shí)釋放底層文件句柄和內(nèi)存映射資源反復(fù)重啟部署時(shí)不會出現(xiàn)文件鎖問題。setMemoryMapped(true)對大圖更友好但首次路由請求會偏慢因?yàn)轫撁鏀?shù)據(jù)是懶加載的預(yù)熱一次就好。啟動后日志里如果出現(xiàn)Using memory mapped files和Finished loading graph說明圖加載成功。之后所有線程共享該單例路由計(jì)算是并發(fā)的但引擎內(nèi)部對圖讀取做了線程安全處理不需要額外加鎖。3.2 封裝單點(diǎn)路由計(jì)算從經(jīng)緯度到路線詳情最基礎(chǔ)的能力是兩個(gè)經(jīng)緯度之間的路線。調(diào)用GraphHopper是GHRequest/GHResponse模式創(chuàng)建請求、設(shè)置起終點(diǎn)經(jīng)緯度、指定編碼方式、發(fā)送到引擎然后檢查響應(yīng)是否有異常。這里有一個(gè)最容易忽視的坐標(biāo)順序問題GraphHopper 的 API 統(tǒng)一是緯度在前、經(jīng)度在后也就是(lat, lon)和國內(nèi)很多系統(tǒng)習(xí)慣的(lng, lat)正好相反。我封裝的服務(wù)類接收業(yè)務(wù)側(cè)的(lng, lat)在進(jìn)入 GraphHopper 之前轉(zhuǎn)成(lat, lng)避免調(diào)用方因?yàn)樽鴺?biāo)順序搞混而返回完全離譜的路線。完整代碼Service public class RouteService { private final GraphHopper graphHopper; public RouteService(GraphHopper graphHopper) { this.graphHopper graphHopper; } public RouteResult route(double fromLng, double fromLat, double toLng, double toLat) { // GraphHopper 使用緯度在前經(jīng)度在后的順序 GHRequest request new GHRequest(fromLat, fromLng, toLat, toLng); request.setProfile(car); // 限制搜索范圍避免歧義點(diǎn)導(dǎo)致路由繞遠(yuǎn) request.setHint(ch.disable, true); GHResponse response graphHopper.route(request); if (response.hasErrors()) { String errorMsg response.getErrors().toString(); throw new IllegalStateException(路由計(jì)算失敗: errorMsg); } ResponsePath path response.getBest(); return new RouteResult(path.getDistance(), path.getTime(), path.getPoints().toLineString(false).toString()); } }setProfile(car)指定用哪種編碼方式必須是在初始化時(shí)setEncodedValuesString里聲明過的否則拋異常。path.getPoints().toLineString(false)把軌跡點(diǎn)序列轉(zhuǎn)成 WKT 格式的 LineString 字符串前端地圖直接按這個(gè)串繪制路徑省去自行序列化的麻煩。getDistance()返回的是米getTime()返回的是毫秒兩個(gè)值后續(xù)計(jì)算矩陣時(shí)都要用到。這個(gè)接口本身不復(fù)雜但它驗(yàn)證了整個(gè) SpringBoot 集成鏈路是否通——配置類有沒有加載、坐標(biāo)轉(zhuǎn)換有沒有問題、GraphHopper 能不能算出路線。集成新引擎時(shí)務(wù)必要先把單點(diǎn)路由跑通再談多途徑點(diǎn)。3.3 距離矩陣計(jì)算多途徑點(diǎn)規(guī)劃的數(shù)據(jù)底座單點(diǎn)路由只能解決 A 到 B多途徑點(diǎn)規(guī)劃需要知道任意兩點(diǎn)之間的耗時(shí)于是 GraphHopper 的矩陣計(jì)算接口就該登場了。它避免你寫雙層循環(huán)逐個(gè)調(diào)用單點(diǎn)路由——一次請求算出所有點(diǎn)對之間的耗時(shí)和距離內(nèi)部會做批量優(yōu)化耗時(shí)只有逐個(gè)調(diào)用的幾分之一。GraphHopper 矩陣 API 要構(gòu)建一個(gè)MatrixRequest設(shè)置所有點(diǎn)的經(jīng)緯度、編碼方式然后執(zhí)行。返回的矩陣是二維數(shù)組下標(biāo)與原數(shù)組一一對應(yīng)。這里要注意MatrixRequest不是GHRequest它在底層會復(fù)用團(tuán)簇算法對區(qū)域內(nèi)的點(diǎn)做批量計(jì)算所以如果業(yè)務(wù)上確實(shí)只需要某幾個(gè)點(diǎn)之間的兩兩耗時(shí)用矩陣接口比循環(huán)單點(diǎn)路由合適得多。public long[][] getTimeMatrix(ListPoint points) { ListGHPoint ghPoints points.stream() .map(p - new GHPoint(p.getLat(), p.getLng())) .collect(Collectors.toList()); MatrixRequest matrixRequest new MatrixRequest(); matrixRequest.setPoints(ghPoints); matrixRequest.setProfile(car); // 只需要耗時(shí)數(shù)據(jù)不返回路徑幾何形狀降低傳輸和計(jì)算開銷 matrixRequest.setOutArrays(Arrays.asList(time, distance)); matrixRequest.setFailFast(false); MatrixResponse matrixResponse graphHopper.matrix(matrixRequest); long[][] result new long[ghPoints.size()][ghPoints.size()]; for (int row 0; row matrixResponse.getTimes().length; row) { // 逐行拷貝耗時(shí)矩陣行下標(biāo)是起點(diǎn)列下標(biāo)是終點(diǎn) result[row] matrixResponse.getTimes()[row]; } return result; }setOutArrays只聲明time和distance別再加weight這類內(nèi)部字段多了白白增加計(jì)算量。setFailFast(false)很關(guān)鍵矩陣中只要有一個(gè)點(diǎn)無法到達(dá)整個(gè)請求會直接失敗把它關(guān)掉后能拿到部分結(jié)果哪些點(diǎn)不可達(dá)在響應(yīng)里標(biāo)記出來方便業(yè)務(wù)層單獨(dú)處理異常點(diǎn)。矩陣結(jié)果保存在內(nèi)存中幾十個(gè)點(diǎn)時(shí)就是一個(gè)N x N的二維數(shù)組后續(xù)順序優(yōu)化算法直接基于這個(gè)矩陣運(yùn)算不再碰 GraphHopper。4. 多途徑點(diǎn)順序規(guī)劃耗時(shí)矩陣 最近鄰 2-opt 是性價(jià)比最高的組合4.1 把多點(diǎn)問題拆成 TSP為什么要先算矩陣再排順序、不能直接在圖上搜索明確了矩陣接口之后核心問題浮現(xiàn)給三十個(gè)派件點(diǎn)和一個(gè)起點(diǎn)怎么決定先送哪個(gè)、后送哪個(gè)路線規(guī)劃問題的本質(zhì)是旅行商問題TSP——找一個(gè)經(jīng)過所有點(diǎn)且總耗時(shí)最短的順序。注意這不是在地圖圖上做一次簡單搜索能解決的因?yàn)樾枰?jīng)過的點(diǎn)有多個(gè)而且順序未知搜索空間是排列組合級別的。圖搜索如 A*只能解決“從 A 到 B 的最短路徑”解決不了“經(jīng)過 A、B、C、D 并以 E 結(jié)束的最短路徑順序”。TSP 的解法分精確算法和啟發(fā)式算法。精確算法如動態(tài)規(guī)劃 Held-Karp在 20 個(gè)點(diǎn)左右就開始吃力幾十上百點(diǎn)的場景完全不可用。實(shí)際工程里貪心最近鄰給出一個(gè)不錯(cuò)的基礎(chǔ)解再用 2-opt 局部搜索優(yōu)化這種組合在幾十點(diǎn)規(guī)模下能跑到接近最優(yōu)耗時(shí)也短是性價(jià)比最高的方案。更復(fù)雜的模擬退火和遺傳算法在這個(gè)規(guī)模下收益有限反而讓代碼復(fù)雜度和調(diào)參成本大幅上升。業(yè)務(wù)上還要考慮起點(diǎn)和終點(diǎn)的約束。最常見場景是“從站點(diǎn)出發(fā)送完所有點(diǎn)再回站點(diǎn)”這是一個(gè)閉合 TSP起點(diǎn)和終點(diǎn)都是站點(diǎn)本身另一種是“不回站點(diǎn)送完就地收工”這就是路徑 TSP。約束不同算法里的矩陣取值方式就不同——閉合 TSP 在計(jì)算總耗時(shí)時(shí)要加上“最后一個(gè)點(diǎn)回到起點(diǎn)”的耗時(shí)。4.2 先用最近鄰快速生成初始順序幾分鐘的高質(zhì)量可行解最近鄰的思路很樸素從起點(diǎn)出發(fā)每次選擇離當(dāng)前點(diǎn)耗時(shí)最短的下一個(gè)未訪問點(diǎn)走完所有點(diǎn)后得到一條路徑。它本質(zhì)是貪心策略單次運(yùn)行結(jié)果是確定的執(zhí)行時(shí)間只有幾毫秒到幾十毫秒取決于點(diǎn)數(shù)解的質(zhì)量通常不超過最優(yōu)解的 20% 偏差作為 2-opt 的初始解完全夠用。關(guān)鍵點(diǎn)在于矩陣的構(gòu)建方式——我們需要拿到任意兩點(diǎn)之間通過路網(wǎng)的真實(shí)驅(qū)動耗時(shí)而不是直線距離。這就是第 3 章里矩陣接口的價(jià)值把三十個(gè)點(diǎn)的經(jīng)緯度一次性傳入GraphHopper 返回兩兩之間的駕駛耗時(shí)這個(gè)耗時(shí)已經(jīng)考慮了路網(wǎng)、紅綠燈和道路等級比歐氏距離靠譜得多。最近鄰算法實(shí)現(xiàn)如下public ListInteger nearestNeighbor(int startIndex, long[][] timeMatrix) { int n timeMatrix.length; boolean[] visited new boolean[n]; ListInteger route new ArrayList(); int current startIndex; route.add(current); visited[current] true; while (route.size() n) { int next -1; long minTime Long.MAX_VALUE; for (int i 0; i n; i) { if (!visited[i] timeMatrix[current][i] minTime) { minTime timeMatrix[current][i]; next i; } } if (next -1) { // 剩余的節(jié)點(diǎn)不可達(dá)直接退出并保留部分路徑 break; } route.add(next); visited[next] true; current next; } return route; }timeMatrix[current][i]的語義是“從當(dāng)前節(jié)點(diǎn)到節(jié)點(diǎn) i 的耗時(shí)”所以貪心選擇時(shí)只需要掃描當(dāng)前行。startIndex是起點(diǎn)在矩陣中的下標(biāo)需要在矩陣接口調(diào)用前維護(hù)好“原始點(diǎn)列表”和“下標(biāo)”的對應(yīng)關(guān)系規(guī)劃完成后按這個(gè)關(guān)系把下標(biāo)翻譯成真實(shí)的經(jīng)緯度點(diǎn)即可。不可達(dá)點(diǎn)時(shí)直接 break 是因?yàn)閒ailFast(false)之后矩陣?yán)飼蠰ong.MAX_VALUE繼續(xù)循環(huán)只會卡死不如提前結(jié)束并把這個(gè)情況上報(bào)給業(yè)務(wù)層。4.3 2-opt 局部搜索用兩兩交換把路徑磨到接近最優(yōu)最近鄰得到一個(gè)初始解但問題很明顯貪心的短視行為經(jīng)常導(dǎo)致某條路走了回頭路或者繞了一個(gè)大圈。2-opt 的思想是取當(dāng)前路徑中的兩條邊斷開后反向連接重排如果新路徑的總耗時(shí)更小就采納。反復(fù)執(zhí)行直到?jīng)]有可以改進(jìn)的交換為止收斂之后路徑基本定型。2-opt 最核心的改進(jìn)點(diǎn)是“倒序”操作?？串?dāng)前路徑序列如果交換位置i和j之間的路徑段需要把這段倒過來而不是簡單換兩個(gè)節(jié)點(diǎn)——因?yàn)槁窂街心扯蔚姆较驔Q定了車輛實(shí)際走的道路方向。用路網(wǎng)耗時(shí)矩陣檢查倒序前后的總耗時(shí)保留更優(yōu)的那個(gè)。2-opt 嵌入實(shí)現(xiàn)public ListInteger twoOpt(ListInteger route, long[][] timeMatrix) { ListInteger best new ArrayList(route); long bestTime calculateTotalTime(best, timeMatrix); boolean improved true; while (improved) { improved false; for (int i 1; i best.size() - 1; i) { for (int j i 1; j best.size(); j) { ListInteger candidate twoOptSwap(best, i, j); long candidateTime calculateTotalTime(candidate, timeMatrix); if (candidateTime bestTime) { best candidate; bestTime candidateTime; improved true; } } } } return best; }twoOptSwap把[i, j]這段反轉(zhuǎn)后重新拼接實(shí)現(xiàn)方式很常規(guī)前半段保留中間段倒序后半段保留。calculateTotalTime按順序遍歷路徑累加相鄰節(jié)點(diǎn)耗時(shí)如果路徑是閉合 TSP還要把最后一個(gè)點(diǎn)和第一個(gè)點(diǎn)的耗時(shí)也加進(jìn)去——這是調(diào)參時(shí)最容易漏掉的一塊。2-opt 的單輪時(shí)間復(fù)雜度是 O(n2)加上外層循環(huán)在 30 個(gè)點(diǎn)的規(guī)模下通常是幾十毫秒級的完全夠用。它做不了全局最優(yōu)但能保證解質(zhì)量在 5% 偏差以內(nèi)對絕大多數(shù)配送調(diào)度場景綽綽有余。4.4 多途徑點(diǎn)接口落地把矩陣和優(yōu)化算法串成一個(gè) HTTP 接口整個(gè)流程串到 SpringBoot 里對外暴露一個(gè) HTTP 接口接收一組經(jīng)緯度點(diǎn)返回排序后的路線。這里我增加了一個(gè)“強(qiáng)制回起點(diǎn)”開關(guān)因?yàn)楹芏鄻I(yè)務(wù)場景是車輛出去必須回站點(diǎn)也有場景是送完就地下班兩種需求用一個(gè)開關(guān)控制算法實(shí)現(xiàn)上只在總耗時(shí)計(jì)算時(shí)多加/少加一條回到起點(diǎn)的邊。接口設(shè)計(jì)考慮了批量規(guī)劃場景的調(diào)用方式一次傳入所有點(diǎn)服務(wù)端同步計(jì)算返回帶有順序標(biāo)記的路線列表。由于矩陣計(jì)算和 2-opt 都在內(nèi)存里跑幾十點(diǎn)級別的接口響應(yīng)時(shí)間通常在數(shù)百毫秒足夠交互式使用。RestController RequestMapping(/api/route) public class MultiPointRouteController { private final RoutePlanningService planningService; public MultiPointRouteController(RoutePlanningService planningService) { this.planningService planningService; } /** * 多途徑點(diǎn)路徑規(guī)劃接口 * param points 起點(diǎn) 途徑點(diǎn)列表 * param returnToStart 是否返回起點(diǎn) */ PostMapping(/plan) public PlanResult plan(RequestBody PlanRequest request) { ListPoint points request.getPoints(); boolean returnToStart request.isReturnToStart(); return planningService.planOrder(points, returnToStart); } }RoutePlanningService.planOrder內(nèi)部依次執(zhí)行轉(zhuǎn)換 GHPoint 列表、調(diào)用矩陣接口、最近鄰生成初始順序、2-opt 優(yōu)化、把下標(biāo)翻譯成經(jīng)緯度、計(jì)算總耗時(shí)。整個(gè)流程把 GraphHopper 引擎、矩陣接口和 TSP 算法串成一個(gè)業(yè)務(wù)閉環(huán)。服務(wù)層接口返回值里包含排序后的點(diǎn)列表、每段路線耗時(shí)和總耗時(shí)業(yè)務(wù)方可以直接按這個(gè)結(jié)果生成調(diào)度單或?qū)Ш铰肪€。planOrder 核心流程拆解步驟操作數(shù)據(jù)來源1轉(zhuǎn)換坐標(biāo)點(diǎn)lng/lat 轉(zhuǎn) lat/lng請求參數(shù)2構(gòu)建耗時(shí)矩陣GraphHopper Matrix API3最近鄰生成初始順序耗時(shí)矩陣42-opt 優(yōu)化順序初始順序 耗時(shí)矩陣5翻譯下標(biāo) → 經(jīng)緯度原始點(diǎn)列表6計(jì)算總耗時(shí)、返回結(jié)果優(yōu)化后順序你會發(fā)現(xiàn)真正的規(guī)劃邏輯并不在 GraphHopper 里而是發(fā)生在這個(gè)服務(wù)類中。GraphHopper 只負(fù)責(zé)回答“這兩點(diǎn)之間開車多久”順序怎么排是你自己的 TSP 算法說了算。5. 避坑GraphHopper 集成里最常見的 5 個(gè)翻車點(diǎn)5.1 坐標(biāo)順序搞反路線全部橫穿地圖現(xiàn)象從北京到天津的路線算出來橫跨了中國版圖或者路線自動繞了上千公里。原因GraphHopper 的 GHPoint 構(gòu)造器明確是(lat, lon)很多業(yè)務(wù)系統(tǒng)主鍵存的是(lng, lat)直接反轉(zhuǎn)傳入后本應(yīng)向北的路變成了往東圖搜索完全錯(cuò)亂。解決在進(jìn)入引擎之前統(tǒng)一做一次坐標(biāo)轉(zhuǎn)換并且寫單元測試鎖定給定已知經(jīng)緯度的 A/B 兩點(diǎn)驗(yàn)證計(jì)算出的距離在合理范圍內(nèi)。我吃過一次虧之后在這個(gè)轉(zhuǎn)換方法里加了強(qiáng)校驗(yàn)——如果緯度超過 90 或者經(jīng)度超過 180直接拋異常寧可開發(fā)期炸掉也不要線上錯(cuò)。5.2 道路數(shù)據(jù)精度不夠壓根搜不到點(diǎn)現(xiàn)象某幾個(gè)點(diǎn)報(bào)Could not find point但經(jīng)緯度看著明明在市區(qū)。原因.osm.pbf 數(shù)據(jù)的精度和詳細(xì)程度取決于數(shù)據(jù)源本身。有些區(qū)域道路缺失或斷頭路太多GraphHopper 在圖上找最近的可行走邊失敗就會報(bào)點(diǎn)不可達(dá)。這種情況在郊區(qū)、新建開發(fā)區(qū)特別常見。解決先把點(diǎn)投影到圖上查看GraphHopper返回的最近邊和投影點(diǎn)確認(rèn)是否有道路數(shù)據(jù)如果有路但斷頭則手動補(bǔ)錄幾條道路或者調(diào)整點(diǎn)坐標(biāo)到實(shí)際道路位置。工程上給業(yè)務(wù)方提供一個(gè)“地圖選址”功能讓他們在地圖上選點(diǎn)而不是填坐標(biāo)能從源頭規(guī)避這個(gè)坑。5.3 強(qiáng)制回起點(diǎn)時(shí)總耗時(shí)少算一段現(xiàn)象接口返回的總耗時(shí)明顯偏短對比實(shí)際跑下來的時(shí)間差了將近半小時(shí)。原因閉合 TSP 要求“最后一個(gè)點(diǎn)回起點(diǎn)”這一段路的耗時(shí)也要計(jì)入總和但實(shí)現(xiàn)里只算了路徑內(nèi)部相鄰點(diǎn)的耗時(shí)少了最后一段返程。這個(gè)在代碼 review 階段特別容易漏因?yàn)榭雌饋砺窂揭呀?jīng)“結(jié)束”了。解決在calculateTotalTime方法里增加一個(gè)布爾參數(shù)returnToStart閉合時(shí)把timeMatrix[last][first]加上。同時(shí)接口返回的明細(xì)里單獨(dú)列出一個(gè)“返程耗時(shí)”字段讓業(yè)務(wù)方能看出這半小時(shí)是怎么來的。5.4 CH 預(yù)計(jì)算打開導(dǎo)致啟動極慢、內(nèi)存吃緊現(xiàn)象啟動時(shí)構(gòu)建圖明顯變慢日志顯示 CH preprocessing 卡了很久內(nèi)存占用翻倍。原因和第 2 章說的一樣CH 預(yù)計(jì)算會為每個(gè)節(jié)點(diǎn)算跳表構(gòu)建時(shí)間和內(nèi)存開銷都很高。多途徑點(diǎn)場景下主要調(diào)矩陣接口單次路由用的不多CH 收益有限但它造成的構(gòu)建負(fù)擔(dān)是實(shí)打?qū)嵉摹＝鉀Q初始化配置關(guān)掉 CHhopper.setCHEnabled(false)。如果確實(shí)有個(gè)別高并發(fā)單點(diǎn)路由需求可以單獨(dú)為那個(gè)接口準(zhǔn)備一個(gè)帶 CH 的引擎實(shí)例兩個(gè)引擎共享同一份圖數(shù)據(jù)目錄互不干擾。5.5 內(nèi)存映射模式下首次請求特別慢現(xiàn)象服務(wù)啟動后第一個(gè)路由請求要等好幾秒甚至幾十秒后面的請求就正常了。原因MMAP 模式下圖數(shù)據(jù)是懶加載到內(nèi)存的哪條路被搜索到了才把那部分?jǐn)?shù)據(jù)頁加載進(jìn)來。首次請求覆蓋的路段多相當(dāng)于把所有道路數(shù)據(jù)都觸達(dá)了一遍自然慢。解決應(yīng)用啟動后做一次“預(yù)熱”調(diào)用隨便算一條短線路讓底層把常用圖頁加載完?；蛘咧苯佑肦AM_STORE模式啟動時(shí)全部載入第一次請求和后面一樣快。內(nèi)存夠的話優(yōu)先 RAM_STORE省心。6. 進(jìn)階加一個(gè)“一鍵優(yōu)化”按鈕前先搞懂這些技巧多途徑點(diǎn)規(guī)劃從能跑到好用中間還有幾個(gè)提升體驗(yàn)的小改動。第一個(gè)是把 2-opt 的迭代上限露出來。當(dāng)途徑點(diǎn)數(shù)超過五十個(gè)時(shí)完全收斂可能要幾十輪而實(shí)際業(yè)務(wù)里 2-opt 前幾輪效果最明顯后面幾輪收益很小。我習(xí)慣設(shè)置一個(gè)最大迭代次數(shù)比如 5 輪配合improved標(biāo)志位耗時(shí)可控解質(zhì)量也只有百分之幾的差距。第二個(gè)技巧是復(fù)用矩陣計(jì)算結(jié)果。同一個(gè)小區(qū)的多個(gè)配送點(diǎn)耗時(shí)矩陣可能長時(shí)間不變而 GraphHopper 的矩陣計(jì)算是有成本的尤其點(diǎn)多的情況下。如果你的輸入點(diǎn)集相對固定把矩陣結(jié)果緩存起來點(diǎn)集變化時(shí)才重新計(jì)算?？梢杂煤唵蔚腃oncurrentHashMap加一個(gè)版本號來實(shí)現(xiàn)點(diǎn)在緩存里就直接跳到 TSP 優(yōu)化階段。第三個(gè)技巧是異步化長任務(wù)。五十個(gè)點(diǎn)以上的規(guī)劃矩陣計(jì)算加 2-opt 可能要幾秒同步阻塞 HTTP 請求會讓前端一直轉(zhuǎn)圈。一個(gè)老板鍵做法接口先返回任務(wù) ID后端用線程池執(zhí)行規(guī)劃完成后把結(jié)果寫到內(nèi)存緩存前端輪詢拿結(jié)果。這和直接用同步接口相比用戶體驗(yàn)差別明顯。車輛容量約束是另一個(gè)常見擴(kuò)展方向。目前算法只優(yōu)化耗時(shí)不關(guān)心車能不能裝下所有貨。如果你的業(yè)務(wù)里每輛車有載重上限那這就從 TSP 變成了 CVRP帶容量約束的車輛路徑問題需要在排順序時(shí)同時(shí)檢查已分配點(diǎn)的累計(jì)重量。最簡單的做法是分桶——按順序貪心塞進(jìn)多輛車每輛車滿負(fù)荷后開下一輛再用 2-opt 分別優(yōu)化每輛車的順序。我做這套系統(tǒng)的過程中最耗時(shí)的不是算法本身而是把坐標(biāo)順序、數(shù)據(jù)精度、返程耗時(shí)這些細(xì)節(jié)打磨對。這些坑不填掉再快的最優(yōu)算法都給不了業(yè)務(wù)可用的結(jié)果。規(guī)劃接口上線之后配送員的實(shí)際行駛距離和我算出來的路線差距穩(wěn)定在 10% 以內(nèi)——說明路網(wǎng)速度假設(shè)和實(shí)際匹配良好。后續(xù)如果你遇到“某些點(diǎn)搜不到”“總耗時(shí)不對”“啟動慢得離譜”這類問題按第 5 章的排查順序過一遍大多數(shù)能直接解決。如果你要更大規(guī)模的點(diǎn)集上千個(gè)點(diǎn)那種建議改用專門的 VROOM 和 jsprit 這類開源求解器配合 GraphHopper 做路網(wǎng)前處理依然能把整套鏈路留在自己的工程里。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取