基于遺傳算法的多車場(chǎng)車輛路徑問(wèn)題研究.pdf

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

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

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

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