第3章輸配送系統(tǒng)規(guī)劃王轉(zhuǎn)北京科技大學(xué)機(jī)械工程學(xué)院2010年9月輸配送系統(tǒng)規(guī)劃主要內(nèi)容3.1輸配送系統(tǒng)概述3.2輸配送系統(tǒng)規(guī)劃3.3輸配送線路優(yōu)化3.4輸配送系統(tǒng)合理化輸配送系統(tǒng)規(guī)劃3.1輸配送系統(tǒng)概述1輸送與配送的定義2輸配送系統(tǒng)的構(gòu)成3車輛輸配送服務(wù)要點(diǎn)輸配送系統(tǒng)規(guī)劃輸送是作長(zhǎng)距離大量貨物之移動(dòng)輸送是與距離無關(guān)之據(jù)點(diǎn)間貨物的移動(dòng)輸送是區(qū)域間貨物之移動(dòng)一臺(tái)貨車對(duì)一個(gè)送貨地點(diǎn)作一次往返送貨運(yùn)輸（輸送）1.輸配送定義配送是作短距離少量貨物的移動(dòng)配送是從企業(yè)送達(dá)顧客處的移動(dòng)配送是區(qū)域內(nèi)貨物的移動(dòng)一臺(tái)貨車對(duì)多處客戶點(diǎn)作巡回送貨稱為配送

配送輸配送系統(tǒng)規(guī)劃輸配送含義針對(duì)配送中心來說由工廠將貨物送至配送中心的過程是輸送，屬于少品種、大量、長(zhǎng)距離的運(yùn)送；由配送中心將貨品送到客戶手中的活動(dòng)是配送，屬于多頻率、多樣少量、短距離的運(yùn)送。輸送和配送的區(qū)別輸送較重視效率，以裝載率優(yōu)先，希望每次載愈多愈有利；配送則以服務(wù)為目標(biāo)，以滿足客戶服務(wù)要求為優(yōu)先配送半徑：30-50公里輸配送系統(tǒng)規(guī)劃2.輸配送系統(tǒng)構(gòu)成輸配送系統(tǒng)是由運(yùn)輸網(wǎng)絡(luò)中的運(yùn)輸路線和集散站的倉(cāng)儲(chǔ)設(shè)施結(jié)合而構(gòu)成的。輸配送系統(tǒng)的基本框架：“配送一輸送一配送”模式輸配送系統(tǒng)規(guī)劃營(yíng)業(yè)所營(yíng)業(yè)所現(xiàn)代化的輸配送系統(tǒng)運(yùn)輸包括主線輸送和集散輸送主線輸送是指運(yùn)轉(zhuǎn)站間的運(yùn)輸;集散輸送是指轉(zhuǎn)運(yùn)站將貨物分散至各營(yíng)業(yè)所的運(yùn)輸集配指營(yíng)業(yè)所與顧客間的集貨與配送作業(yè)集散輸送集散輸送輸配送系統(tǒng)規(guī)劃3.輸配送服務(wù)要點(diǎn)時(shí)效性：確保能在指定的時(shí)間內(nèi)交貨時(shí)效性是流通業(yè)客戶最重視的因素可靠性：可靠性指將貨品完好無缺地送達(dá)目的地。如：裝卸貨時(shí)的細(xì)心程度；運(yùn)送過程對(duì)貨品的保護(hù)對(duì)客戶地點(diǎn)及作業(yè)環(huán)境的了解配送人員的職業(yè)道德溝通性配送人員應(yīng)與顧客做相對(duì)的溝通，且具備良好的服務(wù)態(tài)度從而維護(hù)公司的形象，鞏固客戶的忠誠(chéng)度便利性：例如緊急送貨、信息傳送、順道退貨、輔助資源回收等經(jīng)濟(jì)性：控制成本，收費(fèi)較低輸配送系統(tǒng)規(guī)劃3.2輸配送線路規(guī)劃輸配送線路規(guī)劃問題配送計(jì)劃與決策行車路線和時(shí)刻表的制定輸配送系統(tǒng)規(guī)劃1.輸配送系統(tǒng)規(guī)劃問題（1）單一路徑規(guī)劃（2）多個(gè)起訖點(diǎn)的路徑規(guī)劃（3）起點(diǎn)和終點(diǎn)相同的路徑規(guī)劃輸配送系統(tǒng)規(guī)劃（1）單一路徑規(guī)劃——最短路徑法問題：已知各個(gè)節(jié)點(diǎn)之間的行車時(shí)間，節(jié)點(diǎn)代表公路的連接處，要求找到由A點(diǎn)到B點(diǎn)之間行車時(shí)間最短的路線。2023/12/611輸配送系統(tǒng)規(guī)劃輸配送系統(tǒng)規(guī)劃（2）多起訖點(diǎn)問題——線性規(guī)劃某制造商有3家工廠，與三個(gè)位于不同地點(diǎn)的供應(yīng)商簽訂合同，由它們供貨給三個(gè)工廠，條件是不超過合同所定的數(shù)量，但必須滿足生產(chǎn)需求。已知各運(yùn)輸線路上每噸貨物的運(yùn)輸費(fèi)率。要求具體的調(diào)運(yùn)方案。2023/12/612輸配送系統(tǒng)規(guī)劃線性規(guī)劃問題輸配送系統(tǒng)規(guī)劃（3）巡回路徑問題——流動(dòng)推銷員適用場(chǎng)合從中央配送中心送貨到食品店或藥店從零售店到客戶的配送(商店送貨上門)校車、送報(bào)車、垃圾收集車和送餐車等的路線目標(biāo)：找出途經(jīng)點(diǎn)的順序，使其滿足必須經(jīng)過所有點(diǎn)且總出行時(shí)間或總距離最短的要求。輸配送系統(tǒng)規(guī)劃求解方法感知式合理的經(jīng)停路線中各條線路之間是不交叉的；并且只要有可能路徑就會(huì)呈凸形，或水滴狀。啟發(fā)式輸配送系統(tǒng)規(guī)劃2.配送計(jì)劃與決策1)配送計(jì)劃工作要點(diǎn)中長(zhǎng)期經(jīng)營(yíng)計(jì)劃經(jīng)辦計(jì)劃主要顧客分析人員采用/培訓(xùn)計(jì)劃*增車/車檢計(jì)劃*季節(jié)變動(dòng)車輛分配人員分配運(yùn)行計(jì)劃*勤務(wù)計(jì)劃*作業(yè)要點(diǎn)配送計(jì)劃*（1）配送計(jì)劃輸配送系統(tǒng)規(guī)劃配送業(yè)務(wù)流程訂單受理訂單品種/配送數(shù)量/時(shí)間訂單處理駕駛?cè)請(qǐng)?bào)表*配送計(jì)劃*1.駕駛分配2.配送路線3.里程數(shù)4.時(shí)間5.車量限制6.搬運(yùn)作業(yè)7.條件限制8.優(yōu)先順序作業(yè)指示單駕駛記錄表*裝載作業(yè)裝卸作業(yè)輸配送系統(tǒng)規(guī)劃（2）車輛排程系統(tǒng)(V.S.S)車輛排程系統(tǒng)(VehicleSchedulingSystem簡(jiǎn)稱V.S.S)

