【正文】 22 條染色體 。 該子問題可表示為 滿足約束條件 ： 本文采用文獻 [3]中的啟發(fā)式方法進行求解 。 N 的取值不宜過大或過小 。 例如 ， 圖 1 的布爾矩陣為 即車 輛 1 負責客戶 1 和 2， 車輛 2 負責客戶 4 和 5. 定義適配值計算函數(shù) 適應度函數(shù)是遺傳算法中評價解集好壞的依據(jù) ,適配值高的個體優(yōu)先培養(yǎng) 。 可以采用遺傳算法的思想作為總體框架對該問題進行求解 ， 用遺傳算法求解變量 ， 而變量 則用啟發(fā)式算法求解 。即事先設置一個最大代數(shù)，如當前代數(shù)大于最大代數(shù)時，算法停止。A， 39。實施交叉操作。簡 單的說就是人為選取較好的一對染色體作為新染色體的父母，按染色體按長度分為前后兩段，取其中一個染色體的前半部分放在另一個染色體的前邊，再順序遍歷新染色體的基因并剔除重復基因，從而得到新的染色體 child1。由于適應度函數(shù)通常越大越好，而物流車輛路徑優(yōu)化問題則是求最小經(jīng)濟成本，為了便于計算且增大區(qū)分度，算法采用的是目標函數(shù)的倒數(shù)乘以區(qū)分度系數(shù) β 作為適應度函數(shù)，即 maxF = 1 / S * β (3231) 遺傳算子 1. 遺傳選擇 選擇是用來確定重組或交叉?zhèn)€體，以及被選個體將產生多少個子代個體。如個體 0l26354 表示的配送路徑方案為：路徑 1： 0126，路徑 2： 354共有 2 條配送路徑； 種群的初始化 群體初始化時，采用兩種機制，一種是隨機生成個體，一種是按 前相插入啟發(fā)式算法。由于在配送中心有 m 輛汽車，則最多存在 m 條配送路徑，每條配送路徑都始于配送中心，也終于配送中心。硬時間窗 (Hard Time Windows)：指配送車輛必須在特定時間區(qū)段，將貨物送達顧客手中，不論是遲到或早到都完全不予接受；軟時間窗 (Soft Time Windows)：允許服務的開始時間有所偏離時間窗，則必須按照違反時間的長短施以一定的罰金或其他懲罰法則；混合型時間窗（ Mixed Time Windows）：是指系統(tǒng)中有些客戶 只接受硬時間窗服務，有些客戶接受軟時間窗服務，或者同一客戶，往往軟、硬兩種時間窗服務混合使用。 圖 3 懲罰函數(shù) 帶時間窗的物流配送問題優(yōu)化問題 帶時間窗 VRP（ VRP with Time Windows， VRPTW）是帶裝載能力約束的CVRP(Capacitated VRP， CVRP)的擴展。 若車輛 k 為客戶 i 服務 ， 則 1， 否則為 0， 即 ： 此變量表示車輛分配方案 ， 可用布爾矩陣表示 ； 若車輛 k 經(jīng)由客戶 i 到客戶 j， 則 為 1， 否則為 0， 即 ：， 表示車輛路線安排 。遺傳算法在優(yōu)化領域表現(xiàn)出了其強大的能力，遺傳算法仿照生物進化和遺傳的規(guī)律，利用復制、交換和突變等操作，使優(yōu)勝者繁殖，劣敗者消失，一代代重復同樣的操作，最終找出最優(yōu)解。 這 5 個要素構成了遺傳算法的核心內容。 遺傳算法特別適用于傳統(tǒng)搜索方法難以解決的復雜的和非線性的問題，可廣泛用于組合優(yōu)化、自適應控制、規(guī)劃設計和人工生命等領域。利用遺傳算法進行尋優(yōu)時，編碼、選擇、交叉、變異是四個重要步驟。它是根據(jù)生物進化思想而啟發(fā)得出的一種全局優(yōu)化算法。 Ombuk 提出了用 遺傳算法 進行路線分組，然后用禁忌搜索方法進行路線優(yōu)化的混合算法。 西南交通大學 的袁慶達等設計了考慮時間窗口和不同車輛類型的禁忌算法，這種算法主要采用 GENIUS 方法產生初始解，然后禁忌算法對初始解優(yōu)化。 兩階段方法包括先分組后定路線（ clusterfirstroute second）和先定路線后分組（ routefirstcluster second）兩種啟發(fā)式策略。節(jié)省法或插入法（ savings or insertion）是在求解過程中使用節(jié)省 成本最大的可行方式構造路線，直到無法節(jié)省為止。第一階段是從 1960 年到 1970 年，屬于簡單啟發(fā)式方式，包括有各種局部改善啟發(fā)式算法和貪婪法（ Greedy）等；第二階段是從 1970 年到 1980 年，屬于一種以數(shù)學規(guī)劃為主的啟發(fā)式解法，包括指派法、集合分割法和集合涵蓋法；第三階段是從 1990 開始至今，屬于較新的方法，包括利用嚴謹啟發(fā)式方法、人工智能方法等。下面從車輛路線問題的現(xiàn)有研究型態(tài)和求解方法兩個方面介紹車輛路線問題的研究現(xiàn)狀。 車輛路徑問題的類型 一般而言車輛路線問題大致可以分為以下三種類型（ Ballou， 1992） ： 相異的單一起點和單一終點。 車輛路線問題自 1959 年提出以來，一直是網(wǎng)絡優(yōu)化問題中最基本的問題之一，由于其應用的廣泛性和 經(jīng)濟 上的重大價值，一直受到國內外學者的廣泛關注。本文對大量的基準測試實例 (Benchmark)進行了仿真計算 ,計算結果表明 ,本文所提出的一系列算法能有效求解物流系統(tǒng)中的庫存優(yōu)化問題與車輛路徑問題。然后研究了遺傳算法與鄰域搜索算法的結合方式 ,在遺傳算法中引入了帶克隆操作的鄰域搜索算子。此外 ,相對于常用的單層染色體編碼方案 ,該編碼方案還能降低搜索空間的大小 ,從 6 而提高搜索效率并降低計算時間。提出了 K 近鄰點集的概念以縮減搜索空間并提高算法的時間效率。針對兩種常用的庫存控制策略進行了仿真優(yōu)化的實驗 ,結果表明本文提出的仿真優(yōu)化方法是有效的。用系統(tǒng)仿真方法求解最優(yōu)庫存策略時 ,其難點之一在于仿真的優(yōu)化。 遺傳算法是一種應用很廣泛的智能優(yōu)化算法 ,本文對遺傳算法進行了分析研究 ,針對遺傳算法的一些缺陷提出了相應的改進方法。通過優(yōu)化物流系統(tǒng) ,可以降低物流成本 ,從而增強企業(yè)的市場競爭能力。有容量約束的車輛路徑問題（ Capacitated Vehicle routing problem， CVRP）是由一個服務中心（或車場）的若干車輛向多個客戶點進行配送服務，在已知待服務客戶點和出發(fā)點 的位置、客戶需求及車輛最大負載的前提下，設計車輛配送路徑，規(guī)劃設計方案，使運輸成本最小化，即總代價最?。ㄊ褂密囕v盡量少，行車總距離盡量短）。 VRP 最早由 Dantzig 和 Ramser 于 1959 年提出，引起運籌學、應用數(shù)學、組合數(shù)學、圖論與網(wǎng)絡分析、物流科學、計算機應用等學科研究人員的極大重視，成為運籌學與組合優(yōu)化領域的熱點問題。 本文首先介紹了遺傳算法在解決簡單約束車輛路徑問題上的應用，改進了交叉算子，為研究有時間窗裝卸問題的遺傳算法作了充分準備。 掃描法 。應用 C 語言編程進行實例計算 ,結果表明改進的遺傳算法明顯增強了群體演化的質量 ,提高了算法的收斂速度 ,得到了問題的滿意解。本文主要對單車場非滿載無時間窗的車輛路徑問題和動態(tài)車輛路徑問題進行了研究。配送作為物流中一種特殊的、綜合的活動形式 ,在當今社會經(jīng)濟發(fā)展中發(fā)揮著越來越重要的作用。物流的目標就在于以最少的費用滿足消費者的需求。對配送車輛進行優(yōu)化調度 ,有利于提高物流經(jīng)濟效益、實現(xiàn)物流科學化。在對遺傳算法中的選擇操作、鄰域結構操作進行改進的基礎上 ,提出了一種求解車輛路徑問題的自適應遺傳算法。 關鍵詞 ： 物流車輛路徑問題 。 geic algorithm 3 1 引言 車輛路徑問題（ Vehicle Routing Problem， VRP）是一類在物流配送調度中具有廣泛應用的優(yōu)化組合問題，在現(xiàn)代物流中居于中心地位。采用多組通用算例測算，將多策略分組編碼遺傳算法與其它算法進行比較，其求解結果和計算時間都有明顯改進，驗證了多策略分組編碼遺傳算法能夠有效穩(wěn)定地收斂到所求問題的解。本文重點研究解決有時間窗裝卸問題（ PDPTW）的遺傳算法，作為前期準備，本文作者對遺傳算法解決具有簡單約束條件的 VRP（包括有容量約束的車輛路徑問題 CVRP 和有時間窗的車輛路徑問題 VRPTW）進行了初步研究。 5 2 選題的目的 物流已被認為是繼降低原材料消耗和提高勞動生產率之后的 “ 第三利潤源 ” 。如果能降低庫存成本與配送成本 ,就能有效地降低物流成本。 本文的主要研究工作及貢獻可歸納如下 : (1)對隨機庫存系統(tǒng)建立了基于離散事件系統(tǒng)的計算