簡(jiǎn)介一套基于Java SpringBoot與GraphHopper庫(kù)構(gòu)建的多途徑點(diǎn)路徑規(guī)劃系統(tǒng)源碼面向有一定Java后端基礎(chǔ)、需要實(shí)現(xiàn)物流配送、多點(diǎn)導(dǎo)航或巡檢路線優(yōu)化等場(chǎng)景的開(kāi)發(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等以及若干配置說(shuō)明文檔整體約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ù)持久化方案。開(kāi)發(fā)者可直接參考項(xiàng)目結(jié)構(gòu)理解各文件在路徑規(guī)劃鏈路中的具體作用并基于現(xiàn)有代碼擴(kuò)展業(yè)務(wù)邏輯、調(diào)整路徑算法策略或接入新的地圖數(shù)據(jù)源適合作為二次開(kāi)發(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í)根本排不過(guò)來(lái)。我接手后第一反應(yīng)是找路線規(guī)劃 SDK對(duì)比了一圈發(fā)現(xiàn)自托管的 GraphHopper 是投入產(chǎn)出比最高的方案——它是純 Java 寫的開(kāi)源路由引擎能直接嵌進(jìn) SpringBoot 工程吃 OpenStreetMap 格式的道路數(shù)據(jù)本地就能批量算兩點(diǎn)間耗時(shí)多點(diǎn)順序規(guī)劃則是在它提供的耗時(shí)矩陣接口之上再套一層優(yōu)化算法把“先算距離再排順序”兩步徹底自動(dòng)化。這套東西打通之后排三十個(gè)點(diǎn)的路線從半小時(shí)壓縮到幾秒不用為每次調(diào)度付 API 調(diào)用費(fèi)也沒(mé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)排序。適用對(duì)象很明確自建配送調(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)的開(kāi)源路由引擎核心能力有三塊解析道路數(shù)據(jù)、構(gòu)建路網(wǎng)圖、按不同交通方式計(jì)算兩點(diǎn)或多點(diǎn)之間的路線與耗時(shí)。它不是在線服務(wù)而是一個(gè)嵌入式的 Jar 包你的 SpringBoot 進(jìn)程啟動(dòng)時(shí)調(diào)用它的 API 就能完成路網(wǎng)加載之后每次路由請(qǐng)求都在本地內(nèi)存里計(jì)算不走任何外呼。選它之前我對(duì)比過(guò)幾種方案。純調(diào)用在線地圖廠商的路線 API 當(dāng)然最省事但多途徑點(diǎn)場(chǎng)景下要反復(fù)調(diào)用批量接口費(fèi)用和配額都是問(wèn)題而且有些業(yè)務(wù)數(shù)據(jù)不能出內(nèi)網(wǎng)。另一類是自建 OSRM 服務(wù)它性能很強(qiáng)但有獨(dú)立的 C 進(jìn)程和 HTTP 服務(wù)和 Java 工程是兩套體系部署運(yùn)維要多管一個(gè)組件。GraphHopper 和 SpringBoot 是同語(yǔ)言、同進(jìn)程路網(wǎng)和路由邏輯全在一個(gè) JVM 里對(duì)單機(jī)幾千點(diǎn)規(guī)模以內(nèi)的業(yè)務(wù)足夠用部署也最簡(jiǎn)單。架構(gòu)上它把“路網(wǎng)數(shù)據(jù)文件”和“內(nèi)存中的圖對(duì)象”分開(kāi)處理啟動(dòng)時(shí)一次性讀取.osm.pbf格式的道路數(shù)據(jù)解析后構(gòu)建十字路口節(jié)點(diǎn)和路段邊組成的圖路由請(qǐng)求時(shí)在這個(gè)圖上做雙向 Dijkstra 或 A* 搜索。這里說(shuō)的圖是圖論里的圖不是圖片存儲(chǔ)結(jié)構(gòu)和檢索效率直接決定路由耗時(shí)。你的 SpringBoot 服務(wù)里只需持有 GraphHopper 單例所有請(qǐng)求線程共享同一個(gè)圖對(duì)象這也是它嵌入式用法高效的原因。2.2 道路數(shù)據(jù)怎么落到本地從 .osm.pbf 到 GraphHopper 圖GraphHopper 要跑起來(lái)第一步是準(zhǔn)備道路數(shù)據(jù)。最常見(jiàn)的數(shù)據(jù)格式是.osm.pbf它是 OpenStreetMap 數(shù)據(jù)的二進(jìn)制壓縮格式體積比同內(nèi)容的 XML 小好幾倍解析也更快。國(guó)內(nèi)大區(qū)級(jí)路網(wǎng)數(shù)據(jù)通常幾百 MB全國(guó)級(jí)需要幾個(gè) GB不要一上來(lái)就想全量加載按業(yè)務(wù)覆蓋范圍裁剪數(shù)據(jù)更務(wù)實(shí)。數(shù)據(jù)來(lái)源渠道有幾種但不要下載整個(gè)國(guó)家的文件塞進(jìn)內(nèi)存啟動(dòng)時(shí)構(gòu)建圖會(huì)非常慢且吃內(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)建成自己的圖存儲(chǔ)格式。運(yùn)行時(shí)配置解析器會(huì)讀取道路標(biāo)簽等級(jí)、限速、單行道等然后做節(jié)點(diǎn)合并和邊緣計(jì)算。這個(gè)構(gòu)建過(guò)程耗時(shí)取決于數(shù)據(jù)量一個(gè)城市級(jí)文件通常在幾十秒到幾分鐘區(qū)域級(jí)可能要幾個(gè)小時(shí)。構(gòu)建好的圖會(huì)寫到本地目錄下次啟動(dòng)如果目錄存在且數(shù)據(jù)沒(méi)變就直接加載序列化后的圖啟動(dòng)時(shí)間從幾分鐘降到幾秒。2.3 圖構(gòu)建的三個(gè)核心參數(shù)圖存儲(chǔ)目錄、交通方式、內(nèi)存映射模式GraphHopper 的初始化參數(shù)直接決定內(nèi)存占用和路由準(zhǔn)確性。第一個(gè)是圖存儲(chǔ)目錄指定后引擎會(huì)把構(gòu)建好的圖落盤重啟不用重新解析原始道路數(shù)據(jù)。第二個(gè)是交通方式GraphHopper 的每種交通方式對(duì)應(yīng)一套道路可走性與速度配置汽車模式跳過(guò)步行道、走機(jī)動(dòng)車道步行模式則是另一套規(guī)則選錯(cuò)模式會(huì)導(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圖超過(guò) 1 GBMMAP 更穩(wěn)妥能省下大量?jī)?nèi)存。我通常會(huì)關(guān)閉CHContraction Hierarchies預(yù)處理——預(yù)計(jì)算會(huì)讓單點(diǎn)路由快一個(gè)數(shù)量級(jí)但對(duì)多途徑點(diǎn)的矩陣批量計(jì)算場(chǎng)景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); // 圖存儲(chǔ)目錄構(gòu)建后的圖落盤位置 hopper.setGraphHopperLocation(/data/graph-cache/beijing); // 編碼方式支持汽車、步行等多種方式逗號(hào)分隔 hopper.setEncodedValuesString(car,foot); // 內(nèi)存映射模式有 RAM_STORE 和 MMAP 兩種可選 hopper.setMemoryMapped(false); // 不啟用 CH 預(yù)處理降低構(gòu)建開(kāi)銷 hopper.setCHEnabled(false); hopper.importOrLoad(); return hopper; }代碼里setEncodedValuesString定義圖里預(yù)計(jì)算哪些編碼屬性car 和 foot 是兩種最常見(jiàn)的編碼方式對(duì)應(yīng)不同道路通行能力。importOrLoad()是關(guān)鍵方法數(shù)據(jù)沒(méi)導(dǎo)入過(guò)就執(zhí)行導(dǎo)入并保存導(dǎo)入過(guò)就直接加載。這個(gè)過(guò)程會(huì)打印詳細(xì)的日志第一次運(yùn)行觀察日志里的導(dǎo)入進(jìn)度和耗時(shí)能幫你判斷數(shù)據(jù)量級(jí)是否匹配當(dāng)前機(jī)器配置。3. SpringBoot 里把 GraphHopper 跑起來(lái)從配置類到可調(diào)用的路由接口3.1 依賴與 Bean 初始化讓引擎隨應(yīng)用生命周期啟動(dòng)SpringBoot 工程引入 GraphHopper 很簡(jiǎn)單核心就一個(gè)依賴com.graphhopper:graphhopper-core。版本要和你下載的源碼對(duì)應(yīng)這一點(diǎn)容易翻車GraphHopper 的 Java 版本要求偏高JDK 8 在較新版本上會(huì)直接運(yùn)行失敗建議 JDK 11 或 17。另一個(gè)隱蔽問(wèn)題GraphHopper 依賴了若干第三方庫(kù)如果你的工程里也用了低版本沖突庫(kù)會(huì)出現(xiàn)NoSuchMethodError啟動(dòng)時(shí)注意看異常棧優(yōu)先調(diào)整 GraphHopper 傳遞依賴的版本即可。Bean 初始化上用Configuration定義一個(gè)GraphHopper單例Bean(initMethod importOrLoad)讓它隨 Spring 容器啟動(dòng)自動(dòng)完成圖加載。不要每次請(qǐng)求都 new 一個(gè) GraphHopper那等于每次重新加載路網(wǎng)內(nèi)存會(huì)爆。下面是標(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í)不會(huì)出現(xiàn)文件鎖問(wèn)題。setMemoryMapped(true)對(duì)大圖更友好但首次路由請(qǐng)求會(huì)偏慢因?yàn)轫?yè)面數(shù)據(jù)是懶加載的預(yù)熱一次就好。啟動(dòng)后日志里如果出現(xiàn)Using memory mapped files和Finished loading graph說(shuō)明圖加載成功。之后所有線程共享該單例路由計(jì)算是并發(fā)的但引擎內(nèi)部對(duì)圖讀取做了線程安全處理不需要額外加鎖。3.2 封裝單點(diǎn)路由計(jì)算從經(jīng)緯度到路線詳情最基礎(chǔ)的能力是兩個(gè)經(jīng)緯度之間的路線。調(diào)用GraphHopper是GHRequest/GHResponse模式創(chuàng)建請(qǐng)求、設(shè)置起終點(diǎn)經(jīng)緯度、指定編碼方式、發(fā)送到引擎然后檢查響應(yīng)是否有異常。這里有一個(gè)最容易忽視的坐標(biāo)順序問(wèn)題GraphHopper 的 API 統(tǒng)一是緯度在前、經(jīng)度在后也就是(lat, lon)和國(guó)內(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里聲明過(guò)的否則拋異常。path.getPoints().toLineString(false)把軌跡點(diǎn)序列轉(zhuǎn)成 WKT 格式的 LineString 字符串前端地圖直接按這個(gè)串繪制路徑省去自行序列化的麻煩。getDistance()返回的是米getTime()返回的是毫秒兩個(gè)值后續(xù)計(jì)算矩陣時(shí)都要用到。這個(gè)接口本身不復(fù)雜但它驗(yàn)證了整個(gè) SpringBoot 集成鏈路是否通——配置類有沒(méi)有加載、坐標(biāo)轉(zhuǎn)換有沒(méi)有問(wè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ì)算接口就該登場(chǎng)了。它避免你寫雙層循環(huán)逐個(gè)調(diào)用單點(diǎn)路由——一次請(qǐng)求算出所有點(diǎn)對(duì)之間的耗時(shí)和距離內(nèi)部會(huì)做批量?jī)?yōu)化耗時(shí)只有逐個(gè)調(diào)用的幾分之一。GraphHopper 矩陣 API 要構(gòu)建一個(gè)MatrixRequest設(shè)置所有點(diǎn)的經(jīng)緯度、編碼方式然后執(zhí)行。返回的矩陣是二維數(shù)組下標(biāo)與原數(shù)組一一對(duì)應(yīng)。這里要注意MatrixRequest不是GHRequest它在底層會(huì)復(fù)用團(tuán)簇算法對(duì)區(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ì)算開(kāi)銷 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)無(wú)法到達(dá)整個(gè)請(qǐng)求會(huì)直接失敗把它關(guān)掉后能拿到部分結(jié)果哪些點(diǎn)不可達(dá)在響應(yīng)里標(biāo)記出來(lái)方便業(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)問(wèn)題拆成 TSP為什么要先算矩陣再排順序、不能直接在圖上搜索明確了矩陣接口之后核心問(wèn)題浮現(xiàn)給三十個(gè)派件點(diǎn)和一個(gè)起點(diǎn)怎么決定先送哪個(gè)、后送哪個(gè)路線規(guī)劃問(wèn)題的本質(zhì)是旅行商問(wèn)題TSP——找一個(gè)經(jīng)過(guò)所有點(diǎn)且總耗時(shí)最短的順序。注意這不是在地圖圖上做一次簡(jiǎn)單搜索能解決的因?yàn)樾枰?jīng)過(guò)的點(diǎn)有多個(gè)而且順序未知搜索空間是排列組合級(jí)別的。圖搜索如 A*只能解決“從 A 到 B 的最短路徑”解決不了“經(jīng)過(guò) A、B、C、D 并以 E 結(jié)束的最短路徑順序”。TSP 的解法分精確算法和啟發(fā)式算法。精確算法如動(dòng)態(tài)規(guī)劃 Held-Karp在 20 個(gè)點(diǎn)左右就開(kāi)始吃力幾十上百點(diǎn)的場(chǎng)景完全不可用。實(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)的約束。最常見(jiàn)場(chǎng)景是“從站點(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è)未訪問(wèn)點(diǎn)走完所有點(diǎn)后得到一條路徑。它本質(zhì)是貪心策略單次運(yùn)行結(jié)果是確定的執(zhí)行時(shí)間只有幾毫秒到幾十毫秒取決于點(diǎn)數(shù)解的質(zhì)量通常不超過(guò)最優(yōu)解的 20% 偏差作為 2-opt 的初始解完全夠用。關(guān)鍵點(diǎn)在于矩陣的構(gòu)建方式——我們需要拿到任意兩點(diǎn)之間通過(guò)路網(wǎng)的真實(shí)驅(qū)動(dòng)耗時(shí)而不是直線距離。這就是第 3 章里矩陣接口的價(jià)值把三十個(gè)點(diǎn)的經(jīng)緯度一次性傳入GraphHopper 返回兩兩之間的駕駛耗時(shí)這個(gè)耗時(shí)已經(jīng)考慮了路網(wǎng)、紅綠燈和道路等級(jí)比歐氏距離靠譜得多。最近鄰算法實(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]的語(yǔ)義是“從當(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)”的對(duì)應(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)飼?huì)有Long.MAX_VALUE繼續(xù)循環(huán)只會(huì)卡死不如提前結(jié)束并把這個(gè)情況上報(bào)給業(yè)務(wù)層。4.3 2-opt 局部搜索用兩兩交換把路徑磨到接近最優(yōu)最近鄰得到一個(gè)初始解但問(wèn)題很明顯貪心的短視行為經(jīng)常導(dǎo)致某條路走了回頭路或者繞了一個(gè)大圈。2-opt 的思想是取當(dāng)前路徑中的兩條邊斷開(kāi)后反向連接重排如果新路徑的總耗時(shí)更小就采納。反復(fù)執(zhí)行直到?jīng)]有可以改進(jìn)的交換為止收斂之后路徑基本定型。2-opt 最核心的改進(jìn)點(diǎn)是“倒序”操作?？串?dāng)前路徑序列如果交換位置i和j之間的路徑段需要把這段倒過(guò)來(lái)而不是簡(jiǎn)單換兩個(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ī)模下通常是幾十毫秒級(jí)的完全夠用。它做不了全局最優(yōu)但能保證解質(zhì)量在 5% 偏差以內(nèi)對(duì)絕大多數(shù)配送調(diào)度場(chǎng)景綽綽有余。4.4 多途徑點(diǎn)接口落地把矩陣和優(yōu)化算法串成一個(gè) HTTP 接口整個(gè)流程串到 SpringBoot 里對(duì)外暴露一個(gè) HTTP 接口接收一組經(jīng)緯度點(diǎn)返回排序后的路線。這里我增加了一個(gè)“強(qiáng)制回起點(diǎn)”開(kāi)關(guān)因?yàn)楹芏鄻I(yè)務(wù)場(chǎng)景是車輛出去必須回站點(diǎn)也有場(chǎng)景是送完就地下班兩種需求用一個(gè)開(kāi)關(guān)控制算法實(shí)現(xiàn)上只在總耗時(shí)計(jì)算時(shí)多加/少加一條回到起點(diǎn)的邊。接口設(shè)計(jì)考慮了批量規(guī)劃場(chǎng)景的調(diào)用方式一次傳入所有點(diǎn)服務(wù)端同步計(jì)算返回帶有順序標(biāo)記的路線列表。由于矩陣計(jì)算和 2-opt 都在內(nèi)存里跑幾十點(diǎn)級(jí)別的接口響應(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ù)來(lái)源1轉(zhuǎn)換坐標(biāo)點(diǎn)lng/lat 轉(zhuǎn) lat/lng請(qǐng)求參數(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)化后順序你會(huì)發(fā)現(xiàn)真正的規(guī)劃邏輯并不在 GraphHopper 里而是發(fā)生在這個(gè)服務(wù)類中。GraphHopper 只負(fù)責(zé)回答“這兩點(diǎn)之間開(kāi)車多久”順序怎么排是你自己的 TSP 算法說(shuō)了算。5. 避坑GraphHopper 集成里最常見(jiàn)的 5 個(gè)翻車點(diǎn)5.1 坐標(biāo)順序搞反路線全部橫穿地圖現(xiàn)象從北京到天津的路線算出來(lái)橫跨了中國(guó)版圖或者路線自動(dòng)繞了上千公里。原因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)換并且寫單元測(cè)試鎖定給定已知經(jīng)緯度的 A/B 兩點(diǎn)驗(yàn)證計(jì)算出的距離在合理范圍內(nèi)。我吃過(guò)一次虧之后在這個(gè)轉(zhuǎn)換方法里加了強(qiáng)校驗(yàn)——如果緯度超過(guò) 90 或者經(jīng)度超過(guò) 180直接拋異常寧可開(kāi)發(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 在圖上找最近的可行走邊失敗就會(huì)報(bào)點(diǎn)不可達(dá)。這種情況在郊區(qū)、新建開(kāi)發(fā)區(qū)特別常見(jiàn)。解決先把點(diǎn)投影到圖上查看GraphHopper返回的最近邊和投影點(diǎn)確認(rèn)是否有道路數(shù)據(jù)如果有路但斷頭則手動(dòng)補(bǔ)錄幾條道路或者調(diào)整點(diǎn)坐標(biāo)到實(shí)際道路位置。工程上給業(yè)務(wù)方提供一個(gè)“地圖選址”功能讓他們?cè)诘貓D上選點(diǎn)而不是填坐標(biāo)能從源頭規(guī)避這個(gè)坑。5.3 強(qiáng)制回起點(diǎn)時(shí)總耗時(shí)少算一段現(xiàn)象接口返回的總耗時(shí)明顯偏短對(duì)比實(shí)際跑下來(lái)的時(shí)間差了將近半小時(shí)。原因閉合 TSP 要求“最后一個(gè)點(diǎn)回起點(diǎn)”這一段路的耗時(shí)也要計(jì)入總和但實(shí)現(xiàn)里只算了路徑內(nèi)部相鄰點(diǎn)的耗時(shí)少了最后一段返程。這個(gè)在代碼 review 階段特別容易漏因?yàn)榭雌饋?lái)路徑已經(jīng)“結(jié)束”了。解決在calculateTotalTime方法里增加一個(gè)布爾參數(shù)returnToStart閉合時(shí)把timeMatrix[last][first]加上。同時(shí)接口返回的明細(xì)里單獨(dú)列出一個(gè)“返程耗時(shí)”字段讓業(yè)務(wù)方能看出這半小時(shí)是怎么來(lái)的。5.4 CH 預(yù)計(jì)算打開(kāi)導(dǎo)致啟動(dòng)極慢、內(nèi)存吃緊現(xiàn)象啟動(dòng)時(shí)構(gòu)建圖明顯變慢日志顯示 CH preprocessing 卡了很久內(nèi)存占用翻倍。原因和第 2 章說(shuō)的一樣CH 預(yù)計(jì)算會(huì)為每個(gè)節(jié)點(diǎn)算跳表構(gòu)建時(shí)間和內(nèi)存開(kāi)銷都很高。多途徑點(diǎn)場(chǎng)景下主要調(diào)矩陣接口單次路由用的不多CH 收益有限但它造成的構(gòu)建負(fù)擔(dān)是實(shí)打?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)存映射模式下首次請(qǐng)求特別慢現(xiàn)象服務(wù)啟動(dòng)后第一個(gè)路由請(qǐng)求要等好幾秒甚至幾十秒后面的請(qǐng)求就正常了。原因MMAP 模式下圖數(shù)據(jù)是懶加載到內(nèi)存的哪條路被搜索到了才把那部分?jǐn)?shù)據(jù)頁(yè)加載進(jìn)來(lái)。首次請(qǐng)求覆蓋的路段多相當(dāng)于把所有道路數(shù)據(jù)都觸達(dá)了一遍自然慢。解決應(yīng)用啟動(dòng)后做一次“預(yù)熱”調(diào)用隨便算一條短線路讓底層把常用圖頁(yè)加載完?；蛘咧苯佑肦AM_STORE模式啟動(dòng)時(shí)全部載入第一次請(qǐng)求和后面一樣快。內(nèi)存夠的話優(yōu)先 RAM_STORE省心。6. 進(jìn)階加一個(gè)“一鍵優(yōu)化”按鈕前先搞懂這些技巧多途徑點(diǎn)規(guī)劃從能跑到好用中間還有幾個(gè)提升體驗(yàn)的小改動(dòng)。第一個(gè)是把 2-opt 的迭代上限露出來(lái)。當(dāng)途徑點(diǎn)數(shù)超過(guò)五十個(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í)矩陣可能長(zhǎng)時(shí)間不變而 GraphHopper 的矩陣計(jì)算是有成本的尤其點(diǎn)多的情況下。如果你的輸入點(diǎn)集相對(duì)固定把矩陣結(jié)果緩存起來(lái)點(diǎn)集變化時(shí)才重新計(jì)算?？梢杂煤?jiǎn)單的ConcurrentHashMap加一個(gè)版本號(hào)來(lái)實(shí)現(xiàn)點(diǎn)在緩存里就直接跳到 TSP 優(yōu)化階段。第三個(gè)技巧是異步化長(zhǎng)任務(wù)。五十個(gè)點(diǎn)以上的規(guī)劃矩陣計(jì)算加 2-opt 可能要幾秒同步阻塞 HTTP 請(qǐng)求會(huì)讓前端一直轉(zhuǎn)圈。一個(gè)老板鍵做法接口先返回任務(wù) ID后端用線程池執(zhí)行規(guī)劃完成后把結(jié)果寫到內(nèi)存緩存前端輪詢拿結(jié)果。這和直接用同步接口相比用戶體驗(yàn)差別明顯。車輛容量約束是另一個(gè)常見(jiàn)擴(kuò)展方向。目前算法只優(yōu)化耗時(shí)不關(guān)心車能不能裝下所有貨。如果你的業(yè)務(wù)里每輛車有載重上限那這就從 TSP 變成了 CVRP帶容量約束的車輛路徑問(wèn)題需要在排順序時(shí)同時(shí)檢查已分配點(diǎn)的累計(jì)重量。最簡(jiǎn)單的做法是分桶——按順序貪心塞進(jìn)多輛車每輛車滿負(fù)荷后開(kāi)下一輛再用 2-opt 分別優(yōu)化每輛車的順序。我做這套系統(tǒng)的過(guò)程中最耗時(shí)的不是算法本身而是把坐標(biāo)順序、數(shù)據(jù)精度、返程耗時(shí)這些細(xì)節(jié)打磨對(duì)。這些坑不填掉再快的最優(yōu)算法都給不了業(yè)務(wù)可用的結(jié)果。規(guī)劃接口上線之后配送員的實(shí)際行駛距離和我算出來(lái)的路線差距穩(wěn)定在 10% 以內(nèi)——說(shuō)明路網(wǎng)速度假設(shè)和實(shí)際匹配良好。后續(xù)如果你遇到“某些點(diǎn)搜不到”“總耗時(shí)不對(duì)”“啟動(dòng)慢得離譜”這類問(wèn)題按第 5 章的排查順序過(guò)一遍大多數(shù)能直接解決。如果你要更大規(guī)模的點(diǎn)集上千個(gè)點(diǎn)那種建議改用專門的 VROOM 和 jsprit 這類開(kāi)源求解器配合 GraphHopper 做路網(wǎng)前處理依然能把整套鏈路留在自己的工程里。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取