【正文】 素（一） 配送功能 配送本質(zhì)上是運(yùn)輸，創(chuàng)造空間效用自然是它的主要功能?！? 但配送不同于運(yùn)輸，它是運(yùn)輸在功能上的延伸。支線運(yùn)輸一般是小批量，使用載重量大的運(yùn)輸工具反倒是一種浪費(fèi)。因此，配送與運(yùn)輸結(jié)合，把干線運(yùn)輸與支線運(yùn)輸統(tǒng)一起來，使運(yùn)輸系統(tǒng)更加完善。由于交叉運(yùn)輸?shù)拇嬖?，使輸送路線長，規(guī)模效益差，運(yùn)輸成本高。因?yàn)樵O(shè)置配送中心以后，將原來直接由各工廠送至各客戶的零散貨物通過配送中心以后，將原來直接由各工廠送至各客戶的零散貨物通過配送中心進(jìn)行整合再實(shí)施配送，緩解了交叉輸送，輸送距離短，成本降低。實(shí)現(xiàn)低庫存或零庫存配送通過集中庫存，在同樣的滿足水平上，可使系統(tǒng)總庫存水平降低，既降低了存儲(chǔ)成本，也節(jié)約了運(yùn)力和其他物流費(fèi)用。簡化手續(xù)，方便用戶由于配送可提供全方位的物流服務(wù)，采用配送方式后，用戶只需向配送提供商進(jìn)行一次委托，就可以得到全過程、多功能的物流服務(wù)，從而簡化了委托手續(xù)和工作量，也節(jié)省了開支。如巴塞羅那大眾物流中心承擔(dān)著為大眾、奧迪、斯柯大、菲亞特等大眾系統(tǒng)四個(gè)品牌的汽車配送零部件的任務(wù)。假如用戶新買的車壞了，只要在歐洲范圍內(nèi)，24 小時(shí)內(nèi)就會(huì)由專門的配送公司把用戶所需要的零部件送到手中。這三個(gè)步驟是由一系列配送作業(yè)環(huán)節(jié)組成的，通過這些環(huán)節(jié)的運(yùn)作，使配送的功能得以實(shí)現(xiàn)。配送的基本功能要素主要包括集貨、分揀、配貨、配裝、送貨等。為了滿足特定用戶的配送要求，有時(shí)需要把用戶從幾家甚至數(shù)十家供應(yīng)商處預(yù)定的物品集中到一處。配送的優(yōu)勢之一，就是通過集貨形成規(guī)模效益。分揀將需要配送的物品從儲(chǔ)位上揀取出來，配備齊全，并按配裝和送貨的要求進(jìn)行分類，送入指定發(fā)貨地點(diǎn)堆放的作業(yè)。成功的分揀，會(huì)大大減少差錯(cuò)，提高配送的服務(wù)質(zhì)量。配裝配裝也稱配載，指充分利用運(yùn)輸工具（如貨車、輪船等）的載重量和容積，采用先進(jìn)的裝載方法，合理安排貨物的裝配。配裝是配送系統(tǒng)中具有現(xiàn)代特點(diǎn)的功能要素，也是配送不同于一般送貨的重要區(qū)別之一。如何確定最佳路線，如何使配裝和路線有效結(jié)合起來，是配送運(yùn)輸?shù)奶攸c(diǎn)，也是難度較大的工作 [9]。TSP 不僅可以解決最有巡回路線等 TSP 問題，在交通車輛巡回、學(xué)校教師課程安排、工廠裝配線進(jìn)度管理以及民航機(jī)組人員輪班等問題上也有著廣泛的應(yīng)用前景。要求合理安排其旅行路線，使得總旅行距離（或旅行費(fèi)用、旅行時(shí)間等）最短。車輛路線安排問題（VRP,Vehicle Routing Problem）是對進(jìn)行物流配送的車輛進(jìn)行優(yōu)化調(diào)度。VRP 問題由 Dantzing 和 Ramser 于 1959 年首次提出，該問題一經(jīng)提出，立即引起了運(yùn)籌學(xué)、圖論與網(wǎng)絡(luò)分析、物流科學(xué)、計(jì)算機(jī)應(yīng)用等學(xué)科專家與運(yùn)輸問題制定和管理者的極大關(guān)注，成為運(yùn)籌學(xué)和優(yōu)化科學(xué)研究的前沿和熱點(diǎn)問題。目前，該問題已經(jīng)不再局限于原來的汽車運(yùn)輸問題，在水路和航空運(yùn)輸、工業(yè)管理、電網(wǎng)建設(shè)、通訊工程以及計(jì)算機(jī)應(yīng)用等領(lǐng)域也有相當(dāng)?shù)膽?yīng)用。精確式算法及其應(yīng)用的局限性VRP 問題是組合優(yōu)化領(lǐng)域著名的 NP 難題之一，其求解方法一般相當(dāng)復(fù)雜，通常做法是應(yīng)用相關(guān)技術(shù)將問題分解或者轉(zhuǎn)化為一個(gè)或者多個(gè)已經(jīng)研究過的基本問題（如旅行商問題、指派問題、運(yùn)輸問題、最短路問題、最大流問題、最小費(fèi)用最大流問題、中國郵遞員問題等），再使用相對比較成熟的基本理論和方法進(jìn)行求解，以求得原運(yùn)輸車輛調(diào)度問題的最優(yōu)解或滿意解。在VRP 問題研究的早期，主要是單源點(diǎn)（OnePoint）（即配送中心、車場等）派車，研究如何用最短路線（或在最短時(shí)間內(nèi)）對一定數(shù)量的需求點(diǎn)（即用戶）進(jìn)行車輛調(diào)度，因此主要運(yùn)用精確算法，求出問題的最優(yōu)解。精確算法隨著運(yùn)輸系統(tǒng)的復(fù)雜和調(diào)度目標(biāo)的增加，其計(jì)算量呈指數(shù)遞增，使得獲取中國最大的論文知識(shí)平臺(tái) 整個(gè)系統(tǒng)的精確最優(yōu)解越來越困難，而用計(jì)算機(jī)求解大型優(yōu)化問題的時(shí)間和費(fèi)用又太大了，因此，此類優(yōu)化方法和算法現(xiàn)在一般僅用于求解運(yùn)輸調(diào)度的局部優(yōu)化問題。啟發(fā)式算法能同時(shí)滿足詳細(xì)描繪和求解問題的需要，較精確式算法更加實(shí)用。設(shè)配送中心是 ，m 個(gè)用戶分別是 P1,P2,P3,…,Pm。jdiji如果發(fā)送車輛的噸位已知，并且每一輛車都可以滿載，則研究的目標(biāo)轉(zhuǎn)化為使所有參加發(fā)送的車輛的總發(fā)送距離在滿足約束條件的基礎(chǔ)下最小。如果兩點(diǎn)間的運(yùn)輸不暢通（例如由于橋梁、險(xiǎn)路或交通故障阻塞了某一通道，或者在一段時(shí)間內(nèi)對通過這一段路線的最高貨運(yùn)量高貨運(yùn)量有所限制等），則可以將這些情況轉(zhuǎn)化為相應(yīng)的約束條件列入方程中，然后求解。如圖 25，如果將原來圖 25（a）中由 分別向 和 兩點(diǎn)配送貨物的往返0PiPj運(yùn)輸路線（ 和 ）改為圖 25（b）的 ，0Pi0j 0ij0P則總發(fā)送距離由原來的 2（ ）改變?yōu)?。目前，根據(jù)該方法及其改進(jìn)方法，西方的計(jì)算機(jī)軟件公司開發(fā)了許多成功的車輛優(yōu)化調(diào)度軟件，在實(shí)際應(yīng)用中獲得了良好的經(jīng)濟(jì)效益。現(xiàn)在比較成熟的啟發(fā)式算法很多，它們的區(qū)別主要在于求解過程的收斂速度和收斂程度不同。根據(jù)一些規(guī)則，每一次將不在線路上的點(diǎn)依次增加到線路中去，直到所有的點(diǎn)都被安排進(jìn)去為止。（2）兩階段算法。第一階段得到一個(gè)可行解，第二階段則對解進(jìn)行調(diào)整。該方法經(jīng)常運(yùn)用交互式優(yōu)化技術(shù)，充分發(fā)揮人在求解問題過程中的主觀能動(dòng)性。精確算法中的決策原則，在規(guī)模很大的問題中，導(dǎo)致計(jì)算量的指數(shù)增長。（4）改進(jìn)算法。目前，用并行計(jì)算機(jī)進(jìn)行的并行算法、基于生物遺傳原理的遺傳算法、神經(jīng)網(wǎng)絡(luò)理論等在求解 VRP 問題中也有一定的應(yīng)用和發(fā)展 [15]。在一個(gè)配送中心 P 有一臺(tái)容量為q 的貨車，現(xiàn)在有 n 個(gè)用戶的貨運(yùn)任務(wù)需要完成，已知用戶 i 的貨運(yùn)量是，且有 ，求在滿足各個(gè)用戶需求的條件下，總發(fā)送距離最),.1(ig?qgi???1短的貨車送貨路線。它的解是：從中心 P 出發(fā)，對所有的用戶巡回一次再回到中心的距離最短的路線。表 21 配送中心與用戶之間的距離 （單位：公里）中心 0 中心 0用戶 1 9 用戶 1用戶 2 6 9 用戶 2用戶 3 10 16 8 用戶 3用戶 4 13 18 10 4 用戶 4用戶 5 14 8 11 18 19 用戶 5用戶 6 13 12 8 12 12 9 用戶 6用戶 7 18 15 13 17 16 9 6 用戶 7運(yùn)用 EXCEL2022 中的規(guī)劃求解，可以很快求得車輛路線如表 22。根據(jù)該表，逐次連接用戶，可以得到車輛路線安排如下：0—2—3—4—6—7—5—1—0，該路線距離是 62 公里。設(shè)配送中心按照一定的分類標(biāo)準(zhǔn)把車輛分成 K 種，每一種記為 k（k=1,…,K）裝載量為 ，數(shù)目是 輛。相反，如果 ，即每一輛發(fā)送車??niq1的裝載量都大于所有用戶的總貨運(yùn)量，那么該問題就轉(zhuǎn)化為單車輛的路線安排。首先，假設(shè)向每一個(gè)用戶都派一輛車， (各個(gè)用戶的需要量都小于qgi?最大發(fā)送車的裝載量)以及裝載量最小的車子臺(tái)數(shù)足以安排貨運(yùn)。該用戶剩下的 4 噸作為新的 ，列入原問題中繼續(xù)求解。由于新的 為 4 噸，使得 的giqkgi?假設(shè)依舊成立。如表 23 給出各個(gè)用戶的貨運(yùn)量，表 24 是配送中心、用戶之間的距離，表 25 是連接用戶到同一條線路上的費(fèi)用節(jié)約值（計(jì)算公式同前），表 6 是配送中心可以利用的發(fā)送車的數(shù)目和已經(jīng)安排的發(fā)送車輛數(shù)。表 23 用戶和貨運(yùn)量用戶 1 2 3 4 5 6 7 8貨運(yùn)量（噸） 表 24 配送中心與用戶之間的距離中心 0 中心 0用戶 1 9 用戶 1用戶 2 14 5 用戶 2用戶 3 21 12 7 用戶 3用戶 4 23 22 17 10 用戶 4用戶 5 32 31 26 27 25 用戶 5用戶 6 42 41 36 31 29 10 用戶 6用戶 7 50 49 44 37 31 18 8 用戶 7用戶 8 52 51 46 39 29 20 10 10 用戶 8表 25 用戶連接的費(fèi)用節(jié)約值用戶 1 用戶 1用戶 2 18 用戶 2用戶 3 18 28 用戶 3用戶 4 10 20 34 用戶 4用戶 5 10 20 26 30 用戶 5用戶 6 10 20 32 36 64 用戶 6用戶 7 10 20 34 42 64 84 用戶 7用戶 8 10 20 34 46 64 84 92 用戶 8表 26 發(fā)送車輛數(shù)配送車的類型 4 噸 5 噸 6 噸 可以利用的車輛數(shù) 50 5 4已經(jīng)分配的車輛數(shù) 8 0 0中國最大的論文知識(shí)平臺(tái) 在初始解的基礎(chǔ)上選出具有最大節(jié)約值的格子，如果該格子還滿足：①用戶 i 和用戶 j 不在同一條直線路上；②將原計(jì)劃分別運(yùn)送用戶 i 和用戶 j 的貨物用裝載量大于 的車進(jìn)行運(yùn)送，修改表 26 中已經(jīng)分配的車輛數(shù)，連接用)(gji?戶 i 和 j，修改 的值（ 的含義見表 7 后的注，初始解中ei=2（ i=0， j=1，…，8），其余均為 0），同時(shí)修改 ，直到各用戶e gji??都進(jìn)行過連接為止。表 27 第一次修改后的配送計(jì)劃貨運(yùn)量（噸）中心0中心0 用戶12 用戶1 用戶22 0 用戶2 用戶32 0 0 用戶3 用戶42 0 0 0 用戶4 用戶52 0 0 0 0 用戶5 用戶62 0 0 0 0 0 用戶6 用戶71 0 0 0 0 0 0 用戶7 用戶81 0 0 0 0 0 0 1 用戶8（注：符號 1 表示連接這兩個(gè)用戶，0 表示不連接，2 表示由配送中心給用戶采用直接往返的方式送貨。中國最大的論文知識(shí)平臺(tái) 表 29 再次修改后的配送計(jì)劃貨運(yùn)量（噸）中心0中心0 用戶12 用戶1 用戶22 0 用戶2 用戶31 0 0 用戶3 用戶41 0 0 1 用戶4 用戶51 0 0 0 0 用戶5 用戶61 0 0 0 0 0 用戶6 用戶70 0 0 0 0 1 0 用戶7 用戶80 0 0 0 0 0 1 1 用戶8表 210 再次修改后配送車輛數(shù)配送車輛的類型 4 噸 5 噸 6 噸可以利用的車輛數(shù) 50 5 4已經(jīng)分配的車輛數(shù) 3 0 1繼續(xù)對問題進(jìn)行調(diào)度，得到最終的配送計(jì)劃如表 211 和 212。對理想狀態(tài)下的車輛調(diào)度問題，可以建立數(shù)學(xué)模型如下：配送中心：P ，記為標(biāo)號 0；可用車輛集合是[q,k=1，…，m],q 為載重量；用戶[ 為用戶 i 的貨運(yùn)量，如果可以混裝，則有 ；ginig],.1,? qgi?max用戶 i 到用戶 j 之間的最短距離記為 ；dij定義 01 變量如下：，表示點(diǎn) i 的用戶由車輛 k 完成，否則記 ；yki 0?yki，表示車輛 k 從 i 行駛到點(diǎn) j，否則記 ；1?xj xj?CyXZminSubject to ： qkgi?? i=1，…，n1?ky i=0，… ，n 0ori k j=0，… ，n jXi? i=0，… ，n ykij?? i ，j=0，… ，n 01ori k公式中 表示從點(diǎn) i 到點(diǎn) j 的運(yùn)輸成本，含義可以是距離、費(fèi)用、時(shí)間等。一般地，增發(fā)一輛車的邊際費(fèi)用較高，故當(dāng) i 為配送中心中國最大的論文知識(shí)平臺(tái) （標(biāo)號時(shí) 0） ，（j=1，… ，n）；當(dāng) i 為任務(wù)點(diǎn)（標(biāo)號 1，… jtcj01??，n）， (i 0，j=0，… ，n)。該問題求解的基本思路是在保證一條線路上各用戶的貨運(yùn)量紙盒不大于車輛的載重量的前提下，連接點(diǎn)對。根據(jù)節(jié)約法的原理和上述的基本思路，可設(shè)計(jì)求解理想狀態(tài)下的車輛調(diào)度的具體步驟如下：1．計(jì)算節(jié)約值 ，令集合 s={ | 0}。轉(zhuǎn)下步，否則轉(zhuǎn)步驟 5；(4)考查點(diǎn) i 和點(diǎn) j 連接后線路上總的貨運(yùn)量 Q，如果 ，轉(zhuǎn)下步，否則q?轉(zhuǎn)步驟 6；(5)連接點(diǎn) i 和點(diǎn) j 到同一條線路上；(6)令 S：=Ss(i ，j),轉(zhuǎn)步驟 3。具體數(shù)據(jù)見表 213 和表 214。首先，計(jì)算節(jié)約值 cijicjijcijis ??????0)(0),(例如，連接用戶 5 和 7 時(shí)，有 s(5,7)= 279152750 ??dc類似可以得到其他。表 214 配送中心與用戶之間的距離中心 0 中心 0用戶 1 40 用戶 1用戶 2 60 65 用戶 2用戶 3 75 40 75 用戶 3用戶 4 90 100 100 100 用戶 4用戶 5 200 50 100 50 100 用戶 5用戶 6 100 75 75 90 75 70 用戶 6用戶 7 160 110 75 90 75 90 70 用戶 7用戶 8 80 100 75 150 100 75 100 100 用戶 8其次，按照從大到小的順序排序，得表 215。表 216 用戶連接過程(i，j) (5