【正文】 1 基于遺傳算法的車輛路徑問題研究 中文摘要 ： 近些年 ,物流作為 “ 第三利潤源泉 ” 受到國內(nèi)各行業(yè)的極大重視并得到較大的發(fā)展。物流的目標就在于以最少的費用滿足消費者的需求。配送作為物流中一種特殊的、綜合的活動形式 ,在當今社會經(jīng)濟發(fā)展中發(fā)揮著越來越重要的作用。配送的核心為配送車輛的調(diào)度、貨物配裝及送貨過程。進行配送系統(tǒng)優(yōu)化 ,主要是配送車輛調(diào)度的優(yōu)化。對配送車輛進行優(yōu)化調(diào)度 ,有利于提高物流經(jīng)濟效益、實現(xiàn)物流科學(xué)化。本文主要對單車場非滿載無時間窗的車輛路徑問題和動態(tài)車輛路徑問題進行了研究。論文首先對現(xiàn)有車輛優(yōu)化調(diào)度問題歸類 分析。然后對車輛路徑問題的傳統(tǒng)求解算法的基本思想、性能、適用性進行了分析 ,在此基礎(chǔ)上提出了采用掃描法和遺傳算法相結(jié)合的啟發(fā)式算法來求解物流配送車輛優(yōu)化調(diào)度問題的思想。在對遺傳算法中的選擇操作、鄰域結(jié)構(gòu)操作進行改進的基礎(chǔ)上 ,提出了一種求解車輛路徑問題的自適應(yīng)遺傳算法。應(yīng)用 C 語言編程進行實例計算 ,結(jié)果表明改進的遺傳算法明顯增強了群體演化的質(zhì)量 ,提高了算法的收斂速度 ,得到了問題的滿意解。與傳統(tǒng)遺傳算法相比 ,掃描法和改進遺傳算法的結(jié)合 ,其優(yōu)化能力、運行效率、可靠性均有一定的提高。最后論文在對動態(tài)行駛時間車輛路徑問題 進行建模的基礎(chǔ)上 ,嘗試采用掃描法和改進遺傳算法相結(jié)合的方法對此類問題進行求解 ,在保證客戶服務(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)代物流中居于中心地位。 本文首先介紹了遺傳算法在解決簡單約束車輛路徑問題上的應(yīng)用，改進了交叉算子，為研究有時間窗裝卸問題的遺傳算法作了充分準備。本文詳細分析了有時間窗裝卸問題的數(shù)學(xué)模型，深入研究解決此問題的分組編碼遺傳算法，將禁忌思想用于產(chǎn)生可行解的啟發(fā)式插入搜索算法之中，并構(gòu)造出適用于多目標的適應(yīng)度函數(shù)，設(shè)計新的數(shù)據(jù)結(jié)構(gòu)，對分組編碼遺傳算法進行有效實現(xiàn)。 在分組編碼遺傳算法中 提出路徑調(diào)整思想，設(shè)計出一種多策略分組編碼遺傳算法。采用多組通用算例測算，將多策略分組編碼遺傳算法與其它算法進行比較，其求解結(jié)果和計算時間都有明顯改進，驗證了多策略分組編碼遺傳算法能夠有效穩(wěn)定地收斂到所求問題的解。 VRP 最早由 Dantzig 和 Ramser 于 1959 年提出，引起運籌學(xué)、應(yīng)用數(shù)學(xué)、組合數(shù)學(xué)、圖論與網(wǎng)絡(luò)分析、物流科學(xué)、計算機應(yīng)用等學(xué)科研究人員的極大重視，成為運籌學(xué)與組合優(yōu)化領(lǐng)域的熱點問題。各國研究人員對該問題進行了大量的理論研究及實驗分析，取得了重大進展， 其研究成果在運輸系統(tǒng)、公交車輛路 線設(shè)計、快遞收發(fā)系統(tǒng)、物資調(diào)配系統(tǒng)中都已得到了廣泛應(yīng)用。 研究車輛路徑問題的特點及算法具有重要的實際意義。本文重點研究解決有時間窗裝卸問題（ PDPTW）的遺傳算法，作為前期準備，本文作者對遺傳算法解決具有簡單約束條件的 VRP（包括有容量約束的車輛路徑問題 CVRP 和有時間窗的車輛路徑問題 VRPTW）進行了初步研究。有容量約束的車輛路徑問題（ Capacitated Vehicle routing problem， CVRP）是由一個服務(wù)中心（或車場）的若干車輛向多個客戶點進行配送服務(wù)，在已知待服務(wù)客戶點和出發(fā)點 的位置、客戶需求及車輛最大負載的前提下，設(shè)計車輛配送路徑，規(guī)劃設(shè)計方案，使運輸成本最小化，即總代價最小（使用車輛盡量少，行車總距離盡量短）。 CVRP 實際是多目標組合優(yōu)化問題，一般以派出車輛最少（運輸路線條數(shù)最少）為首要目標，行車總距離最短，即總代價最小為次要目標。 CVRP 要求滿足以下條件及假設(shè)： 4 （ 1）所有的配送車輛以配送中心為起點并最終回到配送中心； （ 2）每條配送路徑上各客戶點的需求量之和不超過車輛的負載量； （ 3）每個客戶點的需求僅由一輛車一次滿足。 5 2 選題的目的 物流已被認為是繼降低原材料消耗和提高勞動生產(chǎn)率之后的 “ 第三利潤源 ” 。通過優(yōu)化物流系統(tǒng) ,可以降低物流成本 ,從而增強企業(yè)的市場競爭能力。因此 ,研究物流系統(tǒng)中的優(yōu)化問題 ,具有十分重要的意義 ,是國內(nèi)外研究的一個熱點。 庫存成本與配送成本是物流系統(tǒng)的核心成本 ,在物流總成本中占據(jù)了很大的比例。如果能降低庫存成本與配送成本 ,就能有效地降低物流成本。 遺傳算法是一種應(yīng)用