桂林市好又多連鎖超市配送路徑優(yōu)化研究

PAGE12桂林市好又多連鎖超市配送路徑優(yōu)化研究摘要隨著我國物流行業(yè)的迅速發(fā)展，社會對物流服務(wù)的要求也越來越高，各類生產(chǎn)、銷售企業(yè)將物流效率的提高作為企業(yè)競爭戰(zhàn)略的重要組成部分。企業(yè)為集中精力提高核心競爭力，迫切需要第三方的物流服務(wù)，這使得近年來第三方物流在我國得到了快速的發(fā)展。我國的第三方物流企業(yè)大多數(shù)是由運輸或倉儲企業(yè)轉(zhuǎn)變而來，多數(shù)還沿用原有的管理模式，信息化程度較低。在第三方物流企業(yè)的業(yè)務(wù)和管理信息化的過程中，運輸調(diào)度信息化是一個重要方面，運輸調(diào)度的效率直接影響整個物流系統(tǒng)的成本。如何優(yōu)化資源配置、降低管理成本、提高管理效率以及顧客滿意度，是第三方物流企業(yè)面臨的重要問題。基于此，本文就以桂林市好又多連鎖超市為例，對其物流配送車輛調(diào)度問題進行研究。關(guān)鍵詞：第三方物流；車輛調(diào)度；路徑優(yōu)化；節(jié)約算法

