該算法的思想是從起點開始，每次新擴展一個距離短的點，并更新從起點到該點的距離與路線。直到拓展到終點，并且往其他方向拓展點的距離不比該點的距離更近時停止。對圖 3 的求解過程如圖4所示。終的路線是。2.2 A*算法在Dijkstra中，當前拓展到的點的距離為從起點到當前點的實際短距離。而A* 算法與 Dijkstra相比增加了一個啟發項，即在計算當前點的路線距離時，使用從起點到當前點的實際短距離加上從當前拓展的點到終點的估計距離。因此，在實際距離相同時，估計距離近的點優先繼續拓展。使用A*算法對圖3 的求解結果如圖5 所示。終的路線是假設我們有1個出發點(編號為)和6個訪問點(編號為)，車輛從出發，需要完成對所有訪問點的訪問。如果終讓車輛停留在后一個訪問點的訪問點，這就是一個開環的路徑，如果要求車輛必須返回出發地，則是閉環的路徑。這里假設為開環路徑，即認為路徑結束的標志是完成所有任務中所有訪問點的配貨。我們這里控制了初始搜索步長len，意為從step(1) 到step(len) 搜索出的路徑是按照 DP的方式搜索到的當前精確合適的路線，而從step(len+1)開始，只記錄該step下的n條路徑中合適的結果。因此，當len的值越大，終搜索的結果越接近精確合適解，但是相應的求解時間也會越長。假設通過該階段終搜索出的合適結果為，接下來將基于此結果執行變鄰域搜索操作。由于是規定的出發點需要保持在輸出路徑的首先位置，因此我們對序列{2,6,1,5,4,3}進行鄰域搜索。VND的框架如圖8 所示。使用VND不斷地對序列變換得到新的序列，并求新序列的路徑成本。需要注意的是，求路徑成本時要將出發點考慮在內，即將出發點添加到序列前，求該完整路徑的旅行成本。經過VND過程的處理，輸出的路線即作為終規劃的路線，例如一個可能的終輸出路徑果是，需要注意的是，這里的節點相當于是“關鍵節點”，即只包含的出發點和需要進行配貨操作的訪問點。而相鄰“關鍵節點”之間的路線，則是根據前述的 Dijkstra計算的兩點之間的路線進行行駛。今天的介紹就到這里，希望小伙伴們能對路徑規劃問題和算法有所了解和收獲！