遺傳算法在配送中心選址中的應(yīng)用

摘要：配送中心是現(xiàn)代物流的重要組成部分，它在整個(gè)物流系統(tǒng)中起著承上啟下的作用，如何合理的選擇配送中心就顯得尤為關(guān)鍵。本文提出了一種新的二進(jìn)制和浮點(diǎn)數(shù)混合編碼的改進(jìn)遺傳算法。該算法對(duì)種群初始化函數(shù)和遺傳操作做相應(yīng)的改進(jìn)，使得表示配送中心選址的決策變量只能在0或1這兩個(gè)離散變量上選擇，解碼更加方便，大大提高了運(yùn)算效率，改進(jìn)的遺傳算法能夠很好的解決物流配送中心的選址問(wèn)題。

關(guān)鍵詞：配送中心；遺傳算法；選址；混合編碼

中圖分類號(hào)：F273文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1002-3100(2007)04-0111-03

Abstract: Distribution center is an important part of modern logistics and plays the leading role in it. How to locate the distribution center appears to be very important. An improved genetic algorithm is introduced which uses the mixed coding of binary and float number. An relevant improvement is made to the population initialization function and inheritance operator and then the decision variables denoting the address of distribution center can only be selected between zero and one， so the decoding is more convenient and the calculation efficiency is greatly improved. The problem of distribution center location can well be solved with the improved genetic algorithm.

Key words: distribution center; genetic algorithm; location; mixed coding

隨著供應(yīng)鏈管理思想在我國(guó)的傳播，物流服務(wù)的重要性越來(lái)越為人們所關(guān)注，尤其是第三方物流的蓬勃發(fā)展更是使“第三利潤(rùn)源”的觀念深入人心。配送中心是現(xiàn)代物流的重要組成部分，其上游是制造商，下游是用戶，它在整個(gè)物流系統(tǒng)中起著承上啟下的作用。合理地選擇配送中心地址可以有效節(jié)省費(fèi)用，促進(jìn)生產(chǎn)和消費(fèi)兩種流量的協(xié)調(diào)和配合，保證物流系統(tǒng)的高效和平衡發(fā)展，是物流系統(tǒng)分析中最重要的一塊。同時(shí)，合理的配送中心能使物流系統(tǒng)有效運(yùn)作，給企業(yè)提供專業(yè)化、個(gè)性化、高質(zhì)高效、完善的增值物流服務(wù)，降低成本，增加企業(yè)的利潤(rùn)，成為企業(yè)生存發(fā)展、增加發(fā)展?jié)摿?、保持?jìng)爭(zhēng)力的重要保證。

物流配送中心選址研究已經(jīng)有很多方法，大致分為定性和定量?jī)纱箢?。定性的方法主要是層次分析法和模糊綜合評(píng)價(jià)法；定量的方法主要有重心法、Cluster法、CFLP法、0-1整數(shù)規(guī)劃法等。物流配送中心選址問(wèn)題屬于優(yōu)化問(wèn)題即成本最小化，遺傳算法用于求解連續(xù)變量的優(yōu)化問(wèn)題是比較方便的，由于配送中心選址模型中的變量眾多復(fù)雜，因此無(wú)法直接利用標(biāo)準(zhǔn)的遺傳算法。本文介紹一種處理此類問(wèn)題的簡(jiǎn)單易行的方法即在標(biāo)準(zhǔn)遺傳算法的基礎(chǔ)上，根據(jù)模型中變量的特點(diǎn)，使表示配送中心的決策變量只能在0-1這兩個(gè)數(shù)上取值，表示運(yùn)輸量的變量采用浮點(diǎn)數(shù)編碼，從而避免了問(wèn)題的復(fù)雜性，很好地解決配送中心的選址問(wèn)題。

1配送中心選址問(wèn)題及其模型