INPUTOUTPUT道路網(wǎng)分析（1）道路網(wǎng)資料：*倉(cāng)庫(kù)位置*顧客位置*十字路*行車距離*道路分析*單向行駛信號(hào)（2）區(qū)域范圍分割資料：*倉(cāng)庫(kù)管轄范圍*倉(cāng)庫(kù)所屬顧客最短途徑*時(shí)間上的最短途徑*距離上的最短途徑*最短途徑的路徑*區(qū)域范圍分割記錄配送計(jì)劃（1）車輛資料：*車種*能力*臺(tái)數(shù)（2）訂購(gòu)資料：*顧客編碼*希望配送時(shí)間*商品*數(shù)量*其它（3）在庫(kù)資料：*倉(cāng)庫(kù)別、商品別在庫(kù)量*其它（1）配送時(shí)間表：*哪輛車*何時(shí)*至何地*攜帶什么貨*其它（2）利用率：*車輛利用狀況*配送狀況（3）區(qū)域范圍分割結(jié)果：*哪個(gè)倉(cāng)庫(kù)配送哪些客戶輸配送系統(tǒng)規(guī)劃（3）配送規(guī)劃與決策劃分基本配送區(qū)域依據(jù)客戶所在地點(diǎn)的遠(yuǎn)近、關(guān)聯(lián)狀況決定配送基本分區(qū)決定配送批次按貨品性質(zhì)差異分批配送，例如生鮮食品與一般食品的運(yùn)送工具不同，需要分批配送初步確定配送先后次序根據(jù)「客戶的交貨時(shí)間」初步確定配送的先后次序車輛安排根據(jù)各客戶的訂貨量、訂貨體積、重量、客戶點(diǎn)環(huán)境、運(yùn)輸費(fèi)用確定自有車輛/外雇車輛1）配送規(guī)劃流程輸配送系統(tǒng)規(guī)劃決定車輛負(fù)責(zé)客戶路徑選擇根據(jù)「各客戶點(diǎn)的位置關(guān)聯(lián)性」及「交通狀況」優(yōu)化配送路徑的選擇配送順序按車輛的調(diào)度安排及配送路徑確定配送順序車輛裝載方式根據(jù)客戶的配送順序，按「后送達(dá)先上車」的順序裝車配送規(guī)劃流程輸配送系統(tǒng)規(guī)劃配送規(guī)劃要素客戶分布情況訂單特性客戶交貨時(shí)間客戶的訂量、體積、重量車輛的數(shù)量、最大載重量運(yùn)送成本客戶點(diǎn)下貨特征客戶分布情況訂單特性客戶交貨時(shí)間貨物的性質(zhì)、形狀、容積、重量劃分基本配送區(qū)域決定配送批次配送先后次序車輛安排車輛負(fù)責(zé)客戶路徑選擇配送順序車輛裝載方式輸配送系統(tǒng)規(guī)劃3.行車路線與計(jì)劃行車路線和時(shí)刻表問題行車路線和時(shí)刻表制定原則制定行車路線與計(jì)劃的方法運(yùn)輸路線的排序輸配送系統(tǒng)規(guī)劃（1）行車路線和時(shí)刻表問題問題描述：有多輛卡車從倉(cāng)庫(kù)出發(fā)，送貨到若干個(gè)站點(diǎn)，然后在當(dāng)天返回倉(cāng)庫(kù)，要求制定行車路線和時(shí)刻表。實(shí)際的限制條件在每個(gè)站點(diǎn)既要取一定量的貨，又要送一定量的貨；使用多部車輛，每部車的載貨重量和容積不同；司機(jī)的總駕駛時(shí)間達(dá)到一定上限時(shí)，就必須休息至少8小時(shí)(運(yùn)輸部門的安全限制)；每個(gè)站點(diǎn)每天只允許在特定的時(shí)間內(nèi)取貨和／或送貨(稱為時(shí)間窗口（TimeWindow）)；途中只有在送貨后才能取貨；允許駕駛員每天在特定的時(shí)間休息和用餐。解法：制定合理路線和時(shí)刻表的原則啟發(fā)式求解法輸配送系統(tǒng)規(guī)劃（2）路線和時(shí)間表的制定原則（1）1)安排車輛負(fù)責(zé)相互距離最接近的站點(diǎn)的貨物運(yùn)輸。輸配送系統(tǒng)規(guī)劃路線和時(shí)間表的制定原則（2）2)安排車輛每日途經(jīng)的站點(diǎn)時(shí)，應(yīng)注意使站點(diǎn)群更加緊湊輸配送系統(tǒng)規(guī)劃路線和時(shí)間表的制定原則（3）3)從距倉(cāng)庫(kù)最遠(yuǎn)的站點(diǎn)開始設(shè)計(jì)路線4)卡車的行車路線應(yīng)呈水滴狀5)盡可能使用最大的車輛進(jìn)行運(yùn)送，這樣設(shè)計(jì)出的路線是最有效的6)取貨、送貨應(yīng)該混合安排，不應(yīng)該在完成全部送貨任務(wù)之后再取貨7)對(duì)過于遙遠(yuǎn)而無法歸入群落的站點(diǎn)，可以采用其它配送方式8)避免時(shí)間窗口過短輸配送系統(tǒng)規(guī)劃配送中心客戶1342561171012（2）節(jié)約法列出距離矩陣列出節(jié)省矩陣將客戶分配到車輛或路徑上在路徑內(nèi)將客戶排序（3）制定行車路線與計(jì)劃方法（1）掃描法2023/12/626輸配送系統(tǒng)規(guī)劃輸配送系統(tǒng)規(guī)劃掃描法(TheSweepMethod)(1)在地圖或方格圖中確定所有站點(diǎn)(含倉(cāng)庫(kù))的位置。(2)自倉(cāng)庫(kù)始沿任一方向向外劃一條直線。沿順時(shí)針或逆時(shí)針方向旋轉(zhuǎn)該直線直到與某站點(diǎn)相交。(3)排定各路線上每個(gè)站點(diǎn)的順序使行車距離最短。排序時(shí)可以使用“水滴”法或者采用“流動(dòng)推銷員”問題的算法。輸配送系統(tǒng)規(guī)劃例子某運(yùn)輸公司用廂式貨車從貨主那里取貨。貨物先運(yùn)回倉(cāng)庫(kù)，集中后以更大的批量進(jìn)行長(zhǎng)途運(yùn)輸。圖中列出了典型的一天的取貨量，取貨量單位是件。廂式貨車的載貨量是10000件。需要多少條運(yùn)輸路線(即多少部車)，每條路線上應(yīng)該經(jīng)過哪些站點(diǎn)，每條路線上的站點(diǎn)應(yīng)該怎樣排序輸配送系統(tǒng)規(guī)劃（4）運(yùn)輸路線的排序?qū)⑺羞\(yùn)輸路線首尾相連按順序排列，使車輛的空閑時(shí)間最短。