目錄摘要 1第一章緒論 41.1研究背景 41.2研究目的和意義 41.3本文研究內(nèi)容與研究方法 5第二章連鎖超市配送相關(guān)理論 62.1物流配送概念 62.2連鎖超市概述 62.3配送路線相關(guān)研究 62.3.1國外研究現(xiàn)狀 62.3.2國內(nèi)研究現(xiàn)狀 8第三章桂林市好又多連鎖超市配送現(xiàn)狀 93.1桂林市好又多連鎖超市簡介 93.2桂林市好又多連鎖超市配送問題 9第四章桂林市好又多連鎖超市配送路線優(yōu)化模型 104.1桂林市好又多連鎖超市車輛路徑問題 104.2車輛路徑問題的主要求解方法 114.2.1節(jié)約思想 114.2.2節(jié)約里程法主要步驟 12第五章基于節(jié)約里程法的桂林市好又多連鎖超市配送車輛路徑優(yōu)化 135.1幾種配送路線優(yōu)化方法的分析與對比 135.2對配送線路的相關(guān)數(shù)據(jù)進行收集整理 135.3利用節(jié)約里程法對配送路徑進行優(yōu)化 145.3.1節(jié)約里程法計算 165.3.2Logware軟件運行 23結(jié)語 29參考文獻 29附錄 31第一章緒論1.1研究背景城市配送線路的選擇直接影響物流配送中運輸費用的重要因素，幾乎可以預(yù)見，對城市配送線路進行合理的優(yōu)化設(shè)計將會大大完善城市配送網(wǎng)絡(luò)，提高城市配送效率，改善城市配送服務(wù)水平。然而，現(xiàn)代物流業(yè)一步一步向著全球化、一體化、信息化的方向發(fā)展，與同期的發(fā)達國家相比，國內(nèi)物流起步較晚，絕大多數(shù)仍是處于發(fā)展初期“只配不送”的中小企業(yè)，導(dǎo)致城市配送成本高且效率低，同時還造成了環(huán)境污染、交通擁堵等城市問題。而發(fā)達國家的物流配送企業(yè)（如UPS）憑借自身完善的線路規(guī)劃方案、雄厚的資金實力、發(fā)達的信息系統(tǒng)和標(biāo)準(zhǔn)化的管理模式漸漸開1.2研究目的和意義本論文以好又多超市在桂林市的城市配送路線優(yōu)化作為主要內(nèi)容從而展開論述，著眼于城市配送過程中的路線優(yōu)化問題。首先介紹城市配送與路線優(yōu)化的相關(guān)理論知識作為指導(dǎo)，明確了線路優(yōu)化的方法;其次通過實地調(diào)研考察收集整理好又多超市在桂林市配送線路運行的基本資料，有針對性地提出其存在的配送路線混亂的問題，考慮了車輛載重和車輛最大行駛距離的約束條件，構(gòu)建配送路線優(yōu)化模型，利用分層聚類分析和節(jié)約里程法重點對好又多超市在桂林市的配送路進行規(guī)劃研究，求解出優(yōu)化后的配送線路方案:最后結(jié)合其他實際情況提出相關(guān)輔助建議共同推進配送優(yōu)化的發(fā)展，為好又多超市桂林市配送線路優(yōu)化提供參考。1.3本文研究內(nèi)容與研究方法為了更好的研究節(jié)約里程法在物流配送路徑優(yōu)化中的應(yīng)用，本文運用的研究方法主要有以下幾種：（1）文獻資料法，即通過圖書館和互聯(lián)網(wǎng)相關(guān)工具，廣泛收集閱讀相關(guān)文獻，總結(jié)研究趨勢和研究成果，為本文研究提供理論支撐。（2）案例分析法：以桂林市好又多連鎖超市承接的G日用品企業(yè)物流配送為研究對象，分析其現(xiàn)狀以及存在的問題。（3）科學(xué)研究方法：采用科學(xué)的研究方法，以實際數(shù)據(jù)為支撐，通過節(jié)約里程法算法思想，對配送路徑進行優(yōu)化，并且對比優(yōu)化結(jié)果，判別優(yōu)化效果。第二章連鎖超市配送相關(guān)理論2.1物流配送概念物流配送，即從商品流通的經(jīng)營方式看的一種商品流通方式。是一種現(xiàn)代的流通方式。物流配送的根據(jù)電子商務(wù)的特點，按照用戶的相關(guān)要求，同意的安排和調(diào)度相關(guān)信息管理，安全及時的將貨物交送給收貨人的一種物流方式。物流配送的許多環(huán)節(jié)都造成巨大的成本、人力、時間浪費，物流企業(yè)必須重視物流配送系統(tǒng)的信息化管理，來降低物流成本。2.2連鎖超市概述連鎖超市根據(jù)字面意思來進行理解的話，就是一個超市幾家共同經(jīng)營，它是使用輸出管理模式的超市品牌效應(yīng)，基于其業(yè)務(wù)流程和零售技術(shù)專業(yè)的改進和勞動的合理分工，它改善了組織的規(guī)模企業(yè)，進一步對于資源共享得到實現(xiàn)，在這種大的背景下，許多商店都進行了操作，這樣就有了一個具有網(wǎng)絡(luò)銷售效應(yīng)的建成。超市之所以要進行連鎖經(jīng)營，其目的就是為了對于銷售“鏈接實現(xiàn)最短線路，成本最低，效率最高”的目標(biāo)，從而使得商品的零售價格有所下降，為企業(yè)在經(jīng)濟市場競爭里面增加實力。由于我國的一個基本國情，國內(nèi)外零售連鎖超市之間的競爭模式，其中最為主要的內(nèi)容就是分配制度的競爭。連鎖超市里面關(guān)于物流配送的效果直接影響連鎖超市的零售經(jīng)營，直接影響企業(yè)的經(jīng)濟規(guī)模利益是不是能夠?qū)崿F(xiàn)，可不可以使供應(yīng)鏈上面的企業(yè)后期創(chuàng)造的利潤情況。2.3配送路線相關(guān)研究2.3.1國外研究現(xiàn)狀國外對問題的研究時間很長，自從在年提出后，立即引起了運籌學(xué)、組合數(shù)學(xué)、圖論及網(wǎng)絡(luò)分析專家的普遍關(guān)注。到二十世紀(jì)年代Clarke和Wright提出了節(jié)約算法求解此類問題。到目前為止，對VRP的算法研究取得了相當(dāng)大的成果，近兩年還在不斷的研究。國外的研究成果主要是采用分枝定界法或最短路徑算法。RobertoBaldacci等人運用精確算法求解有容量限制的帶時間窗的車輛路徑問題。Azit等為求解有容量限制的車輛路徑問題，將所有可行解列出，運用最短路徑法算法進行求解、排序、選擇。Lee等將動態(tài)規(guī)劃的理論運用于車輛路徑問題的研究中，并且也使用最短路徑算法求解。最近，由于信息技術(shù)的發(fā)展與比較成本優(yōu)勢的帶動，產(chǎn)品異地裝箱、包裝、分撥、售賣等增值服務(wù)，目前也逐漸包含進來。物流行業(yè)的過程經(jīng)歷了“港口到港口”、“門口到門口”與“貨架到貨架”等幾個環(huán)節(jié)，其中過程在逐步擴展。Demirdas，E.A.&Uatun，Onden則重視研究第三方物流，第三方物流是指為發(fā)貨人與收貨人提供專業(yè)物流服務(wù)的第三方公司。物流服務(wù)企業(yè)在貨物的實際移動鏈中已經(jīng)不是一個單獨的參與者，而是代表發(fā)貨人員或者收貨人員來執(zhí)行。強調(diào)發(fā)展第三方物流，原區(qū)在于實現(xiàn)物流運營的科學(xué)化，并且使物流企業(yè)與物流需求者之間保持更緊密的聯(lián)系。由于互聯(lián)網(wǎng)的電子商務(wù)快速發(fā)展，電子物流配送迅猛發(fā)展。FilipMoodlift和JomefKoming認(rèn)為歐美國家物流配送發(fā)展較迅猛的主要原因是：第一，運用高科技技術(shù)。歐美國家的配送在運送技術(shù)、存儲保留技術(shù)、裝載搬運技術(shù)、物品安檢技術(shù)、組裝技術(shù)、傳送技術(shù)以及與配送各因素都保持緊密的處理信息技術(shù)等方面，已經(jīng)都建立在領(lǐng)先的配送技術(shù)基礎(chǔ)上，配送中心全部使用電腦管理。PingChen等針對需進行周期性配送的車輛路徑問題，運用迭代鄰域下降算法求解，為此類問題開拓了一種新的解法。Nikolakopoulou等構(gòu)造了一個啟發(fā)式算法求解VRP問題，首先將整個網(wǎng)絡(luò)劃分成若干子網(wǎng)絡(luò)，然后在子網(wǎng)絡(luò)中規(guī)劃車輛的配送路徑。Baker等針對VRP問題構(gòu)造了一個遺傳算法和鄰域搜索算法相結(jié)合的混合遺傳算法來求解，優(yōu)化效果顯著。2.3.2國內(nèi)研究現(xiàn)狀通過對城市配送的路徑進行優(yōu)化，可以在極大限度上減少道路資源的不合理占用，有利于降低配送運輸成本，提高企業(yè)物流效益，所以城市配車輛送路線優(yōu)化早己成為城市配送研究中最基本、最核心的問題之一。它的優(yōu)化研究具有相對較大的實用價值和推廣空間，其部分相關(guān)研究成果已經(jīng)開始應(yīng)用于我國生活的多個領(lǐng)域，比如連鎖超市送貨線路的規(guī)劃、垃圾車日常作業(yè)的線路優(yōu)化、航空線路的優(yōu)化設(shè)計等。由于線路優(yōu)化應(yīng)用的領(lǐng)域各有千秋，研究學(xué)者們的研究方法也不盡相同。朱孟高和米娜率先引入一種可以針對復(fù)雜配送交通網(wǎng)絡(luò)的集束式算法，先將具有相關(guān)聯(lián)配送需求的客戶點進行合并，再通過啟發(fā)式構(gòu)造算法對這些點進行分區(qū)整理，最后采用遺傳算法或禁忌搜索算法計算客戶的派送順序，從而求出配送網(wǎng)絡(luò)模型的近似最優(yōu)解。趙璐、趙磊和朱道立將配送成本達到最低作為目標(biāo)函數(shù)，結(jié)合農(nóng)產(chǎn)品配送特殊的考量要求，建立了有道路限行的配送運輸優(yōu)化模型，進而應(yīng)用遺傳算法進行求解。吉凌燕、蔡慶亮、王輝應(yīng)顧客需求多樣化趨勢，以深入研究節(jié)約算法為核心，組合Dijlcstra算法形成節(jié)約里程表算法，同時在這基礎(chǔ)上完成了對物流路線規(guī)劃模擬系統(tǒng)的開發(fā)研究，滿足顧客的多樣化需求。姜華、楊靜、賈麗芬[28]對連鎖超市配送中心的運行情況進行深入研究，采用節(jié)約里程法對其送貨路線進行合理優(yōu)化研究，解決其存在的各種不合理運輸現(xiàn)象和提升配送質(zhì)量，根據(jù)優(yōu)化前后運行狀況的對比分析，可以看出節(jié)約里程法具有相當(dāng)大的實用性。劉俊娥、李奇對節(jié)約里程法的理論體系進行深入地分析研究，并將其相關(guān)研究結(jié)果應(yīng)用于北京市家樂福的物流配送體系中，通過對比優(yōu)化前后應(yīng)用的相關(guān)數(shù)據(jù)，可以分析得出，節(jié)約里程法得到的線路優(yōu)化方案可以提高企業(yè)經(jīng)濟效益，具有較大的應(yīng)用效果。占義芳[30]通過深入調(diào)查分析，發(fā)現(xiàn)配送線路的選擇直接影響著企業(yè)物流運營的成本，基于此對配送優(yōu)化模型進行了相關(guān)改善，構(gòu)造出基于時間窗的節(jié)約里程線路優(yōu)化模型，并將其應(yīng)用與物流企業(yè)中，滿足企業(yè)的相關(guān)需求。第三章桂林市好又多連鎖超市配送現(xiàn)狀3.1桂林市好又多連鎖超市簡介桂林市好又多連鎖超市有限公司于2001年02月16日在桂林市工商行政管理局登記成立，主要經(jīng)營日用百貨、糧油制品、土特產(chǎn)品、定型包裝食品等，于2001年2月16日在桂林工商局登記注冊掛牌成立，超市注冊資本50（萬元）。3.2桂林市好又多連鎖超市配送問題本文以桂林市好又多連鎖超市承接的桂林市好又多連鎖超市日常配送業(yè)務(wù)為具體案例，分析該公司的配送需求。桂林市好又多連鎖超市是一家日用品零售企業(yè)，對配送時間的要求是城區(qū)在12小時以內(nèi)，城鄉(xiāng)在3天以內(nèi)。為處理桂林市好又多連鎖超市的配送業(yè)務(wù)，桂林市好又多連鎖超市采用了一套先進的物流信息系統(tǒng)對物流活動進行管理，包括運輸管理、倉儲管理、財務(wù)管理、設(shè)備管理、訂單處理以及配送管理。但是，仍然還存在許多問題：（1）信息系統(tǒng)不健全，信息傳遞不暢。雖然已經(jīng)采用了相對比較先進的SAP系統(tǒng)對企業(yè)進行管理，但由于人員素質(zhì)、系統(tǒng)硬件方面的原因，使得信息系統(tǒng)仍然不夠健全，整體的信息化水平比較低。這就使得在信息傳遞方面存在一定的缺陷，導(dǎo)致信息傳遞不暢。所造成的結(jié)果就是，企業(yè)在進行物流配送時，不能夠及時的獲取最新的信息去調(diào)整配送路線、配送車輛以及配送時間。（2）物流配送路線的選擇存在無序性。日用品產(chǎn)品的銷售具有非常明顯的季節(jié)性特點，夏天和冬天是日用品產(chǎn)品銷售的旺季。每當(dāng)進入銷售旺季，蘇寧的物流配送就有點慌不擇路了，完全沒有系統(tǒng)的調(diào)配與管理，處于被動調(diào)配機制。哪家門店的存貨告急，就先送到哪家門店，完全沒有合理的路線選擇與時間安排，出現(xiàn)了物流配送路線選擇與車輛搭配的無序性問題。（3）配送中心選址不科學(xué)使物流配送路線的選擇變得越發(fā)困難。起初，公司在配送中心選址上并沒有綜合的考慮各方面的因素，只是單純的考慮了地價或者是租金方面的價格因素，而忽略了配送中心與各門店之間的關(guān)系，這種盲目不科學(xué)的選址方式，使得在后期的配送過程中，由于路程遠、路況差、配送時間長等因素，造成了高昂的物流配送成本，給企業(yè)帶來了損失。（4）在選擇物流配送路線時沒有考慮到搭配合適的車輛。采用不同的車輛運輸貨物時其載重量是不一樣的，這對于選擇合理的配送路線也是有很大影響的。載重量不夠就不能用最少的出車次數(shù)送到全部的貨物，就不能選擇合理的配送路線，增加了物流成本，同時也影響了配送效率。第四章桂林市好又多連鎖超市配送路線優(yōu)化模型4.1桂林市好又多連鎖超市車輛路徑問題傳統(tǒng)意義上的物流配送最短路徑，指的是貨物由配送中心向顧客移動的過程中，行駛的路徑最短，因此，商家選定一條最短路徑行駛，可以提高物品的時間價值，使成本降到最低，把配送的效率提到最高。車輛路徑問題的簡單描述：在一個有供需關(guān)系的環(huán)境下，配貨中心、若干車輛、一定量的顧客，符合給定的約束情況，然后安排車輛合理出行，給顧客送貨或從顧客那里取貨，最后達到目標(biāo)量的最優(yōu)。VRP是典型NP難題，其被一定量條件限制，含若干個變量和多個目標(biāo)，在這些要求下求出最短路徑的問題，限制條件主要有發(fā)送量、車輛行駛里程限制、交貨時間、車輛容量限制等。選擇合理的配送路線，對是否能降低配送成本、加快配送速度、提高物流服務(wù)質(zhì)量和提升物流配送的總體經(jīng)濟效益等等有直接的影響。到目前為止存在很多分類方法來區(qū)分配送路徑優(yōu)化問題，標(biāo)準(zhǔn)不同分類結(jié)果就相差很大。下面為幾種主要分類方法：（1）按照配送中心多少分類：多配送中心、單配送中心。（2）車輛是否滿載情況：滿載、非滿載、滿載和非滿載并存。（3）配送任務(wù)特征：單送貨、單取貨、送貨取貨并存。（4）顧客有無對貨物送去時間有要求：對時間無限制、對時間有限制。（5）車輛的類型：多種車型、一種單車型。（6）優(yōu)化的目標(biāo)數(shù)量：多個目標(biāo)、單一目標(biāo)。（7）運輸網(wǎng)絡(luò)的特點：隨時間變化的動態(tài)網(wǎng)絡(luò)、不隨時間變化的靜態(tài)網(wǎng)絡(luò)。4.2車輛路徑問題的主要求解方法目前，學(xué)者們主要應(yīng)用了精確算法和啟發(fā)式算法對車輛配送路徑優(yōu)化問題進行研究，精確解法：這種算法主要包括割平面算法、動態(tài)規(guī)劃、網(wǎng)絡(luò)流算法、等等，這些算法通常一般都只有在路段數(shù)和客戶節(jié)點數(shù)相對來說比較少的情況下才可以求得精確解，但是在現(xiàn)在生活中往往路段數(shù)和客戶點都是比較多的，車輛的配送方案會成指數(shù)增加，所以這些精確算法的求解就會相當(dāng)?shù)睦щy，這也就是精確算法的局限性。因此，后來學(xué)者們在解決VRP問題的時候就把目光轉(zhuǎn)向了啟發(fā)式算法，這是研究這種問題的另一類研究的算法，啟發(fā)式算法主要的優(yōu)點就是它可以通過求得問題的近似解，把計算的精度問題進行解決。蟻群算法、模擬退火算法、遺傳算法、禁忌搜索算法及其相互有效組合而成的混合算法都是學(xué)者們在后期研究中經(jīng)常用到的方法。本文配送路徑的優(yōu)化的方法是節(jié)約里程法。4.2.1節(jié)約思想節(jié)約里程法又稱C-W算法，是由Clarke和Writ于1964年首次提出的。它是用來解決運輸車輛數(shù)目不確定的VRP問題的最經(jīng)典的啟發(fā)式算法。采用這種方法不僅可以縮短配送距離，而且還可以提高車輛滿載率，降低運輸成本。其基本思想：設(shè)一家配送中心（P）向其兩個配送點A、B送貨，已知兩配送點到配送中心的距離分別是PA和PB，A、B兩配送點間的距離為AB，假設(shè)配送中心分別對這兩個配送點送貨，并且假設(shè)往程行駛和返程行駛距離相等，則其配送總路程為：P1=2（PA+PB），其配送線路如圖1（a）所示。（a）（b）圖1節(jié)約里程法圖解基于節(jié)約思想，拋棄分別對配送點的直接配送模式，而采用一輛車在滿足其它約束條件下連續(xù)對A、B兩個配送點進行送貨，其配送模式如圖1（b）所示。這樣就可以只使用一個車次，其行走的總距離為：P2=PA+AB+PB。由三角形的兩邊之和大于第三邊的性質(zhì)可知：AB<PA+PB。所以在滿足一定的約束條件下，第二種配送方案明顯優(yōu)于第一種，且節(jié)約里程量為：ΔP=P1-P2=（PA+PB）-AB。并且同一條配送路網(wǎng)中配送點越多，里程節(jié)約量就越大。4.2.2節(jié)約里程法主要步驟（1）通過調(diào)查分析做出配送里程表，分別列出配送中心到各個配送點以及各個配送點之間的實際距離。（2）根據(jù)節(jié)約里程法的基本原理，按照節(jié)約里程公式求出各個配送點的節(jié)約里程數(shù)，制成節(jié)約里程表。（3）將節(jié)約里程表里的節(jié)約里程數(shù)進行降序排列，獲得節(jié)約里程排序表。（4）確定約束條件，通常約束條件為車輛載重限制和車輛最大行駛里程限制。（5）根據(jù)節(jié)約里程排序表和約束條件進行配送線路優(yōu)化。（6）繪出最終優(yōu)化路線圖。第五章基于節(jié)約里程法的桂林市好又多連鎖超市配送車輛路徑優(yōu)化5.1幾種配送路線優(yōu)化方法的分析與對比隨著社會的發(fā)展，人們對于物流管理的重視，對于物流配送路線優(yōu)化方法的研究也越來越深入，在這樣的大環(huán)境之下就出現(xiàn)了多種物流配送路線優(yōu)化方法，如禁忌搜索算法、模擬退火算法、遺傳算法、節(jié)約里程法等。本文將上述四種方法進行綜合比較，見表3.1。表3.1配送路線優(yōu)化方法比較優(yōu)點缺點效率難易程度禁忌搜索算法突破局部最優(yōu)，不會失去全局最優(yōu)性對初始解的依賴性強優(yōu)化效率不高較難模擬退火算法易實現(xiàn)全局最優(yōu)的串行結(jié)構(gòu)的優(yōu)化算法對于大規(guī)模的問題用時較長優(yōu)化效率不高較難遺傳算法利于全局擇優(yōu)，易于實現(xiàn)并行化參數(shù)選擇比較困難，只能針對具體問題進行具體分析優(yōu)化效率不高較難節(jié)約里程法簡便、易行，縮短運輸路程，體現(xiàn)了物流配送網(wǎng)絡(luò)的優(yōu)勢對客戶的需求變化反應(yīng)速度較慢優(yōu)化效率較高高簡易由表3.1可以看出，相對于其他三種算法，節(jié)約里程法比較簡便易行，對初始數(shù)據(jù)的要求不高，且優(yōu)化效率比較高。當(dāng)銷售旺季到來時，對于配送效率要求比較高，如果采用其它三種方法，其效率是跟不上的，而且操作也比較困難。而節(jié)約里程算法的優(yōu)化效率比較高，而且操作比較簡易。因此，對于路線優(yōu)化，本文采用節(jié)約里程法。5.2對配送線路的相關(guān)數(shù)據(jù)進行收集整理由于超市門店較多，收集起來較為困難，因此選取了幾家超市作為代表，對其進行數(shù)據(jù)收集和分析。為了便于敘述，以下各門店和售后服務(wù)站就以A～J的字母表示，配送中心則以P表示。配送中心P到各門店的具體路程，為了便于敘述，以下各門店和售后服務(wù)站就以A～J的字母表示，配送中心則以P表示。配送中心P到各門店的具體路程，以及各門店間的具體路程如圖3所示。圖3.1配送網(wǎng)絡(luò)圖各門店每天的平均配送量見表3.2。表3.2門店平均每天配送量單位：t門店ABCDEFGHIJ配送量0.6目前，已知桂林市好又多連鎖超市在給各門店配送貨物時，使用最大裝載量為2t和4t的兩種廂式貨車，根據(jù)車輛實際情況一次運行的距離應(yīng)控制在45km以內(nèi)。其中2t車運行單價為2.4元/km，4t車運行單價為2.7元/km。5.3利用節(jié)約里程法對配送路徑進行優(yōu)化桂林市好又多連鎖超市有一物配送中心p，A-S表示p附近需要配送的各零售商，早上8點開始配送，要求與當(dāng)天下午2點之前必須配送完畢，每輛車每天平均工作時間不超過6.5小時，在每個送貨點停留的時間為10分鐘，途中速度為25km/h，假設(shè)工廠只擁有20噸車，每次出發(fā)最多能帶20噸的重量而且每次不超過6小時。并且限制車輛一次運輸?shù)淖钸h距離為40公里，配送中心位于坐標(biāo)原點，每個送貨點的位置和貨物重量如下表所示，并且假設(shè)街道的長度是兩點間直線距離的1.21倍。請問怎樣安排運輸路線，使配送中心需要的最少員工數(shù)和車輛數(shù)，運輸距離最小？表3.1配送中心配送位置需求量圖x坐標(biāo)y坐標(biāo)需求量（t）x坐標(biāo)y坐標(biāo)需求量（t）p0.000.00J-1.005.006A-5.00-1.006K1.007.005B-4.001.005L1.003.004C-2.000.008M2.006.008D-6.009.005N3.0012.006E-5.007.007O4.001.004F-3.004.008P5.005.005G-3.005.003Q7.001.003H-1.003.009R9.002.006I6.0010.005S10.007.008圖3.1站點位置坐標(biāo)圖其特點包括：（1）只送貨不進行取貨，只是單純的送貨問題。（2）車輛類型單一，都可以看成速度為25km/h，載重量為20噸車輛。（3）節(jié)點數(shù)量多，配送的節(jié)點數(shù)量多達19個，應(yīng)當(dāng)采取共同配送以減少送貨時間及送貨成本。（4）每次出發(fā)最多能帶20噸的重量，并且從表3.1可以查看各個節(jié)點的信息，路線行駛時間不得超過6個小時。（5）配送中心和配送點的相對位置已經(jīng)給出，各個節(jié)點的橫坐標(biāo)和縱坐標(biāo)都在表3.1中給出了，并且給出了迂回因子，值為1.21。（6）在路徑上運行的最長的時間被指定，最長不能超過6個小時。（7）車輛最早離開站點的時間和它返回最晚的時間被指定，即早上8點開始配送，要求與當(dāng)天16點之前必須返回。（8）VRP的要求：每輛車只能服務(wù)一條路線，配送車輛都始發(fā)和終止于配送中心。（9）沒有堵車等問題存在。5.3.1節(jié)約里程法計算利用節(jié)約里程法計算桂林市好又多連鎖超市的案例。計算步驟如下：第一步，計算配送中心到配送點間的最短距離，畫出距離表。由于知道各個配送點間的坐標(biāo)，利用勾股定理即可算出配送中心到配送點間的最短距離。最后畫出p到各個配送點之間的距離表（保留兩位小數(shù)）矩陣。矩陣如表3.2所示。第二步，根據(jù)最短距離表，利用節(jié)約法計算出用戶間的節(jié)約里程，并由大到小排列，編制節(jié)約里程順序表，如表3.3所示。ΔL=（La+Lb）－Lab例如△L1=(LpA+LpB)－LAB=(5.10+4.12)－2.24=6.98第三步，根據(jù)節(jié)約里程順序表和配送中心的約束條件，繪制配送路線。具體步驟如下：（1）初始解線路總數(shù)：19條；總運輸距離：259.29（km）；車輛臺數(shù)：19輛。如圖3.2所示。表3.2配送中心到各配送點間的最短距離表（單位：km）pABCDEFGHIJKLMNOPQRSp0.005.104.122.0010.829.175.004.903.1611.665.107.073.166.3212.374.127.077.079.2212.21A5.100.002.243.1610.068.005.396.325.6615.567.2110.007.219.9015.269.2211.6612.1714.3217.00B4.122.240.002.248.256.083.164.123.6113.455.007.815.397.8113.048.009.8511.0013.0415.23C2.003.162.240.009.853.004.125.103.1612.815.107.624.247.2113.006.088.609.0611.1813.89D10.8210.058.259.850.002.245.005.007.8112.046.407.289.228.549.4912.8111.7115.2616.5516.13E9.178.006.083.002.240.003.612.835.6611.404.476.007.217.079.4310.8210.2013.4214.8715.00F5.005.393.164.125.003.610.001.002.2410.822.245.004.125.3910.007.628.0610.4412.1713.34G4.906.324.125.105.002.831.000.002.8310.302.004.474.475.109.228.068.0010.7712.3713.15H3.165.663.613.167.815.662.242.830.009.902.004.472.004.249.855.396.328.2510.0511.71I11.6615.5613.4512.8112.0411.4010.8210.309.900.008.605.838.605.663.619.225.019.068.545.00J5.107.215.005.106.404.472.242.002.008.600.002.832.833.168.066.406.008.9410.4411.18K7.0710.007.817.627.286.005.004.474.475.832.830.004.001.415.396.714.478.499.439.00L3.167.215.394.249.227.214.124.472.008.602.834.000.003.169.223.614.476.328.069.85M6.329.907.817.218.547.075.395.104.245.663.161.413.160.006.085.393.167.078.068.06N12.3715.2613.0413.009.499.4310.009.229.853.618.065.399.226.080.0011.057.2811.7111.668.60O4.129.228.006.0812.8110.827.628.065.399.226.406.713.615.3911.050.004.123.005.108.49P7.0711.669.858.6011.7010.208.068.006.325.106.004.474.473.167.284.120.004.475.005.39Q7.0712.1711.009.0615.2613.4210.4410.778.259.068.948.496.327.0711.703.004.470.002.246.71R9.2214.3213.0411.1816.5514.8712.1712.3710.058.5410.449.438.068.0611.665.105.002.240.005.10S12.2117.0015.2313.8916.1215.0013.3413.1511.705.0011.189.009.858.068.608.495.396.715.100.00表3.3節(jié)約里程表（單位：km）p-I-N20.43p-E-I9.43p-A-E6.26p-F-P4.01p-C-H2p-I-S18.87p-J-N9.41p-K-L6.23p-G-P3.97p-C-J2p-D-E17.75p-J-K9.34p-I-L6.22p-G-S3.95p-H-Q1.99p-R-S16.33p-F-G8.9p-D-P6.18p-A-C3.94p-B-L1.9p-N-S15.97p-D-M8.6p-D-H6.17p-H-P3.91p-H-O1.9p-K-N14.06p-E-M8.42p-J-P6.17p-L-Q3.91p-C-G1.8p-Q-R14.05p-J-M8.26p-J-S6.13p-B-C3.89p-G-R1.75p-P-S13.89p-O-R8.24p-G-M6.12p-J-R3.88p-F-Q1.63p-D-N13.7p-O-Q8.19p-E-P6.04p-F-S3.86p-A-M1.52p-I-P13.63p-C-E8.17p-B-F5.96p-B-H3.68p-F-O1.51p-I-K12.9p-I-J8.16p-F-M5.94p-L-O3.68p-C-K1.46p-M-N12.61p-G-N8.05p-F-H5.93p-A-G3.67p-C-N1.37p-Q-S12.57p-G-J8p-A-D5.87p-H-S3.66p-B-P1.35p-I-R12.34p-F-J7.86p-F-I5.85p-G-L3.59p-G-Q1.2p-I-M12.33p-O-S7.84p-H-K5.76p-E-R3.52p-A-I1.2p-N-P12.16p-N-Q7.74p-L-P5.76p-D-R3.48p-C-M1.11p-E-N12.1p-G-K7.5p-H-N5.68p-B-N3.45p-B-S1.1p-K-M11.98p-M-R7.48p-K-Q5.66p-B-K3.38p-A-L1.05p-P-R11.29p-F-N7.37p-L-S5.52p-J-Q3.23p-G-O0.96p-E-G11.24p-B-E7.21p-N-O5.45p-A-J2.99p-C-L0.92p-D-F10.82p-F-K7.07p-J-L5.43p-C-D2.97p-C-I0.86p-D-G10.72p-O-P7.07p-H-M5.24p-C-F2.88p-A-P0.51p-D-K10.61p-A-B6.99p-G-H5.23p-E-Q2.82p-C-P0.47p-E-F10.56p-D-S6.9p-E-L5.12p-J-O2.82p-C-S0.31p-M-S10.47p-K-R6.86p-M-O5.06p-B-M2.64p-A-S0.31p-D-I10.44p-B-D6.69p-H-I4.92p-D-Q2.62p-B-R0.3p-K-S10.28p-E-H6.67p-B-G4.9p-A-H2.6p-B-O0.25p-E-K10.24p-I-O6.57p-D-L4.76p-E-O2.47p-B-Q0.19p-M-P10.23p-E-S6.37p-A-F4.71p-B-I2.33p-C-O0.04p-N-R9.93p-L-M6.32p-K-O4.49p-H-R2.33p-C-R0.04p-E-J9.79p-M-Q6.32p-H-L4.32p-A-N2.2p-C-Q0.02p-I-Q9.68p-L-N6.31p-L-R4.32p-A-K2.17p-A-O0p-K-P9.67p-G-I6.27p-B-J4.22p-D-O2.13p-A-Q0p-P-Q9.67p-H-J6.26p-F-L4.04p-F-R2.05p-A-R0p-D-J9.51圖3.2初始解線路（2）二次解首先選擇最節(jié)約里程的路段（p-I-N），然后是（p-I-S），每條循環(huán)路線上的客戶需求量之和要小于20噸，因為在余下選擇中沒有滿足條件的客戶，此時載重總量為19t，所以，第二回合的配送路線為（p-S-I-N）。線路總數(shù)：17條；總運輸距離：220.00（km）；車輛臺數(shù)：17輛。如圖3.3所示。圖3.3二次解線路（3）三次解先選擇最節(jié)約里程的路段（p-D-E），其他步驟同（2），可得第三回合的配送路線為（p-G-E-D-K），此時載重總量為20t。線路總數(shù)：14條；總運輸距離：180.41（km）；車輛臺數(shù)：14輛。如圖3.4所示。圖3.4三次解線路（4）四次解先選擇最節(jié)約里程的路段（p-Q-R），其他步驟同（2），可得第四回合的配送路線為（p-O-Q-R-P），此時載重總量為18t。線路總數(shù)：11條；總運輸距離：146.87（km）；車輛臺數(shù)：11輛。如圖3.5所示。圖3.5四次解線路（5）五次解先選擇最節(jié)約里程的路段（p-J-M），其他步驟同（2），可得第四回合的配送路線為（p-J-M-L），此時載重總量為18t。線路總數(shù)：9條；總運輸距離：132.28（km）；車輛臺數(shù)：9輛。如圖3.6所示。圖3.6五次解線路（6）六次解先選擇最節(jié)約里程的路段（p-A-B），其他步驟同（2），可得第四回合的配送路線為（p-A-B-F），此時載重總量為19t。線路總數(shù)：7條；總運輸距離：119.33（km）；車輛臺數(shù)：7輛。如圖3.7所示。圖3.7六次解線路（7）最終解最后只剩余（p-C）和（p-H）兩條線路，按照載重量，兩條線路可以進行組合，此時載重總量為17t。線路總數(shù)：6條；總運輸距離：117.33（km）；車輛臺數(shù)：6輛。如圖3.8所示。圖3.8最終解線路路徑一：p-A-B-F-p，運行距離15.50km，20t車一輛，載重19t；路徑二：p-C-H-p，運行距離8.32km，20t車一輛，載重17t；路徑三：p-G-E-D-K-p，運行距離24.31km，20t車一輛，載重20t；路徑四：p-J-M-L-p，運行距離14.59km，20t車一輛，載重18t；路徑五：p-N-I-S-p，運行距離33.18km，20t車一輛，載重19t；路徑六：p-P-R-Q-O-p，運行距離21.43km，20t車一輛，載重18t?？偣沧咝欣锍?17.33km，共節(jié)約里程259.29-117.33=141.96km。5.3.2Logware軟件運行利用Logware軟件ROUTE模塊計算，根據(jù)所給出的信息，下面運用Logware軟件解決問題：在parameters（限定因素）這個對話框中有depotdata（站點數(shù)據(jù)）、generaldata（總體數(shù)據(jù)）、load/unloadtimeformula(裝貨/卸貨時間因素)三大部分組成。（1）在站點數(shù)據(jù)中，需要填寫的數(shù)據(jù)有默認(rèn)車輛速度，其速度為：25km/h。（2）在總體數(shù)據(jù)中，需要填寫的數(shù)據(jù)有：路徑上允許的最長行駛時間為：6h；迂回因子為：1.3。將各個數(shù)值填入到相應(yīng)的地方，如圖3.8所示圖3.8限定因素步驟圖在stops（節(jié)點）這個對話框中，有關(guān)于節(jié)點數(shù)據(jù)的信息，其中包括：1、節(jié)點的描述，即節(jié)點的名稱；2、節(jié)點的類型，即取貨點還是送貨點，實例中都是送貨點；3、節(jié)點的載貨重量，可看表3.1；4、節(jié)點的載貨體積，一律都是按重量計算，不用體積；5、節(jié)點的橫坐標(biāo)和縱坐標(biāo)，可看表3.1；6、節(jié)點的停留時間，停留時間為十分鐘；7、節(jié)點的開始和結(jié)束時間，即早上八點開始，十六點結(jié)束。查看表3.1，將實例中的信息填入到相應(yīng)的地方，如圖3.9。在vehicles（車輛）這個對話框中，有關(guān)于車輛數(shù)據(jù)的信息，其中包括：1、車輛的類型，該題目中是單一的車輛，所以車輛類型數(shù)為1；2、車輛的數(shù)量，因為該題目中每天的貨物重量為111噸，每輛車最多能裝20噸，所以可以取6（111/20=6）輛車。3、車輛的載重量，因為每輛車最多能裝20噸，所以可以看成載重量為20噸；圖3.9節(jié)點數(shù)據(jù)步驟圖圖3.10車輛數(shù)據(jù)步驟圖4、節(jié)點的載貨體積，一律都是按重量計算，不用體積；車輛數(shù)據(jù)步驟圖，如圖3.10所示。圖3.11檢驗匯總數(shù)據(jù)步驟圖在datacheck（數(shù)據(jù)檢驗）這個對話框中，將所填寫的數(shù)據(jù)進行匯總檢驗，其檢驗匯總的結(jié)果如圖3.11。數(shù)據(jù)填寫完成后，點擊Solve按鈕，就可以得到解決的路線圖，路徑設(shè)計的結(jié)果在圖3.12中。由于軟件中配送點不能用A，B，C…，所以相應(yīng)的配送點用1,2,3…代替。根據(jù)報告可以得出，配送路徑為：路徑一：p-A-B-F-p，運行距離15.50km，20t車一輛，載重19t，車輛從早上07:46從配送中心出發(fā)，在三個配送點耽誤30分鐘（3×10分鐘）最終上午09:01到達配送中心。路徑二：p-C-H-p，運行距離8.32km，20t車一輛，載重17t，車輛從早上07:55從配送中心出發(fā)，在兩個配送點耽誤20分鐘（2×10分鐘）最終上午08:39到達配送中心。路徑三：p-G-D-E-L-p，運行距離22.51km，20t車一輛，載重19t，車輛從早上07:25從配送中心出發(fā)，在四個配送點耽誤30分鐘（3×10分鐘）最終上午09:31到達配送中心。路徑四：p-J-K-M-p，運行距離15.76km，20t車一輛，載重17t，車輛從早上07:46從配送中心出發(fā)，在三個配送點耽誤30分鐘（3×10分鐘）最終上午09:01到達配送中心。圖3.12結(jié)果報告圖路徑五：p-N-I-S-p，運行距離33.18km，20t車一輛，載重19t，車輛從早上07:48從配送中心出發(fā)，在三個配送點耽誤30分鐘（3×10分鐘）最終上午09:31到達配送中心。路徑六：p-P-R-Q-O-p，運行距離21.43km，20t車一輛，載重18t，車輛從早上07:50從配送中心出發(fā)，在四配送點耽誤40分鐘（4×10分鐘）最終上午09:39到達配送中心。總共走行里程=15.50+8.32+22.51+15.76+33.18+21.43=116.7km，共節(jié)約里程259.29-116.7=142.59km。利用節(jié)約里程法算出的結(jié)果和用軟件得出的結(jié)果不是完全相同，但是總共走行里程數(shù)與共節(jié)約里程基本相同，兩個結(jié)果的差值僅為（117.33-116.7=0.63km）。由于兩種方法各有優(yōu)缺點，所得結(jié)果不盡相同，節(jié)約里程法沒有考慮配送時間，還有配送中所花費的費用問題；Logware軟件考慮了相關(guān)的時間和費用問題。解決方案運行完成后，在按下Report就可以得到一份報告。這份報告提供了關(guān)于所有路徑和在各個路徑上詳細花費，和所耗時間的概要信息。結(jié)語現(xiàn)代物流的快速發(fā)展促進了物流運輸與配送的建設(shè)。而配送環(huán)節(jié)的建設(shè)在現(xiàn)代企業(yè)發(fā)展中的作用是十分明顯的，它不但可以降低物流時間及成本，而且憑借其強大的服務(wù)功能，可以為客戶提供差異化服務(wù)，提高企業(yè)的市場競爭力。在對這篇論文的選題到最終的完成過程中，深深地意識到在我國物流企業(yè)建立物流運輸與配送的合理化還有很長的路要走，部分物流企業(yè)要建立完備的配送工作環(huán)節(jié)，還需要進一步可行性研究的論證，規(guī)劃設(shè)計，然后具體實施。參考文獻[1] AlanMcKinnon.LowCarbonLogistics./doc/HWLowCarbonLogisticsSeminar.pdf.2014.45-46[2] Cachon,G.CarbonFootprintandtheManagementofSupplyChains.TheINFORMSAnnualMeeting,SanDiego,[A]2013.78-79.[3] HuangHua.AStudyofDevelopingChineseLowGarbonLogisticsintheNewRailwayPeriod.E-ProductE-ServiceandE-Entertainment（ICEEE）.InternationalConference[C].Henan.2016.22-23[4] HongGyunPark,YongJooLee.TheEfficiencyandProductivityAnalysisofLargeLogisticsProvider