第2章 配送中心物流系統(tǒng)優(yōu)化的理論基礎(chǔ)

1、1第一節(jié)第一節(jié) 物流系統(tǒng)優(yōu)化概述物流系統(tǒng)優(yōu)化概述 物流優(yōu)化：通過(guò)理論分析獲取物流管理優(yōu)化方案并將該優(yōu)化方案予以實(shí)施的過(guò)程。 2引導(dǎo)案例某公司目前在西安市5個(gè)區(qū)各有一個(gè)中轉(zhuǎn)庫(kù)房。每天大約有300家零售商店要求第二天上午送貨，目前的服務(wù)方式為每個(gè)庫(kù)房負(fù)責(zé)本轄區(qū)的店(或稱需求用戶)。 該公司正在考慮調(diào)整目前的服務(wù)方式，根據(jù)每天用戶的實(shí)際情況，統(tǒng)籌考慮庫(kù)房的使用和需求用戶的分配使服務(wù)的總費(fèi)用最小。1. 庫(kù)存費(fèi)用2. 倉(cāng)庫(kù)租金3. 公司到庫(kù)房的運(yùn)費(fèi)4. 車輛送貨的行程費(fèi)用及固定費(fèi)用等34PsubsetVxKkxKkJjPixxPixtsxxdydfyrhygZvivjKkijkPiJjijkJjijkp

2、iijkKkJjijkKkPiJjijkkPiJjKkijkkijJjjjjJjjjjJjjj, 1, 1, 0, 1. .min567仿真模型視頻3：額的Flexsim物流配送中心視頻.flv8二、物流系統(tǒng)優(yōu)化的基本思路1.分析并研究問(wèn)題2.明確決策目標(biāo)（注意目標(biāo)的衡量）3.建立優(yōu)化模型（分析模型與仿真模型）4.收集數(shù)據(jù)參數(shù)5.確定計(jì)算方法（近似算法和準(zhǔn)確算法；計(jì)算時(shí)間；準(zhǔn)確性；穩(wěn)定性）6.提出優(yōu)化方案7.初步運(yùn)行并評(píng)價(jià)（不同情境下的性能；解決方案后的結(jié)果與理想結(jié)果；不同階段等的效果）8.修改9.需要修改10. 運(yùn)行得出最優(yōu)方案9物流系統(tǒng)優(yōu)化的應(yīng)用領(lǐng)域 選址 庫(kù)存 運(yùn)輸（配送） 信息技術(shù)位置

3、和數(shù)量訂貨時(shí)間和訂貨數(shù)量運(yùn)輸工具得選擇、運(yùn)輸計(jì)劃的制定構(gòu)建和運(yùn)作物流系統(tǒng)平臺(tái)10第二節(jié) 物流優(yōu)化的應(yīng)用領(lǐng)域 一、優(yōu)化方法在選址決策中的應(yīng)用選址：通過(guò)網(wǎng)絡(luò)分析，優(yōu)化物流節(jié)點(diǎn)的位置和數(shù)量，使物流系統(tǒng)獲得合理的運(yùn)輸成本和庫(kù)存成本，有效滿足顧客的需求。 物流網(wǎng)絡(luò)設(shè)計(jì)通?？梢苑譃槿齻€(gè)步驟：1.網(wǎng)絡(luò)分析。通過(guò)網(wǎng)絡(luò)分析，確定網(wǎng)絡(luò)要素和相互的關(guān)系，比如配送中心的位置、分銷地點(diǎn)和數(shù)量、供應(yīng)商的數(shù)量和位置等2.優(yōu)化設(shè)計(jì)，采用有關(guān)數(shù)學(xué)模型或采用其他方法進(jìn)行優(yōu)化決策分析；3. 組織實(shí)施網(wǎng)絡(luò)設(shè)計(jì)方案。局部物流網(wǎng)絡(luò)設(shè)計(jì) 全局物流網(wǎng)絡(luò)設(shè)計(jì)11二、優(yōu)化方法在物流運(yùn)作管理中的運(yùn)用 運(yùn)輸管理 物料管理制訂最優(yōu)運(yùn)輸計(jì)劃(經(jīng)驗(yàn))制訂

4、最優(yōu)配送計(jì)劃（VRP,P38）庫(kù)存決策12配送標(biāo)準(zhǔn)車輛路徑問(wèn)題的優(yōu)化目標(biāo)為: 確定一個(gè)具有最小車輛數(shù)和對(duì)應(yīng)的最小旅行距離或者費(fèi)用的路線集.約束條件： 每一條車輛路線開(kāi)始于車場(chǎng)點(diǎn)，并且于車場(chǎng)點(diǎn)結(jié)束; 每個(gè)顧客點(diǎn)能且僅能被一輛車服務(wù)一次; 每一條車輛路線總的顧客點(diǎn)的需求不超過(guò)車輛的裝載能力Q; 每一條車輛路線滿足一定的邊約束，比如持續(xù)時(shí)間約束和時(shí)間窗約束等13配送運(yùn)輸干道布局14服務(wù)半徑服務(wù)半徑 一個(gè)區(qū)域性的物流節(jié)點(diǎn)，應(yīng)有一個(gè)合理的運(yùn)輸距離（由點(diǎn)到周邊的最遠(yuǎn)距離）和相應(yīng)合理的服務(wù)區(qū)域（即吸引范圍或腹地。在假定地域上經(jīng)濟(jì)單位的分布是平均的和連續(xù)的這一前提下，為使這個(gè)集中點(diǎn)的位置達(dá)到經(jīng)濟(jì)上最優(yōu)，應(yīng)滿足

