【正文】 1 基于遺傳算法的車輛路徑問題研究 中文摘要 ： 近些年 ,物流作為 “ 第三利潤(rùn)源泉 ” 受到國(guó)內(nèi)各行業(yè)的極大重視并得到較大的發(fā)展。物流的目標(biāo)就在于以最少的費(fèi)用滿足消費(fèi)者的需求。配送作為物流中一種特殊的、綜合的活動(dòng)形式 ,在當(dāng)今社會(huì)經(jīng)濟(jì)發(fā)展中發(fā)揮著越來越重要的作用。配送的核心為配送車輛的調(diào)度、貨物配裝及送貨過程。進(jìn)行配送系統(tǒng)優(yōu)化 ,主要是配送車輛調(diào)度的優(yōu)化。對(duì)配送車輛進(jìn)行優(yōu)化調(diào)度 ,有利于提高物流經(jīng)濟(jì)效益、實(shí)現(xiàn)物流科學(xué)化。本文主要對(duì)單車場(chǎng)非滿載無(wú)時(shí)間窗的車輛路徑問題和動(dòng)態(tài)車輛路徑問題進(jìn)行了研究。論文首先對(duì)現(xiàn)有車輛優(yōu)化調(diào)度問題歸類 分析。然后對(duì)車輛路徑問題的傳統(tǒng)求解算法的基本思想、性能、適用性進(jìn)行了分析 ,在此基礎(chǔ)上提出了采用掃描法和遺傳算法相結(jié)合的啟發(fā)式算法來求解物流配送車輛優(yōu)化調(diào)度問題的思想。在對(duì)遺傳算法中的選擇操作、鄰域結(jié)構(gòu)操作進(jìn)行改進(jìn)的基礎(chǔ)上 ,提出了一種求解車輛路徑問題的自適應(yīng)遺傳算法。應(yīng)用 C 語(yǔ)言編程進(jìn)行實(shí)例計(jì)算 ,結(jié)果表明改進(jìn)的遺傳算法明顯增強(qiáng)了群體演化的質(zhì)量 ,提高了算法的收斂速度 ,得到了問題的滿意解。與傳統(tǒng)遺傳算法相比 ,掃描法和改進(jìn)遺傳算法的結(jié)合 ,其優(yōu)化能力、運(yùn)行效率、可靠性均有一定的提高。最后論文在對(duì)動(dòng)態(tài)行駛時(shí)間車輛路徑問題 進(jìn)行建模的基礎(chǔ)上 ,嘗試采用掃描法和改進(jìn)遺傳算法相結(jié)合的方法對(duì)此類問題進(jìn)行求解 ,在保證客戶服務(wù)水平的要求下 ,取得了比較好的結(jié)果。 關(guān)鍵詞 ： 物流車輛路徑問題 。 掃描法 。 遺傳算法 Abstract:Recent years, logistics, taken as the third profit resource, has been developing rapidly. The object of logistics is to satisfy the requirements of consumers with least cost. As an especial and integrated activity of logistics, physical distribution plays an important role in modern society. Vehicle Routing Problem (VRP) is the main part of the distribution system optimizing. It is benefits to make economic paper mainly studied a type of vehicle routing problem with single depot, nonfull load and without time windows and a dynamic vehicle routing problem. The restrictions and math models of vehicle routing problem is analyzed. This paper also 2 pared and analyzed the basic ideas, capabilities and applicability of tradition method heuristics of VRP. Based on this, this paper put forward an improved geic algorithm for vehicle routing problem, through changing its select operation and neighborhood structure operation, an adaptive geic algorithm was presented for solving this problem. Computational results based on C language programming demonstrated that the adaptative algorithm improved the quality of the results and can solve the problem effectively. Exemplifications proved that this algorithm can enhance capability of optimization, solving efficiency and reliability of running. Finally, a dynamic vehicle routing problem with random time window is modeled. This problem is also solved by sweep and geic algorithms method. The method have made good effect in ensuring customer service level. Keyword: Vehicle Routing Problem。 sweep method。 geic algorithm 3 1 引言 車輛路徑問題（ Vehicle Routing Problem， VRP）是一類在物流配送調(diào)度中具有廣泛應(yīng)用的優(yōu)化組合問題，在現(xiàn)代物流中居于中心地位。 本文首先介紹了遺傳算法在解決簡(jiǎn)單約束車輛路徑問題上的應(yīng)用，改進(jìn)了交叉算子，為研究有時(shí)間窗裝卸問題的遺傳算法作了充分準(zhǔn)備。本文詳細(xì)分析了有時(shí)間窗裝卸問題的數(shù)學(xué)模型，深入研究解決此問題的分組編碼遺傳算法，將禁忌思想用于產(chǎn)生可行解的啟發(fā)式插入搜索算法之中，并構(gòu)造出適用于多目標(biāo)的適應(yīng)度函數(shù)，設(shè)計(jì)新的數(shù)據(jù)結(jié)構(gòu)，對(duì)分組編碼遺傳算法進(jìn)行有效實(shí)現(xiàn)。 在分組編碼遺傳算法中 提出路徑調(diào)整思想，設(shè)計(jì)出一種多策略分組編碼遺傳算法。采用多組通用算例測(cè)算，將多策略分組編碼遺傳算法與其它算法進(jìn)行比較，其求解結(jié)果和計(jì)算時(shí)間都有明顯改進(jìn)，驗(yàn)證了多策略分組編碼遺傳算法能夠有效穩(wěn)定地收斂到所求問題的解。 VRP 最早由 Dantzig 和 Ramser 于 1959 年提出，引起運(yùn)籌學(xué)、應(yīng)用數(shù)學(xué)、組合數(shù)學(xué)、圖論與網(wǎng)絡(luò)分析、物流科學(xué)、計(jì)算機(jī)應(yīng)用等學(xué)科研究人員的極大重視，成為運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域的熱點(diǎn)問題。各國(guó)研究人員對(duì)該問題進(jìn)行了大量的理論研究及實(shí)驗(yàn)分析，取得了重大進(jìn)展， 其研究成果在運(yùn)輸系統(tǒng)、公交車輛路 線設(shè)計(jì)、快遞收發(fā)系統(tǒng)、物資調(diào)配系統(tǒng)中都已得到了廣泛應(yīng)用。 研究車輛路徑問題的特點(diǎn)及算法具有重要的實(shí)際意義。本文重點(diǎn)研究解決有時(shí)間窗裝卸問題（ PDPTW）的遺傳算法，作為前期準(zhǔn)備，本文作者對(duì)遺傳算法解決具有簡(jiǎn)單約束條件的 VRP（包括有容量約束的車輛路徑問題 CVRP 和有時(shí)間窗的車輛路徑問題 VRPTW）進(jìn)行了初步研究。有容量約束的車輛路徑問題（ Capacitated Vehicle routing problem， CVRP）是由一個(gè)服務(wù)中心（或車場(chǎng)）的若干車輛向多個(gè)客戶點(diǎn)進(jìn)行配送服務(wù)，在已知待服務(wù)客戶點(diǎn)和出發(fā)點(diǎn) 的位置、客戶需求及車輛最大負(fù)載的前提下，設(shè)計(jì)車輛配送路徑，規(guī)劃設(shè)計(jì)方案，使運(yùn)輸成本最小化，即總代價(jià)最?。ㄊ褂密囕v盡量少，行車總距離盡量短）。 CVRP 實(shí)際是多目標(biāo)組合優(yōu)化問題，一般以派出車輛最少（運(yùn)輸路線條數(shù)最少）為首要目標(biāo)，行車總距離最短，即總代價(jià)最小為次要目標(biāo)。 CVRP 要求滿足以下條件及假設(shè)： 4 （ 1）所有的配送車輛以配送中心為起點(diǎn)并最終回到配送中心； （ 2）每條配送路徑上各客戶點(diǎn)的需求量之和不超過車輛的負(fù)載量； （ 3）每個(gè)客戶點(diǎn)的需求僅由一輛車一次滿足。 5 2 選題的目的 物流已被認(rèn)為是繼降低原材料消耗和提高勞動(dòng)生產(chǎn)率之后的 “ 第三利潤(rùn)源 ” 。通過優(yōu)化物流系統(tǒng) ,可以降低物流成本 ,從而增強(qiáng)企業(yè)的市場(chǎng)競(jìng)爭(zhēng)能力。因此 ,研究物流系統(tǒng)中的優(yōu)化問題 ,具有十分重要的意義 ,是國(guó)內(nèi)外研究的一個(gè)熱點(diǎn)。 庫(kù)存成本與配送成本是物流系統(tǒng)的核心成本 ,在物流總成本中占據(jù)了很大的比例。如果能降低庫(kù)存成本與配送成本 ,就能有效地降低物流成本。 遺傳算法是一種應(yīng)用