【文章內(nèi)容簡介】 送路線優(yōu)化設(shè)計(jì)的可行性聯(lián)華超市配送中心配送路線的優(yōu)化設(shè)計(jì)屬于車輛優(yōu)化調(diào)度問題，而求解車輛優(yōu)化調(diào)度問題的主要方法精確算法、啟發(fā)算法和智能算法。而精確算法的計(jì)算量和計(jì)算時(shí)間隨著車輛優(yōu)化問題規(guī)模的增大呈指數(shù)增長，對(duì)于較大規(guī)模的車輛優(yōu)化調(diào)度問題不適用。啟發(fā)式算法當(dāng)中的節(jié)約里程法，計(jì)算步驟簡單，計(jì)算速度快，且易于考慮各種實(shí)際問題，并不追求問題的最優(yōu)解，而強(qiáng)調(diào)問題解的滿意性，可以高效地得到問題的近似最優(yōu)解。本文針對(duì)零售業(yè)的實(shí)際情況，即各個(gè)門店對(duì)于某些常用商品的需求是穩(wěn)定而不間斷的，在研究這類問題的時(shí)候，不需要各個(gè)門店在不同時(shí)期對(duì)于不同貨物的需求，只要每次配送固定的商品即可，對(duì)于這類問題，本文建立了問題一的模型，這種模型往往運(yùn)用于配送中心的某些常用的子系統(tǒng)，如某些常用的商品的配送，這類問題講求簡單高效，追求最快的滿意解。因此，用節(jié)約里程法解決問題一這類模型是可行的。而對(duì)于更為復(fù)雜的配送模型，比如大量的非常規(guī)商品的配送，不同的門店需要不同的商品，針對(duì)這類錯(cuò)綜復(fù)雜的模型，必須借助現(xiàn)代化的智能算法，使得配送方案更為科學(xué)合理，準(zhǔn)確易行。因此，用智能算法當(dāng)中的遺傳算法來解決問題二這類模型是可行的。 配送路線優(yōu)化的意義配送合理化與否是配送決策系統(tǒng)的重要內(nèi)容，配送線路的合理與否又是配送合理化的關(guān)鍵。選擇合的理配送路線，對(duì)企業(yè)和社會(huì)都具有很重要的意義。 對(duì)企業(yè)來說，(1)優(yōu)化配送路線，可以減少配送時(shí)間和配送里程，提高配送效率，增加車輛利用率，降低配送成本。(2)可以加快物流速度，能準(zhǔn)時(shí)、快速地把貨物送到客戶的手中，提高客戶滿意度。(3)使配送作業(yè)安排合理化，提高企業(yè)作業(yè)效率，有利于企業(yè)提高競爭力與效益。 對(duì)社會(huì)來說，它可以節(jié)省運(yùn)輸車輛，減少車輛空載率，降低了社會(huì)物流成本，對(duì)其他企業(yè)尤其是生產(chǎn)企業(yè)具有重要意義。與此同時(shí)，還能緩解交通緊張狀況，減少噪聲、尾氣排放等運(yùn)輸污染，對(duì)民生和環(huán)境也有不容忽視的作用 。5 / 306 / 30第二章 聯(lián)華超市配送路線作業(yè)現(xiàn)狀目前聯(lián)華的物流體系是，所有貨物由供貨商直接送達(dá)店面，這種方式雖然靈活，但影響了供貨速度，也加重了供貨商的負(fù)擔(dān)。由于聯(lián)華各門店自行采購，供貨商不一，大大影響了供貨速度；并且，聯(lián)華目前的供貨方式也加重了供貨商負(fù)擔(dān)。隨著中國零售市場白熱化競爭的日趨激烈，建設(shè)區(qū)域物流配送中心無疑可以幫助聯(lián)華加快店面更新速度，鞏固市場。而聯(lián)華超市也應(yīng)在各個(gè)市區(qū)確立商品配送中心，以后供應(yīng)商只要將貨物運(yùn)送至物流中心，各分店商品的配送統(tǒng)一由物流中心來實(shí)現(xiàn)。作為便利店模式的首推者，“靈活” 和“適應(yīng)”一直被視為聯(lián)華成功改變中國人購物習(xí)慣的法寶。店長的“欽點(diǎn)” 讓聯(lián)華許多貨架上充盈著本地的產(chǎn)品。加上所開門店位置多位于大中型城市，這讓門店直送方式有了很強(qiáng)的操作性。聯(lián)華不用多費(fèi)心思經(jīng)營物流，只需讓供應(yīng)商們接上它的訂單生成系統(tǒng)，再順手給個(gè)“deadline”（送貨的最后期限），一切就告萬事大吉。“小批量，多頻次 ”的訂貨原則，保證聯(lián)華可以盡量減少門店庫存。而使用時(shí)段限制，過期則不收貨的“殘酷” 手段，來保證供應(yīng)商的準(zhǔn)時(shí)到貨率，在中國也被認(rèn)為是簡明有效的。近乎于零的物流費(fèi)用和基本合格的配送質(zhì)量，曾讓聯(lián)華人頗感自豪。真正傷腦筋的是供應(yīng)商們，本來利潤就不高，面對(duì)聯(lián)華在物流上的不作為，還得自己挖空心思節(jié)約成本。目前，聯(lián)華的商品配送分幾種情況，大部分情況是通過第三方物流實(shí)現(xiàn)的，費(fèi)用由供應(yīng)商承擔(dān)。以北京地區(qū)為例，給聯(lián)華做配送的主要有上海成協(xié)，朝百批發(fā)，大榮物流等幾家公司。有一小部分品牌，包括可口可樂、寶潔和百事可樂等大公司以及一些生鮮食品等都具有直送的能力。有些聯(lián)華的門店還習(xí)慣于將降價(jià)損失、損耗和營業(yè)額、毛利率指標(biāo)的完不成數(shù)，轉(zhuǎn)嫁給供應(yīng)商來承擔(dān)，也就是說供應(yīng)商與總部談好的交易條件到了門店是要附加的，因?yàn)槁?lián)華是最大的，供應(yīng)商也無可奈何；另外據(jù)悉，聯(lián)華近期采取的分區(qū)采購政策，也使得供貨商從過去習(xí)慣于以一對(duì)一的模式變成了以一對(duì)多，這樣無疑加大了供貨商的運(yùn)營成本，從而導(dǎo)致他們抱怨多多。7 / 30第三章 配送線路優(yōu)化模型及算法 配送線路優(yōu)化的模型 多回路運(yùn)輸—VRP 模型多回路運(yùn)輸問題是現(xiàn)實(shí)中很普遍的一種調(diào)配問題，特別對(duì)于有大量服務(wù)對(duì)象的實(shí)體，例如擁有一個(gè)上千客戶的企業(yè)。此類調(diào)配的核心問題是如何對(duì)車輛進(jìn)行調(diào)度。因此，VRP（Vehicle Routing Problem）模型也應(yīng)運(yùn)而生，成了解決多回路問題的一個(gè)相當(dāng)成功的模型。該問題研究目標(biāo)是：對(duì)一系列顧客需求點(diǎn)設(shè)計(jì)適當(dāng)?shù)穆肪€，使車輛有序地通過他們，在滿足一定的約束條件下（如貨物需求量、發(fā)送量、車輛容量限制，行駛里程限制等） ，達(dá)到一定的優(yōu)化目標(biāo)（如里程最短，費(fèi)用最小，時(shí)間盡量少等） 。它涉及了多輛交通工具的服務(wù)對(duì)象的選擇和路徑確定兩方面問題。一個(gè)典型的 VRP 模型可以如下表述：（1）基本條件 現(xiàn)有 m 輛相同的車輛停在一個(gè)共同的源點(diǎn) ，它需給 n 個(gè)0v客戶提供貨物，顧客為 。12n,v、 …，（2）模型目標(biāo) 確定所需的車輛數(shù) N，并指派這些車輛到一個(gè)回路中，同時(shí)包括回路內(nèi)的路徑安排和調(diào)度，使總費(fèi)用最小。（3）限制條件：N 不大于 m；每一個(gè)訂單都要完成；每輛車完成任務(wù)后都要回到源點(diǎn) ；車輛的容量限制不能超過；特殊問題還需考慮時(shí)窗限制；運(yùn)輸規(guī)章0v限制。 PDPTW 問題模型PDPTW 問題是 VRP 問題的一個(gè)很有用的擴(kuò)展，近段時(shí)期引起越來越多的研究者的注意，許多新的優(yōu)化思想和優(yōu)化方法被引入到此問題中，并產(chǎn)生了一定的影響。PDPTW 問題（Pickup and Delivery Problem with Time Windows，帶時(shí)間窗口的裝卸貨問題）是為一個(gè)車隊(duì)尋找最優(yōu)的運(yùn)輸路徑來滿足所有客戶的運(yùn)輸需求。車隊(duì)的每一輛車從車庫出發(fā)，沿優(yōu)化的路徑為客戶服務(wù)并最終返回車8 / 30庫。每一輛車都給定最大容量和出發(fā)、返回車庫。每個(gè)運(yùn)輸需求指定一個(gè)裝貨點(diǎn)、一個(gè)卸貨點(diǎn)和運(yùn)輸貨物量。裝貨點(diǎn)、卸貨點(diǎn)以及車庫都有時(shí)間窗口。車輛必須在規(guī)定的時(shí)間窗內(nèi)訪問裝、卸貨點(diǎn)。也就是說，在運(yùn)輸網(wǎng)絡(luò)中，已知待服務(wù)的裝、卸貨點(diǎn)和車庫的位置和時(shí)間窗口、車輛的最大容量以及運(yùn)輸貨物量的前提下，設(shè)計(jì)車輛運(yùn)輸路徑，使運(yùn)輸成本最小化。PDPTW 的解是路徑的集合，每一輛車對(duì)應(yīng)一條路徑，包括以下方面：? 需要用到的車輛數(shù)目；即，有多少條路徑? 每輛車訪問每一個(gè)點(diǎn)的順序以及時(shí)刻PDPTW 問題中，要求滿足的約束條件主要有以下幾種：1) 時(shí)間窗口約束：車輛必須在規(guī)定的時(shí)間窗內(nèi)服務(wù)裝貨點(diǎn)或卸貨點(diǎn)。如果車輛在 之前到達(dá)點(diǎn) ，必須在點(diǎn) 等待到 才能開始裝卸貨。車輛在 時(shí)刻之后到達(dá)點(diǎn) ，則無法按時(shí)完成該點(diǎn)的裝卸貨任務(wù)，因而是不允許的。 2） 訪問約束：車輛到客戶指定的裝貨點(diǎn)裝貨，然后運(yùn)輸?shù)较鄳?yīng)的卸貨點(diǎn)卸貨。每一個(gè)點(diǎn)都必須被一輛車服務(wù)且只能服務(wù)一次。 3） 車庫約束：車輛必須從車庫出發(fā)到某一裝貨點(diǎn)，最后從某一卸貨點(diǎn)返回車庫。車輛返回車庫后不允許再次出發(fā)。4） 成對(duì)約束：一個(gè)客戶需求的裝貨點(diǎn) 和其對(duì)應(yīng)的卸貨點(diǎn) 必須被同一輛車訪問。 5） 次序約束：客戶需求的裝貨點(diǎn) 必須在對(duì)應(yīng)的卸貨點(diǎn) 之前被訪問。 6） 容量約束：任何時(shí)刻車輛所裝貨物量之和不能超過車輛的最大容量。上述約束是 PDPTW 問題中常見的幾種約束條件。另外還會(huì)根據(jù)實(shí)際情況的要求增加一些附加約束，如車輛類型與貨物類型之間的類型匹配約束，司機(jī)的最大工作時(shí)間約束等。PDPTW 問題的優(yōu)化目標(biāo)也是總運(yùn)輸成本最小。一般來說，與總運(yùn)輸成本有關(guān)的費(fèi)用包括：車輛的固定代價(jià)，是運(yùn)輸代價(jià)中最重要的部分，要最大可能的減少使用的車輛數(shù)；與車輛行駛距離有關(guān)的代價(jià)。 配送問題的求解算法車輛配送問題的求解算法有很多種，但究其本質(zhì)來講，基本分為最優(yōu)化算法和啟發(fā)式算法兩大類。 最優(yōu)化算法最優(yōu)化算法，也稱之為精確算法，就是指能夠通過有限的計(jì)算和推理得到優(yōu)化問題的最優(yōu)解的算法。在配送問題中，所謂最優(yōu)化算法就是找到一組路徑集合，使得其目標(biāo)函數(shù)值比其它任何一組可行路徑集合的目標(biāo)函數(shù)值更好。常用的最優(yōu)化算法主要有：分枝定界算法、動(dòng)態(tài)規(guī)劃算法和整數(shù)規(guī)劃。通常情況下，NPhard 問題的精確解法的計(jì)算量較大，而且隨著問題規(guī)模的增大計(jì)算量會(huì)呈爆炸式的增長，因此在實(shí)際問題中最優(yōu)化算法的應(yīng)用范圍有限。 啟發(fā)式算法啟發(fā)式算法是通過對(duì)過去經(jīng)驗(yàn)的歸納推理以及實(shí)驗(yàn)分析來解決問題的方法，即借助于某種直觀推斷或試探的方法。啟發(fā)式方法要求分析人員必須運(yùn)用自己的感知和洞察力，從與研究問題有關(guān)而比較具體的模型及算法中尋求其間的聯(lián)系，從中得到啟發(fā)，去發(fā)現(xiàn)適于解決該問題的思路和途徑。用啟發(fā)式方法求解問題時(shí)強(qiáng)調(diào)“滿意” 。常常是得到滿意解，決策者就認(rèn)為可以了，而不去追求最優(yōu)解。之所以這樣是因?yàn)椋? / 30(1) 很多問題不存在嚴(yán)格的最優(yōu)解（如目標(biāo)之間存在矛盾的多目標(biāo)問題） ，此時(shí)對(duì)目標(biāo)的滿意性比最優(yōu)性更能描述人們的選擇行為。(2) 得到某些問題最優(yōu)解的成本太大。(3) 從實(shí)際出發(fā)，有時(shí)探求問題的最優(yōu)解沒有意義。對(duì)于 NPHard 問題，人們自然會(huì)想到啟發(fā)式的算法。啟發(fā)式的算法就是根據(jù)某種啟發(fā)式的信息對(duì)已知的可行解進(jìn)行改善，通過若干次的迭代獲得相對(duì)滿意的解。和精確算法相比，啟發(fā)式的算法不能保證得到全局最優(yōu)解，但是實(shí)現(xiàn)起來相對(duì)簡單。由于車輛運(yùn)輸調(diào)度問題是 NPhard 問題，而現(xiàn)實(shí)中該問題規(guī)模一般很大，因此想以能夠接受的運(yùn)算速度找到最優(yōu)解是不可能的。而啟發(fā)式算法可以在相對(duì)短時(shí)間內(nèi)找到“滿意”解，為此研究人員把精力主要放在構(gòu)造高質(zhì)量的啟發(fā)式算法上。目前已提出的求解車輛運(yùn)輸調(diào)度問題的啟發(fā)式算法很多，主要分為經(jīng)典啟發(fā)式算法和現(xiàn)代啟發(fā)式算法兩類。 節(jié)約算法利用節(jié)約法確定配送線路的主要出發(fā)點(diǎn)是，根據(jù)配送中心的運(yùn)輸能力（包括車輛的多少和載重量）和配送中心到各個(gè)用戶以