5、： 此點(diǎn)應(yīng)位于服務(wù)區(qū)域的幾何中心； 運(yùn)輸距離達(dá)到最長(zhǎng)或服務(wù)周邊達(dá)到最短時(shí)，服務(wù)區(qū)域能達(dá)到大； 如果此節(jié)點(diǎn)只是整個(gè)區(qū)域中的一個(gè)，則此點(diǎn)與相鄰各點(diǎn)之間，它 們的服務(wù)區(qū)域的毗鄰處，應(yīng)不留空白區(qū)，也就是地域彌合的原則。15 服務(wù)區(qū)域劃分 最少數(shù)原則：服務(wù)區(qū)域數(shù)越少，區(qū)域內(nèi)的客戶數(shù)也就越多，配送的規(guī)配送的規(guī)模效益模效益越高； 最小必要數(shù)原則：客戶所要求的交貨時(shí)間、車輛的經(jīng)濟(jì)速度和在每個(gè)客戶所要求的交貨時(shí)間、車輛的經(jīng)濟(jì)速度和在每個(gè)節(jié)點(diǎn)停留時(shí)間節(jié)點(diǎn)停留時(shí)間決定了運(yùn)輸工具經(jīng)濟(jì)運(yùn)輸半徑運(yùn)輸工具經(jīng)濟(jì)運(yùn)輸半徑。服務(wù)區(qū)域數(shù)的減少必然會(huì)使服務(wù)范圍擴(kuò)展，而范圍擴(kuò)展又會(huì)受到運(yùn)輸工具有效運(yùn)輸半徑范圍擴(kuò)展又會(huì)受到運(yùn)輸工具有效運(yùn)

6、輸半徑的限制。由此，產(chǎn)生了區(qū)域劃分的最小必要數(shù)； 區(qū)域再分原則：當(dāng)某一區(qū)域的貨物流量增加到一定程度時(shí)，配送點(diǎn)的成本不能隨流量增加而配送點(diǎn)的成本不能隨流量增加而下降時(shí)下降時(shí)，就應(yīng)將一個(gè)區(qū)域分成兩個(gè)流量相等的區(qū)域，并設(shè)置兩個(gè)相同的配送點(diǎn)。1617實(shí)例1 油品配送路線油品配送路線是根據(jù)加油站的訂單編排加油站的訂單編排的車輛配送路線。其中每一訂單需要指定一個(gè)可供油的油庫(kù)，車輛在油庫(kù)裝油后向加油站供油。在一個(gè)調(diào)度日，車輛可往返于油庫(kù)與加油站之間多次。18 一個(gè)油庫(kù)由幾個(gè)大的儲(chǔ)油罐組成，其中每個(gè)油罐儲(chǔ)存一種油品。油品主要有柴油和汽油兩大類，而每一類包括多種型號(hào)。 在供應(yīng)鏈中，油庫(kù)被分為一級(jí)油庫(kù)和二級(jí)油庫(kù)，

7、其中一級(jí)油庫(kù)的油來(lái)自油品供應(yīng)商，二級(jí)油庫(kù)的油來(lái)自一級(jí)油庫(kù)?；谶@種關(guān)系，對(duì)位于一級(jí)油庫(kù)和二級(jí)油庫(kù)之間的加油站，如果這兩個(gè)油庫(kù)都有其需求油品的庫(kù)，則要求從一級(jí)油庫(kù)出油。 油庫(kù)從信息系統(tǒng)獲知一天的出油計(jì)劃，并根據(jù)車輛駕駛員提供的提油單配油。為防止冒領(lǐng)，信息系統(tǒng)還向油庫(kù)提供配送車輛的車牌號(hào)。由于油庫(kù)的加油平臺(tái)數(shù)有限，為了減少等待時(shí)間，駕駛員可自主確定裝油時(shí)間（在滿足寬松的時(shí)間窗時(shí)間窗約束下）。在一天的固定時(shí)點(diǎn)，油庫(kù)管理員統(tǒng)計(jì)當(dāng)天實(shí)際總出油量，上傳信息。19 車輛 油品配送車輛具有多車型多艙位多車型多艙位的特點(diǎn)。油罐車輛的車型主要根據(jù)車輛噸位進(jìn)行劃分，不同噸位的車輛所能配送的加油站不同。例如位于市區(qū)的