輸配送系統(tǒng)規(guī)劃運(yùn)輸路線的排序例子2023/12/630輸配送系統(tǒng)規(guī)劃輸配送系統(tǒng)規(guī)劃3.3輸配送線路優(yōu)化運(yùn)輸路線優(yōu)化配送計(jì)劃優(yōu)化（0-1規(guī)劃法）制定配送計(jì)劃的節(jié)約法輸配送系統(tǒng)規(guī)劃1.運(yùn)輸路線優(yōu)化（1）直達(dá)運(yùn)輸線路優(yōu)化模型問題描述：已知有m個(gè)生產(chǎn)地點(diǎn)Ai，i＝1，2，…，m，可供應(yīng)某種物資，其供應(yīng)量分別為ai，i＝1，2，…，m，有n個(gè)銷地（需求地）Bj，j＝1，2，…，n，其需求量分別為bj，j＝1，2，…，n，從Ai到Bj運(yùn)輸單位物資的運(yùn)價(jià)為Cij。整理成如表3-2所示產(chǎn)銷平衡表和單位運(yùn)價(jià)表。用xij表示從Ai到Bj的運(yùn)量，其數(shù)學(xué)模型如下：

（3-1）輸配送系統(tǒng)規(guī)劃（2）中轉(zhuǎn)運(yùn)輸線路優(yōu)化模型問題描述產(chǎn)地與銷地之間沒有直達(dá)路線，貨物由產(chǎn)地到銷地必須通過某中間站轉(zhuǎn)運(yùn)。某些產(chǎn)地既輸出貨物，也吸收一部分貨物；某銷地既吸收貨物，又輸出部分貨物，即產(chǎn)地或銷地也可以起中轉(zhuǎn)站的作用，或者既是產(chǎn)地又是銷地。產(chǎn)地與銷地之間雖然有直達(dá)路線，但直達(dá)運(yùn)輸?shù)馁M(fèi)用或運(yùn)輸距離分別比經(jīng)過某些中轉(zhuǎn)站還要高或遠(yuǎn)。存在以上情況的運(yùn)輸問題，統(tǒng)稱為轉(zhuǎn)運(yùn)問題。數(shù)學(xué)模型基本思路：化為無轉(zhuǎn)運(yùn)的平衡運(yùn)輸問題假設(shè)：首先根據(jù)具體問題求出最大可能中轉(zhuǎn)量Q（Q是大于總產(chǎn)量

