【正文】 這樣的染色體結(jié)構(gòu)可通俗地理解為第一輛車從配送中心 0 出發(fā)，經(jīng)過(guò)需求點(diǎn)siii 11211 , ? 后，回到配送中心 0， 形成子路徑 1；第二輛車也從配送中心 0 出發(fā)，經(jīng)過(guò)以 28 前未訪問(wèn)的需求點(diǎn) tiii 22221 , ? 后，返回配送中心 0，形成子路徑 2；依次類推，直到所有的 n個(gè)需求點(diǎn)全部被遍歷，形成子路徑 m。本算法采用人機(jī)對(duì)話來(lái)調(diào)整 a 的大小。 隨機(jī)選擇三個(gè)位置 5 4 3 9 8 1 7 6 2 交換相應(yīng)的城市 5 4 3 9 8 6 7 1 2 5 4 6 9 8 1 7 3 2 5 4 6 9 8 3 7 1 2 5 4 1 9 8 6 7 3 2 5 4 1 9 8 3 7 6 2 25 第 4 章 遺傳算法求解有時(shí)間窗非滿載 VSP 由于現(xiàn)在各任務(wù)需求點(diǎn)，如零售商店、連鎖店等都盡可能的銷售暢銷商品，庫(kù)存數(shù)量最好不要太多，且不能缺貨，因此現(xiàn)在的物流配送一般是小范圍、近距離 、多品種、小批量、多批次、為多用戶服務(wù)的經(jīng)濟(jì)活動(dòng)，這時(shí)每個(gè)任務(wù)點(diǎn)的貨物量小于車輛容量，用一輛車執(zhí)行單一任務(wù)，屬于非滿載運(yùn)行情況，在一輛車上同時(shí)裝載有不同任務(wù)點(diǎn)的貨物，所以物流配送車輛優(yōu)化調(diào)度大部分是非滿載車輛優(yōu)化調(diào)度問(wèn)題。過(guò)程示于圖 37中。步驟如下： Step l：在字串上均勻的選擇兩點(diǎn)，由這兩點(diǎn)定義的子串稱為映射段； Step 2：交換雙親的兩個(gè)子串，產(chǎn)生原始后代； Step 3：確定兩映射段之間的關(guān)系； Step 4： 根據(jù)映射關(guān)系將后代合法化。在這種情況下，群體中實(shí)際上已不存在競(jìng)爭(zhēng)，從而搜索目標(biāo)難以得到改善，出現(xiàn)了停滯現(xiàn)象。遺傳算法正是基于適應(yīng)度對(duì)個(gè)體進(jìn)行選擇，以保證適應(yīng)性好的個(gè)體有機(jī)會(huì)在下一代中產(chǎn)生更多的子個(gè)體。例如 7和 8的二進(jìn)制編碼分別為 0111和 Hamming懸崖（ Hamming cliffs） ,有可能降低遺傳算法的搜索效率。 神經(jīng)網(wǎng)絡(luò) 遺傳算法的另一個(gè) 活躍的研究方向是在神經(jīng)網(wǎng)絡(luò)方面的應(yīng)用，這包括優(yōu)化神經(jīng)網(wǎng)絡(luò)的連接權(quán)系數(shù)、網(wǎng)絡(luò)的空間結(jié)構(gòu)等。初始群體群體的染色體數(shù)量應(yīng)適當(dāng)選擇。這種點(diǎn)到點(diǎn)的搜索方法在多峰值優(yōu)化問(wèn)題中，容易誤入局部最優(yōu)解。三者分述如下： 硬時(shí)間窗 (Hard Time Windows)：指配送車必須在特定時(shí)間區(qū)段 (如圖 21中的 ? ?le, )內(nèi)將貨品送達(dá)顧客手中，不論是遲到或早到都完全不予接受。 亞啟發(fā)式算法包括表搜索算法 (Table Search)、模擬退火算法 (Simulated Annealing)、遺傳算法 (Geic Algorithm)和神經(jīng)網(wǎng)絡(luò) (Neural Networks)方法。 算法 貨運(yùn)車輛優(yōu)化調(diào)度問(wèn)題的求解方法非常 豐富，目前主要有以下四類： 系統(tǒng)仿真法 (Simulation ) 此方法最早由 Golden 和 Skiscim 于 1986 年提出，主要應(yīng)用于行車線路與物流中心區(qū)位的選擇，優(yōu)點(diǎn)在于可直接觀察系統(tǒng)安排的效率與效果，但由于問(wèn)題的實(shí)際情況多變且具有不確定性，是否能將實(shí)際的配送情形系統(tǒng)邏輯化為仿真程序，往往令人質(zhì)疑。張震 (1995)針對(duì)單車場(chǎng)滿載問(wèn)題，提出了考慮運(yùn)輸行程約束的優(yōu)化方法。 圖 11 配送流程圖 在傳統(tǒng)的配送系統(tǒng)中，由于商品的需求量及種類較少，零售商可憑借較多的存貨及較常的定貨周期來(lái)減少供貨商的配送頻率，以降低運(yùn)輸成本。 對(duì)于有時(shí)間窗的非滿載 VSP 問(wèn)題，將貨運(yùn)量約束和軟時(shí)間窗約束轉(zhuǎn)化為目標(biāo)約束，建立了非滿載VSP模型，設(shè)計(jì)了基于自然數(shù)編碼，使用最大 保留交叉、改進(jìn)的反轉(zhuǎn)變異等技術(shù)的遺傳算法。物流配送開始在我國(guó)迅速興起發(fā)展起來(lái)，對(duì)物流配送的研究引起了國(guó)內(nèi)物流專家學(xué)者的廣泛關(guān)注。假設(shè)零售商與供應(yīng)商之間通過(guò)一個(gè)物流配送中心來(lái)配送，則只需 i+j 次配送，如圖 13所示，如此一來(lái)即可減少 (ij(i+j))的配送次數(shù)，當(dāng)供應(yīng)商與零售商數(shù)目越多，節(jié)省的配送次數(shù)也就會(huì)越多。 按任務(wù)特征分，有純裝問(wèn)題或純卸題 (pure pick up or pure delivery, 車輛在所有任務(wù)點(diǎn)裝貨或卸貨，及集貨或送貨問(wèn)題 ) 及裝卸混合問(wèn)題 (bined pick up and delivery，每項(xiàng)任務(wù)有不同的裝貨點(diǎn)和卸貨點(diǎn)，即集貨、送貨一體化問(wèn)題 )。該方法在解題時(shí)可減少搜尋的次數(shù)，所以是一種容易且快速的求解困難問(wèn)題的算法。 滿載車輛優(yōu)化調(diào)度問(wèn)題 當(dāng)貨主的貨物量不小于車輛容量時(shí)，執(zhí)行每項(xiàng)任務(wù)需要的車輛可能不只一輛，車輛為完成任務(wù)，需 滿載運(yùn)行。 t e l ??tP M 10 圖 22 軟時(shí)間窗約束示意圖 混合型時(shí)間窗 (Mixed Time Windows )：系統(tǒng)中有些顧客屬于硬時(shí)間窗，有些則屬于軟時(shí)間窗；同一顧客，往往軟、硬兩種時(shí)間窗混合使用。 算法具有極強(qiáng)的容錯(cuò)能力。父代的遺傳基因的結(jié)合是通過(guò)父代染色體之間的交叉并到達(dá)下一代個(gè)體的。Ochi 和 Luiz 1998 )，但僅僅是開始嘗試階段，還有待于進(jìn)一步的研究。 一個(gè) n 階 Gray碼是一個(gè)由所有 n位二進(jìn)制位串組成的有序循環(huán)序列，使得相鄰的位串之間恰有一位不同。一般可采用以下的方法進(jìn)行轉(zhuǎn)換： ? ? ? ?轉(zhuǎn)換前轉(zhuǎn)換后 kk fM A Xf ?? 其中 MAX為一常數(shù)，最好與群體無(wú)關(guān)，一般可以由下列四種方式?jīng)Q定 : 任意足夠大的正數(shù)。 標(biāo)準(zhǔn)差祛除法 此方法是利用平均適應(yīng)度函數(shù)與其標(biāo)準(zhǔn)差間的差異來(lái)修正原個(gè)體的適應(yīng)度，以解決線性定標(biāo)會(huì)產(chǎn)生負(fù)值的問(wèn)題，是線性定標(biāo)前的一個(gè)預(yù)處理方法，但計(jì)算上比較復(fù)雜。 圖 34 說(shuō)明了交叉過(guò)程，同樣步驟可產(chǎn)生另一個(gè)后代 [4 2 3 1 5 6 7 8 9]。 2— 交換和 3— 交換說(shuō)明分別示于圖 39和圖 310中。 問(wèn)題描述 一般車輛優(yōu)化調(diào)度問(wèn)題可描述為：一個(gè)物流配送中心使用載重量相同的多輛汽車完成多個(gè)貨物需求點(diǎn)的配送任務(wù)。求滿足貨運(yùn)要求的費(fèi)用最少的車輛行使線路。 采用懲罰的方法來(lái)處理約束。若車輛在 ia 之前到達(dá)點(diǎn) i，則車輛在此等待，發(fā)生了機(jī)會(huì)成本損失。 有時(shí)間窗的 VSP 則是在一般車輛優(yōu)化調(diào)度問(wèn)題的基礎(chǔ)上要求每項(xiàng)任務(wù) i 在時(shí)間范圍? ?ii ba, 內(nèi)完成，并可根據(jù)時(shí)間約束的嚴(yán)格與否，分為軟時(shí)間窗和硬時(shí)間窗的 VSP。建議的最優(yōu)參數(shù)范圍是30~20?n , ~?cp , ~?mp 。目前發(fā)展的主要變異算子如表 32所示。 由于染色體復(fù)制后，當(dāng)前群體中最佳染色體可能喪失繁殖能力，為了提高遺傳算法的性能，可在使用輪盤賭的基礎(chǔ)上采用最佳保留策略。因此，個(gè)體繁殖數(shù)量的調(diào)節(jié)在遺傳操作中就顯得比較重要。 排列編碼 對(duì)于某些問(wèn)題，排列是其解的一種自然的表示。下面是幾種常用的編碼方法。目前在運(yùn)籌學(xué)、機(jī)械優(yōu)化設(shè)計(jì)、電網(wǎng)設(shè)計(jì)、生產(chǎn)管理等應(yīng)用學(xué)科中都嘗試著用遺傳算法解決現(xiàn)實(shí)優(yōu)化計(jì)算問(wèn)題。 與傳統(tǒng)方法相比，遺傳算法的優(yōu)越性主要表現(xiàn)在：首先，在遺傳算子的作用下，遺傳算法具有很強(qiáng)的搜索能力，能以很大的概率找到 問(wèn)題的全局最優(yōu)解：其次，由于它固有的并行性，能有效地處理大規(guī)模的優(yōu)化問(wèn)題。 有時(shí) 間窗約束的車輛優(yōu)化調(diào)度問(wèn)題可以用圖 24表示： 圖 24 VSPTW問(wèn)題的結(jié)構(gòu) 第 3 章 遺傳算法基本理論 遺傳算法的基本原理 遺傳算法是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法，它由美國(guó)Holland教授首先在《自然結(jié)合人工智能系統(tǒng)的適應(yīng)性》一書中提出，是利用生物進(jìn)化的特性所發(fā)展的方法，由一群群體 (Population)以隨機(jī)配對(duì)產(chǎn)生下一代，利用交叉 (Crossover)及變異 (Mutation)等操作進(jìn)行基因的進(jìn)化，并經(jīng) 由選擇 (Selection)機(jī)能決定下一代相對(duì)的旅行商問(wèn)題 一般車輛優(yōu)化調(diào)度問(wèn)題 有時(shí)間窗約束的車 輛優(yōu)化調(diào)度問(wèn)題 加入車輛裝載能力約束 加入時(shí)間窗約束 12 個(gè)數(shù)，使適應(yīng)度越大的解存活的機(jī)會(huì)越大；也就是“適者生存”的原則來(lái)選擇隨機(jī)的值域，最后留下的就是最優(yōu)解。因此，在配送運(yùn)輸上，時(shí)間因素是十分重要的。 在兩階段法求解過(guò)程中，常常采用交互式優(yōu)化技術(shù)，把人的主觀能動(dòng)作用結(jié)合到問(wèn)題的求解過(guò)程中，其主要思想是：有經(jīng)驗(yàn)的決策者具有對(duì)結(jié)果和參數(shù)的某種判斷能力，并且根據(jù)知識(shí)直感，把主觀的估計(jì)加到優(yōu)化模型中去。 按優(yōu)化目標(biāo)數(shù)來(lái)分，有單目標(biāo)問(wèn)題和多目標(biāo)問(wèn)題。 國(guó)外對(duì)物流配送車輛優(yōu)化調(diào)度問(wèn)題作了大量而深入的研究，例如早在 1983 年 Bodin, Golden 等人在他們的綜述文章中就列舉了 700余篇文獻(xiàn)。 雖然 我國(guó)物流發(fā)展 持 續(xù)加速，但與國(guó)民經(jīng)濟(jì)發(fā)展的要求 還 相差甚遠(yuǎn) ，這就要求我們對(duì)物流產(chǎn)業(yè)的各個(gè)環(huán)節(jié)進(jìn)行研究。 I 摘 要 近年來(lái)，物流作為“第三方利潤(rùn)的源泉”受到國(guó)內(nèi)各行業(yè)的極大重視并得到了較大的發(fā)展。 據(jù)中國(guó)物流信息中心統(tǒng)計(jì)測(cè)算， 2021 年，全國(guó)社會(huì)物流總額達(dá) 萬(wàn)億元，同比增長(zhǎng) %(按現(xiàn)價(jià)計(jì)算 )，增幅比上年同期提高 個(gè)百分點(diǎn)。各學(xué)科專家對(duì)該問(wèn)題進(jìn)行了大量的理論研究及實(shí)驗(yàn)分析，取得了很大的進(jìn)展。 按車輛對(duì)車場(chǎng)的所屬關(guān)系分，有車輛開放問(wèn)題 (車輛可以不返回其發(fā)出車場(chǎng) )和車輛封閉問(wèn)題 (車輛必須返回其發(fā)出車場(chǎng) )。一般第一階段常用構(gòu)造算法，在第二階段常用的改進(jìn)技術(shù)有 2opt(Lin，1965)、 3opt(Lin Kernighan， 1973)和 Oropt(Or， 1976)交換法，這是一種在解的鄰域中搜索，對(duì)初始解進(jìn)行某種程度優(yōu)化的算法，以改進(jìn)初始解。由于消費(fèi)者需求趨于多樣化，對(duì)送貨時(shí)間的要求日趨嚴(yán)格，尤其是運(yùn)送有時(shí)效性的商品，例如海鮮、花卉、蔬菜、水果等講究新鮮度的貨物，除了因缺貨造成的機(jī)會(huì)成本的損失外，由于配送不及時(shí)也會(huì)造成貨物價(jià)值的大大降低。 行程安排 (Scheduling)問(wèn)題 一般車輛優(yōu)化調(diào)度問(wèn)題再加入時(shí)間窗約束，則必須考慮到達(dá)各顧客的先后順序，也就是行程安排問(wèn)題。復(fù)制體現(xiàn)了向最優(yōu)解的逼近，交叉體現(xiàn)了最優(yōu)解的產(chǎn)生，變異體現(xiàn)了全局最優(yōu)解的覆蓋。對(duì)于復(fù)雜的函數(shù)優(yōu)化問(wèn)題 (如非線性、不連續(xù)、多峰 值函數(shù)的優(yōu)化等 )和組合優(yōu)化問(wèn)題 (如 VSP, TSP,01 背包問(wèn)題、工作計(jì)劃問(wèn)題 確定表示問(wèn)題解答的染色體（編碼） 初始化染色體種群 計(jì)算每個(gè)染色體的適應(yīng)度 滿足終止條件？ 根據(jù)適應(yīng)度選擇串進(jìn)行復(fù)制 交叉 變異 輸出最優(yōu)解 否 是 14 制定等 )都有廣闊的發(fā)展前景。設(shè)計(jì)優(yōu)良的編碼方案是遺傳算法的應(yīng)用難點(diǎn)之一。這樣，可以直接在解的表現(xiàn)型上操作，從而便于引入與問(wèn)題領(lǐng)域相關(guān)的啟發(fā)式信息，增加遺傳算法的搜索能力。為了保證適應(yīng)度函數(shù)為非負(fù)，可以采用如下的轉(zhuǎn)化形式： ? ? ? ?轉(zhuǎn)換前轉(zhuǎn)換后 kkk fff /?? 適應(yīng)度定標(biāo) 在設(shè)計(jì)遺傳算法時(shí)，群體的規(guī)模一般在幾十至幾百，與實(shí)際物種的規(guī)模相差很遠(yuǎn)。適應(yīng)度比例方法是目前遺傳算法中最基本也是最常用的復(fù)制方法，它也叫輪盤賭復(fù)制法或蒙特卡羅復(fù)制，其具體步驟如下： Step l：對(duì)各個(gè)染色體 kv 計(jì)算適應(yīng)度 kf ； Step 2：計(jì)算種群中 n個(gè)染色體適應(yīng)度的和 ???nk kfF 1； Step 3：對(duì)各染色體 kv ，計(jì)算選擇概率 Ffp kk /? nk ,2,1 ?? ； Step 4：對(duì)各染色體 kv 計(jì)算累計(jì)概率 ???nj jk pq 1nk ,2,1 ?? 復(fù)制過(guò)程類似旋轉(zhuǎn)轉(zhuǎn)輪 n次，每次按如下方式選出一個(gè)染色體來(lái)構(gòu)造新的種群，具體過(guò)程為：在 ? ?1,0 區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的偽隨機(jī)數(shù) r，若： 1qr? ，則選擇第一個(gè)染色體 1v ；否則選擇第 k個(gè)染色體 ? ?nkvk ?,2? ，使得 kk qrq ???1 成立。變異在遺傳算法中的作用是第二位的 ［３］［５］ 。一般，當(dāng)種群規(guī)模增大時(shí)，將有利于改善種群的多樣性，從而可能有利于使算法收斂到最優(yōu)解或最優(yōu)解附近。又如，若干廠家生產(chǎn)一些產(chǎn)品，需要運(yùn)到配送中心，車輛從配送中心出發(fā)，到各廠家去裝貨，裝滿貨后返回配送中心，在滿足 廠家發(fā)貨要求的情況下，按什么線路行駛，可使總費(fèi)用最小，即集貨車輛優(yōu)化調(diào)度。懲罰成本函數(shù)的設(shè)定一般以配送中心與顧客在商議之后所簽定的合同為主，但因?qū)嶋H上所簽定合同是為維護(hù)買賣雙方共同的利益，故考慮的因素相當(dāng)多。如果一個(gè)染色體對(duì)應(yīng)的解違反了某個(gè)約束，試其違反程度給予一定懲罰，使其具有較小的適應(yīng)度。此問(wèn)題稱之為有時(shí)間窗的車輛優(yōu)化調(diào)度問(wèn)題。每個(gè)需求點(diǎn) (供貨點(diǎn) )的需求量 (供貨量 )已知，且都小于配送車輛的載重量；配送中心和各需求點(diǎn)中任意兩點(diǎn)間的運(yùn)距已知或可以推算出來(lái)；一個(gè)需求點(diǎn)的任務(wù) 只能由一輛車一次運(yùn)送完成；每個(gè)配送車輛從配送中心出發(fā)，完成運(yùn)送任務(wù)后返回配送中心。 圖 39 2— 交換變異的說(shuō)明 隨機(jī)選擇一個(gè)子巡回 5 4 3 9 8 1 7 6 2 插入到一個(gè)隨機(jī)位置 5 4 3 7 8 6 2 9 1