8、加油站一般只能由噸位小于7噸的車輛配送； 車輛的多艙位車輛的多艙位是油品配送的一個(gè)特色。 一輛車還有載重量限制，并從安全角度考慮，一般情況下車輛不能滿載裝車。為了保證油品質(zhì)量，通常限制艙位只能裝柴油或汽油。 車輛在油庫(kù)的出油平臺(tái)通過(guò)頂部或底部出口裝油，在加油站則通過(guò)帶閥的管子靠重力將油輸送到地下油罐。 出于事故承擔(dān)風(fēng)險(xiǎn)事故承擔(dān)風(fēng)險(xiǎn)的考慮和運(yùn)輸對(duì)象單一性，在我國(guó)，國(guó)有石油企業(yè)不愿將運(yùn)輸公司作為下屬子公司。20訂單 次日必須配送次日必須配送訂單。這類訂單要求必須在次日進(jìn)行配送。 次日選擇配送次日選擇配送訂單。此類訂單只要求在次日運(yùn)力富余的情況下才進(jìn)行配送。如果次日沒(méi)有配送這類訂單，則順延至下一調(diào)度

9、日。 追加配送訂單。追加配送訂單。這類訂單是在當(dāng)天生成并要求當(dāng)天配送、較為緊急的配送需求。如何制定配送計(jì)劃？21 制定配送計(jì)劃的常規(guī)方式是：在一天的某個(gè)固定時(shí)間（如下午3點(diǎn)），制定次日配送計(jì)劃。 如果人工制定計(jì)劃，由于需要權(quán)衡配送成本、運(yùn)量平衡等因素，對(duì)一個(gè)日配量達(dá)300噸的配送計(jì)劃，一般需要花4-5小時(shí)。22實(shí)例2 零售配送路線 零售配送是面向最終用戶的小批量多品種配送。在一條零售配送路線中，根據(jù)一組訂單，車輛從倉(cāng)庫(kù)裝貨，然后有序地運(yùn)送到各個(gè)訂單地址。2324 零售配送只有在具有一定配送規(guī)模時(shí)，才具有成本優(yōu)勢(shì)。例如，由上海市煙草集團(tuán)、上海市煙糖集團(tuán)和捷強(qiáng)集團(tuán)三方總投資6億元興建的上海海煙物流

10、中心上海海煙物流中心，平均每周需要向6000多個(gè)商業(yè)網(wǎng)點(diǎn)進(jìn)行配送，配送品種達(dá)13250種，年配送量可達(dá)3500萬(wàn)箱。美國(guó)的一家主要從事家具及各種設(shè)備的運(yùn)輸服務(wù)的公司Sears公司，管理著全美國(guó)1000輛車，年訂單數(shù)達(dá)21000個(gè)，年運(yùn)輸量超過(guò)4百萬(wàn)車次，服務(wù)范圍覆蓋了70%的美國(guó)人口。25 食品有限公司在廣州市有20個(gè)主要的賣場(chǎng)，物流公司需要將位于市郊倉(cāng)庫(kù)的貨物發(fā)送到各個(gè)賣場(chǎng)滿足其需要，并希望配送的總里程最短以降低成本。 圖5-2給出公司在廣州市主城區(qū)主要賣場(chǎng)分布圖。 其中節(jié)點(diǎn)1代表倉(cāng)庫(kù)，節(jié)點(diǎn)2至21為賣場(chǎng)。 21個(gè)節(jié)點(diǎn)之間的里程見(jiàn)附錄4，其中節(jié)點(diǎn)之間的里程與導(dǎo)航線路由GIS導(dǎo)航系統(tǒng)得到，它充

11、分考慮了城市的路網(wǎng)結(jié)構(gòu)以及相關(guān)交通法規(guī)，基本符合實(shí)際情況。262728 采用貪心算法得到總里程為102.2公里，路線為1,2,4,5,6,7,3,8,10,11,12,13,14,15,16,17,18,19,9,20,21,129 HGPSO-TSP優(yōu)化的總里程為88.6公里，線路為： 1,7,3,15,14,13,12,11,10,21,16,17,18,19,20,9,8,6,5,4,2,1。30廣州市限制噸位限制噸位1.5噸以上貨車噸以上貨車進(jìn)入中心城區(qū),采用四輛四輛貨車貨車送貨，行駛路線以及相應(yīng)載重(公斤)和里程(公里)如下：1.線路1：1,2,20,18,19,9,1；載重：876

12、；載重率：97.33%；里程：55.6；2.線路2：1,21,17,16,11,10,1；載重：876；載重率：97.33%；里程：57.9；3.線路3：1,5,12,13,14,15,1；載重：900；載重率：100%；里程：64.9；4.線路4：1,7,3,8,6,4,1；載重：894；載重率：99.33%；里程：39.1；5.總載重：3546；平均載重率：98.5%；總里程：217.5公里。0.9噸的車！3132采用三輛貨車三輛貨車送貨，行駛路線以及相應(yīng)載重(公斤)和里程(公里)如下：1. 線路1：1,7,3,5,4,2,1；載重：996；載重率：66.4%；里程：36.4；2. 線路2