的一個(gè)數(shù)）；純中轉(zhuǎn)站可視為輸出量和輸入量均為Q的一個(gè)產(chǎn)地和銷地。兼中轉(zhuǎn)站的產(chǎn)地

可視為一個(gè)輸入量為Q的銷地及一個(gè)產(chǎn)量為ai+Q的產(chǎn)地。兼中轉(zhuǎn)站的

可視為一個(gè)輸出量為Q的產(chǎn)地及一個(gè)銷量為

的銷地。輸配送系統(tǒng)規(guī)劃中轉(zhuǎn)運(yùn)輸線路優(yōu)化模型輸配送系統(tǒng)規(guī)劃中轉(zhuǎn)運(yùn)輸線路優(yōu)化模型

（3-2）輸配送系統(tǒng)規(guī)劃2.配送計(jì)劃優(yōu)化（0-1規(guī)劃法）問題描述單網(wǎng)點(diǎn)配送問題中，物流網(wǎng)點(diǎn)向所屬用戶送貨，各用戶的需求量為bj（j＝1，2，…，n）。假定以汽車作為發(fā)送工具，每臺(tái)汽車的載重量為Q，若滿足則該網(wǎng)點(diǎn)只需派一臺(tái)汽車巡回送貨即可，即所謂的“旅行推銷員”問題設(shè)B0為物流網(wǎng)點(diǎn)，Bj（j＝1，2，…，n）為需求用戶。顯然，一個(gè)可行的循回路線應(yīng)由n＋1段路線構(gòu)成，以Xijr（i＝0，1，2，…，n；j＝0，1，2，…，n；r＝1，2，…，n＋1，i≠j）表示i-j段路線作為某巡回路線中第r段行程的決策變量，當(dāng)Xijr＝l時(shí)表示該段行程在巡回路線上，當(dāng)Xijr＝0時(shí)表示該段行程不在巡回路線上。輸配送系統(tǒng)規(guī)劃（0，1）規(guī)劃模型這是一個(gè)0-1規(guī)劃模型。解0-1規(guī)劃模型可用窮舉法和隱枚舉法輸配送系統(tǒng)規(guī)劃3.制定配送計(jì)劃的節(jié)約法

