輸配送系統(tǒng)規(guī)劃課件

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

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

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

輸配送系統(tǒng)規(guī)劃（4）運輸路線的排序?qū)⑺羞\輸路線首尾相連按順序排列，使車29運輸路線的排序例子2022/12/330輸配送系統(tǒng)規(guī)劃輸配送系統(tǒng)規(guī)劃運輸路線的排序例子2022/12/130輸配送系統(tǒng)規(guī)劃輸配送303.3輸配送線路優(yōu)化運輸路線優(yōu)化配送計劃優(yōu)化（0-1規(guī)劃法）制定配送計劃的節(jié)約法輸配送系統(tǒng)規(guī)劃3.3輸配送線路優(yōu)化運輸路線優(yōu)化輸配送系統(tǒng)規(guī)劃311.運輸路線優(yōu)化（1）直達運輸線路優(yōu)化模型問題描述：已知有m個生產(chǎn)地點Ai，i＝1，2，…，m，可供應(yīng)某種物資，其供應(yīng)量分別為ai，i＝1，2，…，m，有n個銷地（需求地）Bj，j＝1，2，…，n，其需求量分別為bj，j＝1，2，…，n，從Ai到Bj運輸單位物資的運價為Cij。整理成如表3-2所示產(chǎn)銷平衡表和單位運價表。用xij表示從Ai到Bj的運量，其數(shù)學(xué)模型如下：

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

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

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

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

的銷地。輸配送系統(tǒng)規(guī)劃（2）中轉(zhuǎn)運輸線路優(yōu)化模型問題描述產(chǎn)地與銷地之間沒有直達路線33中轉(zhuǎn)運輸線路優(yōu)化模型輸配送系統(tǒng)規(guī)劃中轉(zhuǎn)運輸線路優(yōu)化模型輸配送系統(tǒng)規(guī)劃34中轉(zhuǎn)運輸線路優(yōu)化模型

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