13、：1,8,15,14,13,12,11,10,6,1；載重：1296；載重率：86.4%；里程：65.6；3. 線路3：1,9,20,21,16,17,18,19,1；載重：1254；載重率：83.6%；里程：63.5；4. 總載重：3546；平均載重率：78.8%；總里程：165.5公里。1.5噸的車！噸的車！333435總載重：6430；平均載重率：85.7%；總配送里程：159.7公里。36實(shí)例3 快遞配送路線 快遞業(yè)務(wù)是針對(duì)小體積高價(jià)值的物件快遞。其一般業(yè)務(wù)流程是：客戶服務(wù)中心根據(jù)客戶下單，派車前去收取快件，并匯總到收發(fā)站；收發(fā)站經(jīng)過(guò)快件整合后遞送到服務(wù)中心；服務(wù)中心完成規(guī)定的程序（如

14、標(biāo)簽、射頻掃描、重量復(fù)查、分類、生成文檔、辦理正式手續(xù)）后，將快件包裹裝配至空運(yùn)集裝箱或袋子，運(yùn)輸至機(jī)場(chǎng)；同時(shí)，服務(wù)中心根據(jù)快件目的地進(jìn)行分揀后，或直接派車送件，或?qū)⒖旒\(yùn)送到收發(fā)站，由收發(fā)站負(fù)責(zé)送件。3738宅急送快運(yùn)有限公司宅急送快運(yùn)有限公司成立于1994年，目前已發(fā)展成為國(guó)內(nèi)提供綜合物流快遞服務(wù)最大的快運(yùn)公司，在北京、上海、廣州、沈陽(yáng)、成都、武漢等大中城市成立了300余家全資分支機(jī)構(gòu)，并在1000余個(gè)縣、市發(fā)展了眾多合作伙伴，形成了“宅急送全國(guó)物流快運(yùn)網(wǎng)絡(luò)”，使宅急送的門到門快運(yùn)業(yè)務(wù)覆蓋到全國(guó)2000多個(gè)城市和地區(qū)。2006年，公司員工達(dá)到10000名，車輛1800臺(tái)，年貨物進(jìn)出港量70

15、00萬(wàn)件，年遞增率超過(guò)45%，同年被中國(guó)交通協(xié)會(huì)評(píng)為“中國(guó)百?gòu)?qiáng)物流企業(yè)第23名”、“中國(guó)最具成長(zhǎng)性物流企業(yè)”稱號(hào)。 主要從事的業(yè)務(wù)有:小件業(yè)務(wù)、.速遞業(yè)務(wù)和經(jīng)濟(jì)業(yè)務(wù)。其中小件業(yè)務(wù)的承運(yùn)范圍為10棺以內(nèi)，三邊之和(長(zhǎng)+寬+高)不超過(guò)100cm。39 宅急送成都分公司位于成都市簇橋鄉(xiāng)文昌工業(yè)園區(qū)，所覆蓋川內(nèi)網(wǎng)點(diǎn)達(dá)80多個(gè)地方，均可做門到門服務(wù)。 分公司員工數(shù)量220名，辦公面積300平米，倉(cāng)儲(chǔ)面積4000平米，車輛數(shù)量配量41輛，其中金杯車22輛、廂式貨車巧輛?，F(xiàn)有配送能力可到達(dá)國(guó)內(nèi)2000余個(gè)城市的門到門配送。 宅急送成都分公司在成都市內(nèi)有6個(gè)營(yíng)業(yè)廳1.城中營(yíng)業(yè)廳:位于太升北路，所轄區(qū)域?yàn)橐画h(huán)路

16、以內(nèi);2.城東營(yíng)業(yè)廳:位于琉璃場(chǎng)，所轄區(qū)域?yàn)闁|面;3.城西營(yíng)業(yè)廳:位于營(yíng)門口，所轄區(qū)域?yàn)槲髅?4.城南營(yíng)業(yè)廳:位于紅牌樓，所轄區(qū)域?yàn)槟厦?5.城北營(yíng)業(yè)廳:位于八里小區(qū)，所轄區(qū)域?yàn)楸泵?6.金牛營(yíng)業(yè)廳:位于火車北站，主要負(fù)責(zé)鐵路、公路口岸貨物的進(jìn)、出港業(yè)務(wù)，運(yùn)營(yíng)單位。40 四川分公司城東營(yíng)業(yè)廳坐落于成都市東南部琉璃場(chǎng)琉璃一街，其前身為磨子橋營(yíng)業(yè)廳。 目前該廳配備金杯車和三噸車各一輛，小件員一名。 所轄范圍北起一環(huán)路東四段至一環(huán)路南二段沿線;南至錦江工業(yè)開(kāi)發(fā)區(qū)、龍泉經(jīng)濟(jì)技術(shù)開(kāi)發(fā) 區(qū)等區(qū)域;東起蜀都大道、雙桂路、迎暉路、成渝路沿線;西至人民南路四段大部分所轄區(qū)域都屬于成都市錦江區(qū)。41424344對(duì)

