【文章內(nèi)容簡介】 輛行駛的距離、車輛運(yùn)行的時間和相關(guān)成本等。（5）貨物，,一類是人,一類是物,物的這一類統(tǒng)稱為貨物。在本文中，指城市社區(qū)超市配送的貨物。（6）限定條件，指客戶所需要的貨物的種類、數(shù)量；客戶對時間的要求；車輛的通行時間；車輛的最大行駛距離（指來回的總距離）和最大載貨量。（7）車輛路徑的優(yōu)化目標(biāo)，指通過路徑優(yōu)化要達(dá)到的目的，如油耗量最少、路徑最短、時間合理、客戶滿意等。 車輛路徑問題的基本類型車輛路徑問題概念出現(xiàn)后，國內(nèi)外學(xué)者對VRP進(jìn)行了多種分類。根據(jù)研究重點(diǎn)的不同，VRP可以產(chǎn)生很多模型，這些模型有不同的分類方式?？傮w來說有以下分類：（1） 根據(jù)車場（配送中心、倉庫等）劃分，分為多車場和單車場問題。本文了研究單配送中心車輛路徑問題，即所有車輛從一個配送中心出發(fā)；也研究了多配送中心為題，即雙配送中心車輛路徑問題，車輛從兩個配送中心出發(fā)。（2） 根據(jù)配送車輛的型號劃分，可以分為單車型車輛路徑問題和多車型車輛路徑問題，本文重點(diǎn)研究單車型車輛路徑問題。（3） 根據(jù)客戶對車輛達(dá)到時間來劃分，可以分為無時間要求的車輛路徑問題和帶時間窗的車輛路徑問題。帶時間窗的車輛路徑問題又可以分軟時間窗問題和硬時間窗問題，硬時間窗車輛路徑問題對時間要求非常嚴(yán)格，必須在指定時間到達(dá)配送收貨點(diǎn)，早到或者晚到都會被拒絕；軟時間窗車輛路徑問題要求配送車輛在客戶要求的時間范圍內(nèi)到達(dá)，在規(guī)定范圍提前到或者遲到，則需要承擔(dān)一定的懲罰費(fèi)用。本文主要研究無時間限制的車輛路徑問題和軟時間窗車輛路徑問題。（4） 按照車輛載重情況劃分，可以分為滿載和非滿載車輛路徑問題。本文主要研究兩者的混合裝載問題，即盡量滿載，可以出現(xiàn)非滿載情況。（5） 按照配送任務(wù)劃分，可以分為送貨配送，收貨配送，送貨和收貨同時進(jìn)行的車輛路徑問題。（6） 按照配送車輛是否返回配送中心劃分，可以分為封閉式車輛路徑問題（配送車輛從配送中心出發(fā)并且返回配送中心）和開放式車輛路徑問題（配送車輛從配送中心出發(fā)但是不返回配送中心）。本文重點(diǎn)研究封閉式車輛路徑問題。 車輛路徑問題的求解算法車輛路徑問題屬于NP問題，求解該問題的算法主要是精確算法和啟發(fā)式算法。精確算法是通過有限計(jì)算和推理得到的路徑優(yōu)化問題的最優(yōu)解算法，一般包括割平面算法、動態(tài)規(guī)劃算法、網(wǎng)絡(luò)流法等。啟發(fā)式算法是通過對以往經(jīng)驗(yàn)的總結(jié)歸納或者通過實(shí)驗(yàn)仿真來解決問題的方法，啟發(fā)式算法不是最求最優(yōu)解，而是相對滿意的次優(yōu)解。啟發(fā)式算法一般包括傳統(tǒng)啟發(fā)式算法和現(xiàn)代啟發(fā)式算法。傳統(tǒng)啟發(fā)式算法主要有節(jié)約算法、插入算法、兩階段啟發(fā)式算法、掃描算法等；現(xiàn)代啟發(fā)式算法主要有遺傳算法、禁忌搜索算法、模擬退火算法、蟻群算法、粒子群算法、量子進(jìn)化算法等。遺傳算法是一種在自然選擇和生物進(jìn)化的基礎(chǔ)上，運(yùn)用計(jì)算機(jī)模擬生物群在自然進(jìn)化過程中基因的選擇、交叉、變異，進(jìn)而香型的一種智能優(yōu)化搜索算法。 遺傳算法的相關(guān)概念基因在遺傳算法中的基本單元就是基因，可以表示為X=x1,x2...xn,根據(jù)不同的問題，基因可以分為二進(jìn)制串，整數(shù)串，實(shí)數(shù)串等。 編碼和解碼在實(shí)際應(yīng)用中，需要把實(shí)際問題的解轉(zhuǎn)化為遺傳的解。編碼就是將普通的模型轉(zhuǎn)化到基因模型，這樣就把實(shí)際的問題轉(zhuǎn)化為遺傳算法可以解決的問題；解碼是與編碼相反的過程，即將遺傳算法解決的方案轉(zhuǎn)化實(shí)際的問題解。 種群種群就是許多基因的集合。遺傳算法解決實(shí)際問題的過程中，從隨機(jī)選擇的個體初始解開始進(jìn)行地帶搜索，初始解的集合和每次迭代生成新的解就形成了一個種群。種群的規(guī)模大小代表所含基因的數(shù)量所以種群的大小取值很重要，種群規(guī)模越大運(yùn)行速度越慢。 適應(yīng)度函數(shù)為了尋找最優(yōu)個體，必須對個體位串進(jìn)行適應(yīng)性評價。因此，適應(yīng)度函數(shù)就構(gòu)成了個體的生存環(huán)境。根據(jù)個體的適應(yīng)值就可以決定它在次環(huán)境的生存能力。一般來說，好的染色體串結(jié)構(gòu)具有比較高的適應(yīng)度函數(shù)值，可以獲得較高的評價，具有較強(qiáng)的生存能力。遺傳算子遺傳算法的進(jìn)化通過遺傳算子的作用逐代進(jìn)化。標(biāo)準(zhǔn)的遺傳算子包括選擇算子、交叉算子和變異算子三種基本形式。 選擇算子選擇的作用是是從種群中選擇優(yōu)秀的個體，使它出現(xiàn)在下一代中，一般適應(yīng)度函數(shù)越高的個體，出現(xiàn)在下一代的概率越大。選擇算子能提高種群的適應(yīng)度平均值，但是不影響個體的適應(yīng)度值。選擇算子的作用是保存對解決問題有用的遺傳信息，可以影響遺傳算法的整體結(jié)果。選擇算子種類繁多，根據(jù)不用的選擇方式可以產(chǎn)生不同的結(jié)果。一般來說，最常見選擇方法是轉(zhuǎn)輪盤法。隨機(jī)選擇、優(yōu)勢個體保留等。 交叉算子利用遺傳算法解決實(shí)際問題的過程中，在種群中選擇一對個體進(jìn)行交配；根據(jù)位串的長度對要交配的個體隨機(jī)選擇1到L長度的位置作為雜交位置；根據(jù)雜交概率實(shí)施雜交，配對的給提在雜交位置處，相互交換各自的部分基因，最后形成一對新個體。 變異算子 變異算子根據(jù)生物進(jìn)化染色體某位基因的突變，從而改變?nèi)旧w結(jié)構(gòu)和特征的特性，在利用遺傳算法節(jié)約實(shí)際問題的過程中，主要目的是保持種群的多樣性，避免過早收斂。 遺傳算法的流程遺傳算法在整個進(jìn)化過程中的遺傳操作是隨機(jī)性的，但是它所沉陷的特性并不是完全隨機(jī)搜索，它能有效利用歷史信息來推測下一代期望性能所有的尋優(yōu)點(diǎn)集。這樣一代代不斷進(jìn)化，最后收斂到一個最適應(yīng)環(huán)境的個體上，求得問題的最優(yōu)解。遺傳算法所涉及的五大要素：參數(shù)編碼、初始群體設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作的設(shè)計(jì)和控制參數(shù)的設(shè)定。遺傳算法的運(yùn)行過程是一個典型的迭代過程，其必須完成的工作內(nèi)容基本步驟如下： 選擇編碼策略，把參數(shù)集合X和域轉(zhuǎn)換為串結(jié)構(gòu)空間S； 定義適應(yīng)值函數(shù)f(x) 確定遺傳策略，包括選擇群體大小n，選擇、雜交、變異方法，以及確定雜交概率pc、變異概率pm等遺傳參數(shù)； 隨機(jī)初始化生成群體P； 計(jì)算群體中個體位穿解碼后的適應(yīng)值f(x)。 按照遺傳策略，運(yùn)用選擇、雜交和變異算子作用于新后代形成下一代。 判斷群性能是否滿足某一指標(biāo)，或者已完成預(yù)定迭代次數(shù)，如果不滿足則返回步驟（6），或者修改遺傳策略再返回步驟（6）。 遺傳算法的特點(diǎn) 與傳統(tǒng)的優(yōu)化算法相比，遺傳算法主要有有以下特點(diǎn)：遺傳算法不是直接作用在參變量集上，而是利用參變量集的某種編碼。遺傳算法不是從單個點(diǎn)，而是從一個點(diǎn)的群體開始搜索。遺傳算法利用適應(yīng)值信息，無須導(dǎo)數(shù)和其他輔助信息。遺傳算法利用概率轉(zhuǎn)移規(guī)則，而不是確定性規(guī)則。遺傳算法的主要優(yōu)點(diǎn)是它在搜索過程中不容易陷入局部最優(yōu)，即使在所定義的函數(shù)是不連續(xù)的。非規(guī)則的情況下，它也能以很大的概率找到整體最優(yōu)解；其次，由于它的固有的并行性，遺傳算法使用于大規(guī)模車輛路徑計(jì)算。3遺傳算法在 LS物流公司城市社區(qū)超市配送運(yùn)作現(xiàn)狀與問題重慶LS物流有限公司成立于2012年，注冊資金8000萬元，是一家專業(yè)致力于服務(wù)重慶及全國范圍內(nèi)干線運(yùn)輸、倉儲、配送等一體化物流服務(wù)、物流方案設(shè)計(jì)、大件運(yùn)輸、軍品運(yùn)輸、商品貿(mào)易及供應(yīng)鏈金融服務(wù)的物流企業(yè)。公司先后為宗申集團(tuán)、嘉陵集團(tuán)、濰柴動力、潤通動力、兩江機(jī)械、珠峰大江、佳速汽配、大江信達(dá)、瑞方渝美、特發(fā)信息、重慶羅森等客戶開展民品全國干線運(yùn)輸、倉儲、商品批發(fā)與代理、冷鏈物流及城市商超配送業(yè)務(wù)。 城市社區(qū)超市配送存在的問題 隨著城市社區(qū)超市配送企業(yè)的競爭加劇，城市社區(qū)超市物流企業(yè)面臨著減小訂單響應(yīng)時間、降低物流運(yùn)輸成本以及提高客戶滿意度等的壓力。為了能夠在競爭激烈的市場生存，物流企業(yè)必須改善自己的物流配送體系，才能滿足市場需求。配送路徑的的規(guī)劃是物流配送的核心，超市配送企業(yè)對其非常重視。但是，大多數(shù)物流公司在規(guī)劃配送路線時，只考慮了一般情況，而沒有考慮客戶的臨時要求和多配送中心的問題，這可能造成配送路線的局部優(yōu)化，沒要達(dá)到系統(tǒng)優(yōu)化的目的。 LS物流公司配送信息系統(tǒng)難以達(dá)到配送要求 LS物流公司原來是某國有企業(yè)的一個部門，后來發(fā)展為股份制有限公司。由于受到傳統(tǒng)觀念和以前公司制度的固定思維的約束，配送模式陳舊，配送效率緩慢，耗費(fèi)高。公司的資源配置不合理，在物流信息系統(tǒng)、物流車輛路徑規(guī)劃和決策等軟件方面投入不足，導(dǎo)致信息系統(tǒng)落后，物流規(guī)劃混亂，車輛調(diào)度不合理等。物流新技術(shù)的應(yīng)用不足，大多停留在分散的、低水平層面、不能綜合、系統(tǒng)地應(yīng)用新的物流技術(shù)。缺乏高效的信息指揮系統(tǒng)，不能隨時對車輛配送進(jìn)行監(jiān)控和調(diào)節(jié)路線。配送人員只能在設(shè)定的路線配送，盲目性強(qiáng)。 LS物流公司物流管理落后根快速消費(fèi)品的配送要求比較高，城市社區(qū)超市每天需求的物品更新速度快，而LS物流公司的配送商品的更新速度慢，滿足不了社區(qū)超市的靈活性要求。城市社區(qū)超市商品的配送效率受到配送中心、車輛配送路線安排以及調(diào)度的影響。而LS物流公司配送路線固定，配送中心與配送車輛之間的協(xié)調(diào)度低，導(dǎo)致滿載車輛的數(shù)目，空載情況經(jīng)常發(fā)生，車輛的適用效率不高。沒有專門的人員協(xié)調(diào)配送中心的選址和配送路線的合理制定，導(dǎo)致物流配送管理體系混亂，配送人員與管理人員之間的溝通不足，難以對實(shí)際配送問題作出有效的解決方案。 總結(jié) 本章主要是對LS物流公司的基本情況進(jìn)行介紹，通過分析社區(qū)超市物流公司配送過程中存在的問題。305 發(fā)展重慶市電子電器廢棄物回收網(wǎng)絡(luò)的建議4 LS物流公司社區(qū)超市配送路徑優(yōu)化中VRP模型構(gòu)建與遺傳算法的應(yīng)用 車輛路徑問題的數(shù)學(xué)模型無時限單配送中心TSP問題，即不考慮客戶對貨物送達(dá)時間限制的單配送中心車輛路徑問題。該問題可以描述為：在配送中心地理位置、客戶地理位置和需求量抑制的條件下，要求從單配送中心派出多輛車為所有客戶提供配送服務(wù)，要求完成所有配送任務(wù)的車輛行駛總里程最短，并滿足條件：車輛由配送中心出發(fā)，最終返回該配送中心；所有客戶的需求必須得到滿足，每個客戶只能由一輛車提供服務(wù)，且僅被服務(wù)一次；每條配送路線上，貨物的配送量之和不能超過配送車輛的最大載重量，并且運(yùn)行距離不得超過該車的最大行駛距離。其中，式（1）目標(biāo)函數(shù)，表示服務(wù)完所有客戶所需行駛的總里程最短；式（2）確保每輛配送車輛的載重量（即該車所服務(wù)所有客戶需求量之和）不得超過該車的最大承載量；式（3）表示配送車輛的配送行程不得超過該車的最大行駛距離；式（4）表示車輛從配送中心出發(fā)并返回配送中心；式（