VNS求解CVRP問題=怎么解決

今天就跟大家聊聊有關VNS求解CVRP問題=怎么解決，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結了以下內容，希望大家根據這篇文章可以有所收獲。

CVRP問題就是容量受限制的車輛路徑問題，容量受限指的是每輛車的容量都有限制，我們對問題的目標進行設定，下面設定問題的目標為在用最少車輛的前提下，使得所用車輛所行使的總距離最短。

1.CVRP及數學模型

1.1  帶容量的車輛路徑問題描述

帶容量約束的車輛路徑問題描述為：有一個車場，共有Ｋ輛車，每輛車的最大載重為Q，這些車輛為L個客戶服務，客戶i的需求為q_i，每個客戶可由任一輛車進行服務，但只能被一輛車服務一次，每輛車服務完后必須返回原車場。其目標是找到一個合適的車輛調度方案，在滿足客戶需求的同時使車輛的運輸成本最低。

1.2  帶容量的車輛路徑問題模型

帶容量約束的車輛調度問題模型建立：配送中心（用0表示），用戶編號為1,2,……,L；配送中心及客戶點均以點i和j表示，車輛用k表示；編號1,2,……，k；用戶i的貨物需求為q_i，q_i＜Q；從i地到j地的運輸成本為C_ij，, w_ijk表示車輛K從客戶i到客戶j的車的剩余容量，

定義決策變量

數學模型如下

目標函數(1)表示車輛運行的總費用最低；式(2)表示每輛車運輸的貨物不超過最大載重；式(3)表示保證每個 客戶都要被訪問；式(4)、式(5)表示保證每個客戶只能被 一輛車訪問；式(6)表示每輛車從配送中心出發是滿載的； 式(7)表示進入任一客戶之前，車上足夠的貨物供給客戶；式(8)表示消除子回路；式(9)表示變量的取值范圍。

2.VNS求解CVRP問題

不同于上次推文所使用的交換算子和插入算子，本文使用的是逆轉算子，即將兩個位置之間的所有元素都逆序排列。

因為本文的目標是在使用車輛數量最少的前提下，使總行駛距離最短。小編認為CVRP問題依然可以看成另一種形式的TSP問題。舉個例子，比如說一共有10個顧客，每個顧客所需要裝貨的容積為{4 3 6 9 10 4 6 5 8 7}，而每輛車的載貨量為30，假設初始顧客排序為1 2 3 4 5 6 7 8 9 10，那么我們就可以依次求容積和，一旦總容積和大于30就將顧客進行分為一組，每一組的顧客由一輛車取貨，因此分組情況為{4 3 6 9| 10 4 6 4| 8 7}，分為3組，每組再按照順序依次取貨。因此第1輛車服務的顧客為{1 2 3 4}，第2輛車服務的顧客為{5 6 7 8},第3輛車服務的顧客為{9 10}。小伙伴們是否明白了呢，不過這是小編一家之言，雖然能出一個不錯的結果，但這個方法究竟是否可行，還需各位小伙伴們指點。

看完上述內容，你們對VNS求解CVRP問題=怎么解決有進一步的了解嗎？如果還想了解更多知識或者相關內容，請關注億速云行業資訊頻道，感謝大家的支持。