17、該營(yíng)業(yè)廳，每天金杯車司機(jī)送取貨工作流程如下:1. 7:00到本部(位于簇橋鄉(xiāng)文昌工業(yè)園區(qū))報(bào)到，并參加早會(huì)，車輛于當(dāng)日2. 晨4:00左右配好城東營(yíng)業(yè)廳所負(fù)責(zé)的貨物;3. 7:30前離開(kāi)本部;4. 8:00前到達(dá)城東營(yíng)業(yè)廳報(bào)到;5. 12:00前完成上午發(fā)貨;6. 12:00以后，負(fù)責(zé)完成當(dāng)日到達(dá)營(yíng)業(yè)廳當(dāng)日需派送的同城小件貨物。7. 另外，該公司針對(duì)物流司機(jī)的晚點(diǎn)操作也進(jìn)行了相應(yīng)的處罰:若沒(méi)有在規(guī)定時(shí)間內(nèi)及時(shí)物流，處罰金額為50元/批次。所以，對(duì)送貨司機(jī)而言，返回營(yíng)業(yè)廳的時(shí)間越早越好。4546 車輛路徑問(wèn)題(VehideRoutingProblem，VRP) 己經(jīng)成為運(yùn)輸、物流以及配送管理領(lǐng)域

18、的核心問(wèn)題。其主要研究滿足約束條件的最優(yōu)的車輛使用方案以及最優(yōu)的車輛路線方案。 47 下面給出幾種常用的約束:1)容量約束:每條路徑總的需求量(或供應(yīng)量)不超過(guò)車輛的容量Q2)行程距離約束:每輛車的最大行程距離不超過(guò)某一預(yù)先指定的數(shù)3)時(shí)間窗約束:包括硬時(shí)間窗和軟時(shí)間窗。 在滿足某些約束條件下，如何安排車輛行程，使服務(wù)所有用戶的車輛行駛距離最小或所需車輛數(shù)最少。48配送路線決策系統(tǒng)與GIS系統(tǒng)配送路線決策系統(tǒng)的所有地理數(shù)據(jù)都將來(lái)自GIS系統(tǒng)。其中，基本的數(shù)據(jù)是經(jīng)緯度坐標(biāo)和最短路長(zhǎng)。1.搜索與地址相匹配的經(jīng)緯度坐標(biāo)。2.圖上取點(diǎn)。圖上取點(diǎn)是指，在無(wú)法通過(guò)訂單地址獲得經(jīng)緯度坐標(biāo)情況下，操作員可直接

19、在地圖上取點(diǎn)，并將點(diǎn)的經(jīng)緯度坐標(biāo)添入數(shù)據(jù)庫(kù)。3.應(yīng)用全球定位系統(tǒng)(Global Positioning Systems，GPS)和無(wú)線通信手段，自動(dòng)捕獲現(xiàn)場(chǎng)地理坐標(biāo)。49計(jì)算最短路徑是GIS系統(tǒng)的一項(xiàng)基本功能.1.成本最小的最短路徑2.時(shí)間最短的路徑3.某種車型能夠通行的最短路徑。50目前的GIS系統(tǒng)只能逐個(gè)地計(jì)算兩點(diǎn)間的最短路。假設(shè)GIS系統(tǒng)計(jì)算一次最短路的平均時(shí)間是0.2秒，則計(jì)算100個(gè)點(diǎn)的最短路長(zhǎng)的平均時(shí)間為1980秒，約33分鐘；如果是1000個(gè)點(diǎn)，則至少需要11天的時(shí)間！目前國(guó)內(nèi)GIS系統(tǒng)的最短路平均計(jì)算時(shí)間還達(dá)不到0.2秒。以上海市區(qū)為例，計(jì)算25個(gè)點(diǎn)的最短路長(zhǎng)矩陣至少需要15分

20、鐘！51配送路線決策系統(tǒng)與物流信息系統(tǒng)52VRP求解方法1. 節(jié)約里程法2. 旋轉(zhuǎn)射線法53VRP問(wèn)題的求解可采用下面兩種方法： 節(jié)約算法（Savings Algorithm）是Clarke 和Wright 在1964 年提出的?？梢杂盟鼇?lái)解決運(yùn)輸車輛數(shù)目不確定的VRP 問(wèn)題，對(duì)有向和無(wú)向問(wèn)題同樣有效。5455562）旋轉(zhuǎn)射線法旋轉(zhuǎn)射線法求解VRP問(wèn)題時(shí)分如下幾步完成：57 1、點(diǎn)點(diǎn)間運(yùn)輸-最短路徑求解 最短路徑是線路優(yōu)化模型中最為基礎(chǔ)的問(wèn)題之一，也是解決其它一些線路優(yōu)化問(wèn)題的有效工具。為了在使用最短路徑求解時(shí)，得到合理的、正確的解。 求解此類最短路徑問(wèn)題，主要有迪杰斯特拉（Dijkstra）

21、法、逐次逼近法和Floyd算法等。在此專門對(duì)迪杰斯特拉法進(jìn)行介紹。5859 2、單回路運(yùn)輸-TSP模型及求解 TSP（Traveling Salesman Problem，旅行商問(wèn)題）模型是單回路運(yùn)輸問(wèn)題中最為典型的一個(gè)模型，它是一個(gè)典型的NP-Hard問(wèn)題。對(duì)于大規(guī)模的線路優(yōu)化問(wèn)題，無(wú)法獲得最優(yōu)解，只能通過(guò)啟發(fā)式算法獲得近似解。啟法式算法不僅可用于復(fù)雜的TSP問(wèn)題求解，對(duì)中小規(guī)模的問(wèn)題也同樣適用。它的不足在于，它只能保證得到可行解，而且不同的啟發(fā)式算法所得到的結(jié)果也不完全相同。下面介紹兩種比較簡(jiǎn)單的啟發(fā)式算法，以便對(duì)該法有一個(gè)較全面得認(rèn)識(shí)。60 1）最近鄰點(diǎn)法（Nearest Neighbo