（3-1）當(dāng)時(shí)，不僅要進(jìn)行巡回路線的選擇。而且還要進(jìn)行車輛的綜合調(diào)度節(jié)約法是由克拉克（Clarke）和懷特（Wright）于1964年提出來的，它是一種啟發(fā)式方法節(jié)約法的基本原理△C12＝C01＋C02－C12>0B0B2B1C01C02C12輸配送系統(tǒng)規(guī)劃節(jié)約法問題描述輸配送系統(tǒng)規(guī)劃節(jié)約法求解過程初始可行方案首先假定載重量最小的汽車臺(tái)數(shù)是無限多的，即Xl＝∞。對(duì)每一用戶各派一臺(tái)車往返送貨，得到一初始可行方案按節(jié)約法原理對(duì)方案進(jìn)行修正修正時(shí)。以節(jié)約量的大小為順序，從大到小依次將某些用戶連接到巡回路線中，并考慮汽車載重量和各種車輛臺(tái)數(shù)的約束。反復(fù)進(jìn)行這樣的修正，直至再?zèng)]有可連接的用戶時(shí)為止[例3-2]由網(wǎng)點(diǎn)B0向12個(gè)用戶Bj（j＝1，2，…，。12）送貨，各點(diǎn)之間的運(yùn)輸里程和各用戶的需求量見表3-7。表3-8為可供調(diào)度的車輛數(shù)目及其載重量。輸配送系統(tǒng)規(guī)劃3.4輸配送系統(tǒng)合理化輸配送效率化目標(biāo)輸配送系統(tǒng)合理化途徑提高配送效率的實(shí)踐輸配送系統(tǒng)規(guī)劃1.輸配送效率化目標(biāo)輸配送效率化目標(biāo)“距離最小”“時(shí)間最小”“成本最小”合理化的方向提高每次輸配送量提高車輛運(yùn)行速率削減車輛使用臺(tái)數(shù)縮短輸配送距離適當(dāng)配置物流設(shè)施據(jù)點(diǎn)輸配送系統(tǒng)規(guī)劃2.輸配送合理化的途徑（1）消除交錯(cuò)輸送（2）回程車的利用輸配送系統(tǒng)規(guī)劃輸配送合理化的途徑（3）直配、直送零售業(yè)批發(fā)業(yè)廠商廠商配送中心訂購(gòu)訂購(gòu)出貨指示配送輸配送系統(tǒng)規(guī)劃輸配送合理化的途徑（4）信息系統(tǒng)的建立物流信息系統(tǒng)一般由訂單處理、庫(kù)存管理、出貨計(jì)劃管理、輸配送管理等四個(gè)子系統(tǒng)構(gòu)成出貨計(jì)劃管理及輸配送管理子系統(tǒng)的功能：①自動(dòng)選擇最適合的輸送手段：根據(jù)交貨配送時(shí)間、車輛最大積載量、客戶的訂貨量、個(gè)數(shù)、重量來選出一個(gè)最經(jīng)濟(jì)的輸配送方法。②配車計(jì)劃的自動(dòng)形成：根據(jù)貨物的形狀、容積、重量及車輛的能力等，由電腦自動(dòng)安排車輛或裝載方式。③配送路線的自動(dòng)生成：在信息系統(tǒng)中輸入每一客戶點(diǎn)的位置，電腦便會(huì)依最短距離找出最便捷路徑。輸配送系統(tǒng)規(guī)劃輸配送合理化的途徑（5