（3-1）當(dāng)時，不僅要進行巡回路線的選擇。而且還要進行車輛的綜合調(diào)度節(jié)約法是由克拉克（Clarke）和懷特（Wright）于1964年提出來的，它是一種啟發(fā)式方法節(jié)約法的基本原理△C12＝C01＋C02－C12>0B0B2B1C01C02C12輸配送系統(tǒng)規(guī)劃3.制定配送計劃的節(jié)約法38節(jié)約法問題描述輸配送系統(tǒng)規(guī)劃節(jié)約法問題描述輸配送系統(tǒng)規(guī)劃39節(jié)約法求解過程初始可行方案首先假定載重量最小的汽車臺數(shù)是無限多的，即Xl＝∞。對每一用戶各派一臺車往返送貨，得到一初始可行方案按節(jié)約法原理對方案進行修正修正時。以節(jié)約量的大小為順序，從大到小依次將某些用戶連接到巡回路線中，并考慮汽車載重量和各種車輛臺數(shù)的約束。反復(fù)進行這樣的修正，直至再沒有可連接的用戶時為止[例3-2]由網(wǎng)點B0向12個用戶Bj（j＝1，2，…，。12）送貨，各點之間的運輸里程和各用戶的需求量見表3-7。表3-8為可供調(diào)度的車輛數(shù)目及其載重量。輸配送系統(tǒng)規(guī)劃節(jié)約法求解過程初始可行方案輸配送系統(tǒng)規(guī)劃403.4輸配送系統(tǒng)合理化輸配送效率化目標(biāo)輸配送系統(tǒng)合理化途徑提高配送效率的實踐輸配送系統(tǒng)規(guī)劃3.4輸配送系統(tǒng)合理化輸配送效率化目標(biāo)輸配送系統(tǒng)規(guī)劃411.輸配送效率化目標(biāo)輸配送效率化目標(biāo)“距離最小”“時間最小”“成本最小”合理化的方向提高每次輸配送量提高車輛運行速率削減車輛使用臺數(shù)縮短輸配送距離適當(dāng)配置物流設(shè)施據(jù)點輸配送系統(tǒng)規(guī)劃1.輸配送效率化目標(biāo)輸配送效率化目標(biāo)合理化的方向輸配送系統(tǒng)規(guī)422.輸配送合理化的途徑（1）消除交錯輸送（2）回程車的利用輸配送系統(tǒng)規(guī)劃2.輸配送合理化的途徑（1）消除交錯輸送輸配送系統(tǒng)規(guī)劃43輸配送合理化的途徑（3）直配、直送零售業(yè)批發(fā)業(yè)廠商廠商配送中心訂購訂購出貨指示配送輸配送系統(tǒng)規(guī)劃輸配送合理化的途徑（3）直配、直送零售業(yè)批發(fā)業(yè)廠商廠商配送44輸配送合理化的途徑（4）信息系統(tǒng)的建立物流信息系統(tǒng)一般由訂單處理、庫存管理、出貨計劃管理、輸配送管理等四個子系統(tǒng)構(gòu)成出貨計劃管理及輸配送管理子系統(tǒng)的功能：①自動選擇最適合的輸送手段：根據(jù)交貨配送時間、車輛最大積載量、客戶的訂貨量、個數(shù)、重量來選出一個最經(jīng)濟的輸配送方法。②配車計劃的自動形成：根據(jù)貨物的形狀、容積、重量及車輛的能力等，由電腦自動安排車輛或裝載方式。③配送路線的自動生成：在信息系統(tǒng)中輸入每一客戶點的位置，電腦便會依最短距離找出最便捷路徑。輸配送系統(tǒng)規(guī)劃輸配送合理化的途徑（4）信息系統(tǒng)的建立出貨計劃管理及輸配送管45輸配送合理化的途徑（5）改善運行車輛的通信條件通信系統(tǒng)可以隨時掌握以下信息及狀況a.車輛及司機的狀況b.道路信息或氣象信息c.車輛作業(yè)狀況及裝載狀況d.進行作業(yè)指示e.傳達緊急的信息f.提高運行效率及安全運轉(zhuǎn)g.把握運行車輛的所在地輸配送系統(tǒng)規(guī)劃輸配送合理化的途徑（5）改善運行車輛的通信條件輸配送系統(tǒng)規(guī)劃46輸配送合理化的途徑（6）控制出貨量a.給予大量訂貨客戶折扣b.訂定最低訂貨量c.調(diào)整交貨時間d.對于季節(jié)性的變動盡可宣導(dǎo)客戶提早預(yù)約輸配送系統(tǒng)規(guī)劃輸配送合理化的途徑（6）控制出貨量輸配送系統(tǒng)規(guī)劃47輸配送合理化的途徑（7）共同配送所謂“共同配送”，是指多家企業(yè)共同參與只由一家物流公司獨自進行的配送作業(yè)。共同配送的類型水平式的共同配送：在批發(fā)商店及代理商店之間進行的是一種水平式的共同配送，垂直式的共同配送：由制造商主導(dǎo)來整合批發(fā)業(yè)的配送，或由連鎖店總部主導(dǎo)來整合供貨廠商的配送

輸配送系統(tǒng)規(guī)劃輸配送合理化的途徑（7）共同配送輸配送系統(tǒng)規(guī)劃483.提高配送效率的實踐提高配送營運效率時間配送順道回收紙箱能節(jié)省大量成本道路品質(zhì)的改善、人力調(diào)派、車輛調(diào)派及路線安排技術(shù)計算機配車、配載、線路優(yōu)化GPS技術(shù)規(guī)定市區(qū)商業(yè)區(qū)設(shè)立卸貨站托盤規(guī)格標(biāo)準化車輛間的通訊建立共同配送中心輸配送系統(tǒng)規(guī)劃3.提高配送效率的實踐提高配送營運效率時間配49本章小結(jié)輸配送系統(tǒng)概述輸配送定義輸配送系統(tǒng)的構(gòu)成輸配送服務(wù)要點輸配送系統(tǒng)規(guī)劃輸配送系統(tǒng)規(guī)劃問題配送計劃與決策行車路線和時刻表的制定輸配送系統(tǒng)優(yōu)化運輸路線配送優(yōu)化：（0，1）優(yōu)化、節(jié)約法輸配送系統(tǒng)合理化提高輸配送運行效率的方法配送決策流程配送規(guī)劃要素配送計劃及相關(guān)表單輸配送系統(tǒng)規(guī)劃本章小結(jié)輸配送系統(tǒng)概述輸配送定義輸配送系統(tǒng)的構(gòu)成輸配送服務(wù)要50第3章輸配送系統(tǒng)規(guī)劃王轉(zhuǎn)北京科技大學(xué)機械工程學(xué)院2010年9月輸配送系統(tǒng)規(guī)劃第3章輸配送系統(tǒng)規(guī)劃王轉(zhuǎn)輸配送系統(tǒng)規(guī)劃51主要內(nèi)容3.1輸配送系統(tǒng)概述3.2輸配送系統(tǒng)規(guī)劃3.3輸配送線路優(yōu)化3.4輸配送系統(tǒng)合理化輸配送系統(tǒng)規(guī)劃主要內(nèi)容3.1輸配送系統(tǒng)概述3.2輸配送系統(tǒng)規(guī)劃3.3523.1輸配送系統(tǒng)概述1輸送與配送的定義2輸配送系統(tǒng)的構(gòu)成3車輛輸配送服務(wù)要點輸配送系統(tǒng)規(guī)劃3.1輸配送系統(tǒng)概述1輸送與配送的定義輸配送系統(tǒng)規(guī)劃53輸送是作長距離大量貨物之移動輸送是與距離無關(guān)之據(jù)點間貨物的移動輸送是區(qū)域間貨物之移動一臺貨車對一個送貨地點作一次往返送貨運輸（輸送）1.輸配送定義配送是作短距離少量貨物的移動配送是從企業(yè)送達顧客處的移動配送是區(qū)域內(nèi)貨物的移動一臺貨車對多處客戶點作巡回送貨稱為配送

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

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