22、r） 最近鄰點(diǎn)法可以通過(guò)如下五步完成： 將起始點(diǎn)定為整個(gè)回路的起點(diǎn)； 找到剛加入到回路的上一個(gè)點(diǎn)最近的一個(gè)點(diǎn)，并將其加入到線路中； 重復(fù)步驟，只到集合所有節(jié)點(diǎn)都加入到了線路中； 然后，將最后加入的節(jié)點(diǎn)和起始點(diǎn)連接起來(lái)，形成回路； 最后，按流線型要求調(diào)整回路的形狀。如果調(diào)整后的結(jié)果小于步驟所得的解，將該解定為TSP問(wèn)題的解。612）最近插入法（Nearest Insertion）最近插入法可以通過(guò)如下步驟完成： 6263 3、多回路運(yùn)輸-VRP模型及求解64三、物流優(yōu)化的其他應(yīng)用領(lǐng)域第一層次：配送中心的產(chǎn)品進(jìn)貨計(jì)劃第二層次：營(yíng)銷策略與產(chǎn)品的市場(chǎng)需求特征第三層次：產(chǎn)品的進(jìn)貨價(jià)格65第三節(jié) 物流優(yōu)化

23、的基礎(chǔ)理論與計(jì)算方法 一、規(guī)劃論 例2-1：運(yùn)輸問(wèn)題的數(shù)學(xué)模型 大宗物資調(diào)運(yùn)，如原材料等在全國(guó)有若干生產(chǎn)基地，根據(jù)以后的交通網(wǎng)絡(luò)，制訂調(diào)運(yùn)方案，將這些物資運(yùn)到各消費(fèi)地點(diǎn)，且總運(yùn)費(fèi)最小。用數(shù)學(xué)語(yǔ)言描述如下： 已知有m個(gè)生產(chǎn)基地，Ai （i=1,2,m）可供應(yīng)某種物資，其供應(yīng)量分別為ai（i=1,2,m）,有n 個(gè)銷地Bj (j= i=1,2,n), 其需要量分別為bj ( i=1,2,n)，從Ai至Bj 運(yùn)輸單位物資的運(yùn)價(jià)（單價(jià)）為cij ,這些數(shù)據(jù)匯總于產(chǎn)銷平衡表和單位運(yùn)價(jià)表中。66 產(chǎn)銷平衡表 單位運(yùn)價(jià)表若用 表示從Ai到Bj的運(yùn)量，在產(chǎn)銷平衡的條件下，要求得到總運(yùn)費(fèi)最小的調(diào)運(yùn)方案，可求解以

24、下數(shù)學(xué)模型：11minmnijijijzc x11,1,2,.,1,2,.,0mijjinijijijxbjnxa imx這就是運(yùn)輸問(wèn)題的數(shù)學(xué)模型。可用單純行法的簡(jiǎn)化方法表上作業(yè)法來(lái)解答67二、排隊(duì)論 例2-2：有一售票口。已知顧客按照平均2分30妙的時(shí)間間隔的負(fù)指數(shù)分布到達(dá)，顧客在售票口前服務(wù)平均時(shí)間為2分鐘。若服務(wù)時(shí)間也服從負(fù)指數(shù)分布，求顧客為購(gòu)票所需的平均逗留時(shí)間和等待時(shí)間；若經(jīng)過(guò)調(diào)查，顧客在售票口前至少要占用1分鐘，且認(rèn)為服務(wù)時(shí)間服從負(fù)指數(shù)分布是不恰當(dāng)?shù)模鴳?yīng)服從以下概率密度分布在這種情況下，再求顧客的逗留時(shí)間和等待時(shí)間。 1110yyefyy68解：用 表示單位時(shí)間平均到達(dá)的顧客數(shù)，

25、 表示單位時(shí)間內(nèi)能被服務(wù)完成的顧客數(shù)， 表示在系統(tǒng)中顧客逗留時(shí)間的期望值， 表示在隊(duì)列中顧客等待時(shí)間的期望值， 表示系統(tǒng)中的平均顧客數(shù)， 表示在隊(duì)列中等待的平均顧客數(shù)。 適用于相繼到達(dá)間隔時(shí)間為負(fù)指數(shù)分布、服務(wù)時(shí)間為一般服務(wù)時(shí)間分布的單服務(wù)臺(tái)模型。（1） swqwsL 222 1SVar TPKL公式為: P K 公式110.4,0.5,0.82.52110sw分8qw 分69令y 為服務(wù)時(shí)間，那么Y=1+X，X服從均值為1的負(fù)指數(shù)分布，于是EY=2, VarX=170三、庫(kù)存論例2-3：已知倉(cāng)庫(kù)最大容量為A，原有貯存量為I，要計(jì)劃在m個(gè)周期內(nèi)，確定每一個(gè)周期的合理進(jìn)貨量與銷售量，使總收入最多

