基于遺傳算法的多車場車輛路徑問題研究.pdf

1、物流配送所獲取的利潤在現(xiàn)代物流企業(yè)利潤中所占比例非常大，而車輛路徑問題又是物流配送中的核心問題。因此對車輛路徑問題(VRP)的研究具有非常重要的意義。在實際生活中，大型的物流企業(yè)并不只擁有一個配送中心(車場)，而是擁有多個配送中心，這便引出了多車場車輛路徑問題(MDVRP)。MDVRP屬于NP難問題，求得最優(yōu)解相當困難，因此該文便采用遺傳算法對其進行求解。遺傳算法是利用了生物進化的特點，利用染色體在進化過程中的交叉、變異過程，對問題的解

2、空間進行全局搜索，從而尋求較優(yōu)解。在對多車場車輛路徑問題的研究中，設(shè)計了兩種遺傳算法，來適應(yīng)不同的需求。對小規(guī)模，或者求解效果要求不高的數(shù)據(jù)集，采用單親遺傳算法；而對規(guī)模較大，要求求解效果較好，時間要求不高的數(shù)據(jù)集，采用基于虛擬車場的遺傳算法。 該文對MDVRP進行了研究，其主要貢獻有以下幾個方面： ①對MDVRP的數(shù)學模型以及研究方法進行了探討，構(gòu)造出了數(shù)學模型，并對不同的研究方法進行了歸納總結(jié)，并提出了自己的研究方法

3、。 ②在對于小規(guī)模數(shù)據(jù)時，采用把多車場問題轉(zhuǎn)化成多個單車場問題并行解決的方法，使用單親遺傳算法的思想，構(gòu)造出相應(yīng)的遺傳算子對多車場車輛路徑問題進行求解。 ③在對于大規(guī)模數(shù)據(jù)時，采用增加虛擬車場的方法把多車場車輛路徑問題進行轉(zhuǎn)換成單車場車輛路徑問題，采用普通遺傳算法的思想，并構(gòu)造出相應(yīng)的遺傳算子對其進行求解。 ④對不同規(guī)模的數(shù)據(jù)集進行測試，證明了該文提出的兩種解決方法的各自的不同應(yīng)用場合。所做的模擬系統(tǒng)能用于物流企

4、業(yè)，具有實際適用價值。 從論文結(jié)構(gòu)上來看，該文首先介紹了MDVRP的研究背景和當前的研究現(xiàn)狀。然后該文對MDVRP進行了描述，提出了該問題的數(shù)學模型。在第三章里面，詳細介紹了在對小規(guī)模的MDVRP進行求解的時候，所采用的單親遺傳算法。單親遺傳算法對MDVRP的求解是針對于把MDVRP轉(zhuǎn)化為多個VRP的解決方法而設(shè)計的，其特點是運算速度快。然后在第四章介紹了基于虛擬車場的遺傳算法來解決較大規(guī)模的MDVRP問題。這種方法的主要思想是