物流配送中心選址問(wèn)題可以描述如下：有m個(gè)供應(yīng)基地，n個(gè)容量有限制的備選配送中心和l個(gè)用戶；供應(yīng)基地到配送中心、配送中心到用戶的運(yùn)費(fèi)均為運(yùn)輸量的線性函數(shù)；配送中心的可變成本為流量的凹函數(shù)；由于資金限制，選擇的配送中心總數(shù)限制為P，如何選擇使總成本最小。該問(wèn)題的數(shù)學(xué)模型如下：

約束條件如下：

2遺傳算法在配送中心選址中的應(yīng)用

遺傳算法已被廣泛應(yīng)用于優(yōu)化問(wèn)題的求解，尤其是求最小值或最大值問(wèn)題。遺傳算法求解優(yōu)化問(wèn)題的一般流程如圖所示。

配送中心的選址問(wèn)題就是帶有眾多約束的、求解成本最小化的優(yōu)化問(wèn)題。本文在標(biāo)準(zhǔn)遺傳算法的基礎(chǔ)上，提出了新的編碼方法，使得表示配送中心選址的決策變量只能在0-1這兩個(gè)離散變量上選擇，表示運(yùn)輸量的變量就用實(shí)值，解碼更加方便，大大提高了運(yùn)算效率。

2.1編碼方法

2.2遺傳算子

標(biāo)準(zhǔn)遺傳算法的操作算子一般都包括選擇、交叉和變異三種基本形式，它們構(gòu)成了遺傳算法具備強(qiáng)大搜索能力的核心。

2.3對(duì)約束的處理

在配送中心選址問(wèn)題的數(shù)學(xué)模型中約束條件較多，所采用的編碼方式中不可行解在群體中比例很大，所以采用懲罰策略。罰函數(shù)法的基本思想是對(duì)解空間中無(wú)對(duì)應(yīng)可行解的個(gè)體計(jì)算適應(yīng)度時(shí)，處以一個(gè)罰函數(shù)，從而降低該個(gè)體的適應(yīng)度，使該個(gè)體被遺傳到下一代群體中的概率減小。

2.4適應(yīng)度函數(shù)

在遺傳算法中使用適應(yīng)度來(lái)度量群體中各個(gè)個(gè)體在優(yōu)化計(jì)算中能達(dá)到或接近于最優(yōu)解的優(yōu)良程度。度量個(gè)體適應(yīng)度的函數(shù)稱為適應(yīng)度函數(shù)。適應(yīng)度函數(shù)也稱為評(píng)價(jià)函數(shù)，是根據(jù)目標(biāo)函數(shù)確定用于區(qū)分群體中個(gè)體好壞的標(biāo)準(zhǔn)。

3實(shí)例

4結(jié)論

對(duì)于物流企業(yè)而言，網(wǎng)絡(luò)中的設(shè)施選址是最重要的物流均衡戰(zhàn)略規(guī)劃問(wèn)題。文中的模型不僅考慮了運(yùn)輸成本，還考慮了配送中心的可變運(yùn)營(yíng)成本，因此具有較好的實(shí)用性。遺傳算法在配送中心選址中的應(yīng)用取得了較好的效果，該模型不僅可以用于配送中心選址問(wèn)題，還可以用于企業(yè)選擇銷(xiāo)售、儲(chǔ)備中心等問(wèn)題中。

參考文獻(xiàn)：

[1] 玄光南，程潤(rùn)偉. 遺傳算法與工程優(yōu)化[M]. 北京：清華大學(xué)出版社，2004.

[2] Davis L. Handbook of Genetic Algorithm[M]. New York: Nostrand Reinhold， 1991.

[3] 黎鈞琪. 改進(jìn)遺傳算法及其在物流配送中心選址優(yōu)化的應(yīng)用[D]. 武漢：武漢理工大學(xué)（碩士學(xué)位論文），2001.

[4] 吳堅(jiān)，史忠科. 基于遺傳算法的配送中心選址問(wèn)題[J]. 華南理工大學(xué)學(xué)報(bào)，2004(6):71-74.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”