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