26、。已知第i個(gè)周期出售一個(gè)單位貨物的收入為ai ,而定購(gòu)一個(gè)單位的定貨費(fèi)為bi ,(i=1,2,.,m)。71四、對(duì)策論例2-4：某廠用三種不同的設(shè)備 加工三種不同的產(chǎn)品 。已知三種設(shè)備分別加工三種產(chǎn)品時(shí)，單位時(shí)間內(nèi)創(chuàng)造的價(jià)值由表2-4給出。 出現(xiàn)負(fù)值是由于設(shè)備的消耗大于創(chuàng)造出的價(jià)值。在上述條件下，求出一個(gè)合理的加工方案。7273京藏高速擁堵今年今年3月份以來(lái)，月份以來(lái)，京藏高速公路頻繁發(fā)生堵車現(xiàn)象京藏高速公路頻繁發(fā)生堵車現(xiàn)象。從。從8月月14日開(kāi)始，京藏高速公路進(jìn)京方向再次出現(xiàn)堵車，堵車時(shí)間持日開(kāi)始，京藏高速公路進(jìn)京方向再次出現(xiàn)堵車，堵車時(shí)間持續(xù)續(xù)20多日、被堵車輛綿延上百公里，其時(shí)間之長(zhǎng)、數(shù)

27、量之多多日、被堵車輛綿延上百公里，其時(shí)間之長(zhǎng)、數(shù)量之多實(shí)屬罕見(jiàn)，引起了社會(huì)的廣泛關(guān)注。實(shí)屬罕見(jiàn)，引起了社會(huì)的廣泛關(guān)注。截至昨日，京藏高速仍被數(shù)萬(wàn)輛大型貨車擠得水泄不通。截至昨日，京藏高速仍被數(shù)萬(wàn)輛大型貨車擠得水泄不通。除京藏高速，北京西北的貨運(yùn)通道京新高速除京藏高速，北京西北的貨運(yùn)通道京新高速(原京包高速及原京包高速及110國(guó)道新線國(guó)道新線)在今年在今年6月也曾爆堵月也曾爆堵20多天多天 .74京藏高速擁堵的原因1. 八達(dá)嶺高速拒絕八達(dá)嶺高速拒絕4噸以上的大貨車進(jìn)入，這些車輛只得全部轉(zhuǎn)噸以上的大貨車進(jìn)入，這些車輛只得全部轉(zhuǎn)入入110國(guó)道國(guó)道 。2. 京藏高速承擔(dān)了太多的貨運(yùn)壓力，暴露這條狹長(zhǎng)走

28、廊運(yùn)輸方京藏高速承擔(dān)了太多的貨運(yùn)壓力，暴露這條狹長(zhǎng)走廊運(yùn)輸方式單一的弊端。式單一的弊端。3. 多條高速與國(guó)道對(duì)接，形成漏斗形路網(wǎng)，對(duì)接處的通行速度多條高速與國(guó)道對(duì)接，形成漏斗形路網(wǎng)，對(duì)接處的通行速度緩慢，進(jìn)而導(dǎo)致高速路上等待通行的車輛聚集，造成擁堵。緩慢，進(jìn)而導(dǎo)致高速路上等待通行的車輛聚集，造成擁堵。4. 110國(guó)道昌平與延慶交界附近路面開(kāi)始大修。該段施工使京藏國(guó)道昌平與延慶交界附近路面開(kāi)始大修。該段施工使京藏高速通行能力比原先降低高速通行能力比原先降低50%，這使擁堵?tīng)顩r雪上加霜。，這使擁堵?tīng)顩r雪上加霜。751. 高速成運(yùn)煤重要通道高速成運(yùn)煤重要通道 .由于南方氣溫的快速升高，南方地區(qū)由于南

29、方氣溫的快速升高，南方地區(qū)用電壓力增加，電煤需求隨之增大。訂單的增多，導(dǎo)致他們用電壓力增加，電煤需求隨之增大。訂單的增多，導(dǎo)致他們需要新購(gòu)大量貨車，京藏高速堵車也隨之產(chǎn)生。需要新購(gòu)大量貨車，京藏高速堵車也隨之產(chǎn)生。 2. 取煤源頭由晉轉(zhuǎn)蒙取煤源頭由晉轉(zhuǎn)蒙.大城西煤炭集散地，東西走起來(lái)最長(zhǎng)十大城西煤炭集散地，東西走起來(lái)最長(zhǎng)十七八公里，南北最少也有七八公里，南北最少也有10公里。公里。3. 繞行面臨罰款風(fēng)險(xiǎn)繞行面臨罰款風(fēng)險(xiǎn).這條線路的成本要比京藏高速高出近這條線路的成本要比京藏高速高出近1/3，風(fēng)險(xiǎn)高，絕大部分司機(jī)不會(huì)考慮。風(fēng)險(xiǎn)高，絕大部分司機(jī)不會(huì)考慮。4. 限流卡口、以罰代管加劇擁堵限流卡口、以