輸配送系統(tǒng)規(guī)劃（4）運輸路線的排序?qū)⑺羞\輸路線首尾相連按順序排列，使車79運輸路線的排序例子2022/12/380輸配送系統(tǒng)規(guī)劃輸配送系統(tǒng)規(guī)劃運輸路線的排序例子2022/12/130輸配送系統(tǒng)規(guī)劃輸配送803.3輸配送線路優(yōu)化運輸路線優(yōu)化配送計劃優(yōu)化（0-1規(guī)劃法）制定配送計劃的節(jié)約法輸配送系統(tǒng)規(guī)劃3.3輸配送線路優(yōu)化運輸路線優(yōu)化輸配送系統(tǒng)規(guī)劃811.運輸路線優(yōu)化（1）直達運輸線路優(yōu)化模型問題描述：已知有m個生產(chǎn)地點Ai，i＝1，2，…，m，可供應(yīng)某種物資，其供應(yīng)量分別為ai，i＝1，2，…，m，有n個銷地（需求地）Bj，j＝1，2，…，n，其需求量分別為bj，j＝1，2，…，n，從Ai到Bj運輸單位物資的運價為Cij。整理成如表3-2所示產(chǎn)銷平衡表和單位運價表。用xij表示從Ai到Bj的運量，其數(shù)學(xué)模型如下：

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

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

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

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

的銷地。輸配送系統(tǒng)規(guī)劃（2）中轉(zhuǎn)運輸線路優(yōu)化模型問題描述產(chǎn)地與銷地之間沒有直達路線83中轉(zhuǎn)運輸線路優(yōu)化模型輸配送系統(tǒng)規(guī)劃中轉(zhuǎn)運輸線路優(yōu)化模型輸配送系統(tǒng)規(guī)劃84中轉(zhuǎn)運輸線路優(yōu)化模型

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

（3-1）當(dāng)時，不僅要進行巡回路線的選擇。而且還要進行車輛的綜合調(diào)度節(jié)約法是由克拉克（Clarke）和懷特（Wright）于1964年提出來的，它是一種啟發(fā)式方法節(jié)約法的基本原理△C12＝C01＋C02－C12>0B0B2B1C01C02C12輸配送系統(tǒng)規(guī)劃3.制定配送計劃的節(jié)約法88節(jié)約法問題描述輸配送系統(tǒng)規(guī)劃節(jié)約法問題描述輸配送系統(tǒng)規(guī)劃89節(jié)約法求解過程初始可行方案首先假定載重量最小的汽車臺數(shù)是無限多的，即Xl＝∞。對每一用戶各派一臺車往返送貨，得到一初始可行方案按節(jié)約法原理對方案進行修正修正時。以節(jié)約量的大小為順序，從大到小依次將某些用戶連接到巡回路線中，并考慮汽車載重量和各種車輛臺數(shù)的約束。反復(fù)進行這樣的修正，直至再沒