溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
構造CVRP問題初始解的啟發(fā)式方法是什么，針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。
今天小編為大家講解一種構造CVRP（容量受限的車輛路徑問題）的啟發(fā)式方法。什么是CVRP問題，不太了解的小伙伴可以看一下VNS（變鄰域搜索算法）求解CVRP問題這篇文章。首先說一下思路，構造CVRP問題啟發(fā)式方法，最著名的莫過于Clark and Wright在1964年提出的方法——節(jié)約算法。
在這里我們以solomon算例種的c102算例為例進行講解。
設顧客數量為n，每輛車容量為200，0代表配送中心
下面小編詳細介紹一下這種經典的啟發(fā)式方法。
step1：假設有n輛車，每輛車只服務一個顧客，因此就產生n個獨立的回路。
然后計算將顧客i 和顧客j合并到一條路徑上，距離的減少量也就是所謂的節(jié)約值：
，找出最大節(jié)約值對應的那兩個顧客i 和顧客j，然后將顧客i 和顧客j合并到一條路徑上，如下圖所示。
step2：當一條路徑上有兩個顧客時，比如說上圖中的0120這種情況，再想將沒有被融合的路徑上的一個顧客i 融合到該路徑時，一共有3種插入位置，也就是：0i120、01i20、012i0，需要計算這3種情況的節(jié)約值。如果一條路徑上只有一個顧客，節(jié)約值還像上述方法計算即可。
step3：當一條路徑上所有顧客的需求總量超過車的容量時，這時就需要開辟一條新的路徑，然后按照step1和step2再次計算節(jié)約值，然后進行路徑融合，直到所有的顧客都被分配到車輛來送貨時，該算法就STOP了。
關于構造CVRP問題初始解的啟發(fā)式方法是什么問題的解答就分享到這里了，希望以上內容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業(yè)資訊頻道了解更多相關知識。
免責聲明：本站發(fā)布的內容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