30、罰代管加劇擁堵.河北、北京分別在京藏高速河北、北京分別在京藏高速220公里處、公里處、97公里處等地段設(shè)置了對(duì)進(jìn)京大貨車的限流卡公里處等地段設(shè)置了對(duì)進(jìn)京大貨車的限流卡口，從而引發(fā)了連鎖反應(yīng)：因北京境內(nèi)車輛行駛緩慢而推延口，從而引發(fā)了連鎖反應(yīng)：因北京境內(nèi)車輛行駛緩慢而推延至河北境內(nèi)的交通擁堵，因河北境內(nèi)的車輛行駛緩慢而推延至河北境內(nèi)的交通擁堵，因河北境內(nèi)的車輛行駛緩慢而推延至內(nèi)蒙古境內(nèi)的交通擁堵。至內(nèi)蒙古境內(nèi)的交通擁堵。76解決方案1. 開(kāi)辟一條運(yùn)煤的鐵路專線開(kāi)辟一條運(yùn)煤的鐵路專線 。2. 在沿線各收費(fèi)站實(shí)施遠(yuǎn)程、多點(diǎn)限流，根據(jù)配額漸次放行。在沿線各收費(fèi)站實(shí)施遠(yuǎn)程、多點(diǎn)限流，根據(jù)配額漸次放行。3

31、. 內(nèi)蒙古對(duì)京藏高速公路內(nèi)蒙古段實(shí)施單雙號(hào)限行管制內(nèi)蒙古對(duì)京藏高速公路內(nèi)蒙古段實(shí)施單雙號(hào)限行管制 。4. 張家口地區(qū)的非進(jìn)京大型貨車，特別是運(yùn)煤車輛，一律繞行張家口地區(qū)的非進(jìn)京大型貨車，特別是運(yùn)煤車輛，一律繞行國(guó)、省道，嚴(yán)禁通行京張、丹拉、宣大、張石高速公路。國(guó)、省道，嚴(yán)禁通行京張、丹拉、宣大、張石高速公路。 5. 北京市交通委則表示，每晚北京市交通委則表示，每晚22點(diǎn)至次日點(diǎn)至次日4點(diǎn)，在昌平區(qū)西關(guān)環(huán)點(diǎn)，在昌平區(qū)西關(guān)環(huán)島分流貨車，貨車全部經(jīng)京藏高速出京，在此時(shí)段，國(guó)道島分流貨車，貨車全部經(jīng)京藏高速出京，在此時(shí)段，國(guó)道110舊線雙行改進(jìn)京單行，增加一條進(jìn)京車道。同時(shí)，為確保八舊線雙行改進(jìn)京單行

32、，增加一條進(jìn)京車道。同時(shí)，為確保八達(dá)嶺旅游車輛通行，每日達(dá)嶺旅游車輛通行，每日6點(diǎn)至點(diǎn)至15點(diǎn)，京藏高速出京方向禁止點(diǎn)，京藏高速出京方向禁止大貨車通行，貨車經(jīng)由大貨車通行，貨車經(jīng)由110舊線出京。舊線出京。 77物流系統(tǒng)優(yōu)化的常用方法 解析方法優(yōu)點(diǎn)：最準(zhǔn)確！缺點(diǎn)：難以表現(xiàn)物流活動(dòng)的全貌. 仿真方法（實(shí)驗(yàn)技術(shù)）優(yōu)點(diǎn)：適合于大型、復(fù)雜和多元的物流問(wèn)題。缺點(diǎn)：仿真模型的建立及結(jié)果的分析。 啟發(fā)方法優(yōu)點(diǎn)：具有很好的操作性，符合人的思維。缺點(diǎn)：適用于特定問(wèn)題。78 第四節(jié)第四節(jié) 優(yōu)化方法在物流管理中的作用及應(yīng)優(yōu)化方法在物流管理中的作用及應(yīng)用難點(diǎn)分析用難點(diǎn)分析 一、優(yōu)化方法在物流管理中的作用分析79二、優(yōu)化方法在物流管理中的應(yīng)用難點(diǎn)分析對(duì)現(xiàn)代物流管理理念的理解與把握 現(xiàn)代物流管理的核心是：協(xié)調(diào)與合作！優(yōu)化模型的建立與求解技術(shù) 系統(tǒng)優(yōu)化的范圍越來(lái)越廣，集成越來(lái)越強(qiáng)！物流優(yōu)化方案的有效實(shí)施與不斷改進(jìn) 注意考慮對(duì)物流系統(tǒng)優(yōu)化方案的實(shí)施效果影響較大的一些外界因素！80案例1背景 新產(chǎn)品的不斷涌現(xiàn), 大量廢舊家電被棄置, 勢(shì)必造成嚴(yán)重環(huán)境污染。電冰箱中的制冷劑CFC- 12 和發(fā)泡劑CFC- 11會(huì)破壞臭氧層。一臺(tái)電腦所需要的700 多種化學(xué)原料中, 50%以上對(duì)人體有害，一臺(tái)電腦顯示器中僅含鉛