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