《基于雙層規(guī)劃模型的生鮮物流配送中心選址和配送路線優(yōu)化實證探究》17000字（論文）

基于雙層規(guī)劃模型的生鮮物流配送中心選址和配送路線優(yōu)化實證研究摘要近年來，生鮮產(chǎn)品在電子商務(wù)平臺上的訂單規(guī)模不斷增大，體現(xiàn)出生鮮電商市場發(fā)展的巨大潛力。生鮮產(chǎn)品物流的及時配送成為制約生鮮電商企業(yè)發(fā)展的重要因素，而影響配送的關(guān)鍵點在于配送中心的選址和配送路線的優(yōu)化等方面。本文主要研究生鮮物流配送中心選址和配送路線優(yōu)化問題，基于系統(tǒng)的思想，建立了選址-路線雙層規(guī)劃模型，并通過設(shè)計上下層模型的啟發(fā)式算法，對生鮮電商物流配送系統(tǒng)進行優(yōu)化。首先，文章介紹了本文的研究背景、研究意義和國內(nèi)外研究現(xiàn)狀。隨后，本文介紹了選址問題和路徑優(yōu)化問題的常見模型，并分別介紹了模型對應(yīng)的求解算法。接著，本文針對選址-路徑問題建立了雙層規(guī)劃模型，上層選址模型是改進后的P-中值模型，在目標函數(shù)中加入了配送中心的固定成本和腐敗成本，使得模型更加準確合理；下層路徑優(yōu)化模型中考慮了生鮮產(chǎn)品配送時的固定成本、運輸成本、貨損成本和時間窗懲罰成本，并對TSP問題模型進行了改進。本文又針對雙層規(guī)劃模型設(shè)計了求解算法，在上層模型中利用貪婪取走啟發(fā)式算法進行求解，在下層模型中利用最近插入法對配送路徑進行優(yōu)化。最后，本文將所建模型和求解算法應(yīng)用于實際案例中，對案例中的生鮮電商企業(yè)進行配送中心的選址和配送路線的優(yōu)化。關(guān)鍵詞：雙層規(guī)劃模型；選址-路徑；貪婪取走啟發(fā)式算法；最近插入法目錄TOC\o"1-3"\h\u7941第1章緒論 1105741.1研究背景 1139871.2研究意義 2229801.3國內(nèi)外研究現(xiàn)狀 3245631.3.1國外研究現(xiàn)狀 3194251.3.2國內(nèi)研究現(xiàn)狀 325878第2章生鮮物流中心選址與配送路徑優(yōu)化問題研究 5146362.1生鮮物流中心選址問題研究 5311612.1.1選址問題概述 5281212.1.2常見求解模型介紹 7275362.2生鮮物流配送路徑優(yōu)化研究 10127572.2.1路徑優(yōu)化問題概述 10306492.2.2常見求解模型介紹 1259182.3生鮮物流配送中心選址及路徑優(yōu)化問題研究 13297412.3.1選址-路徑問題概述 13163772.3.2選址-路徑基本模型 1313725第3章生鮮物流配送中心選址及路徑優(yōu)化模型分析 159663.1雙層規(guī)劃模型介紹 1575463.2模型的構(gòu)建思路 15203533.3上層模型的構(gòu)建 16227743.3.1模型假設(shè) 16182203.3.2符號介紹 17248883.3.3成本分析 1760773.3.4生鮮物流配送中心選址模型 1836193.4下層模型的構(gòu)建 1995383.4.1模型假設(shè) 19226213.4.2符號介紹 19244073.4.3成本分析 2031893.4.4配送路線優(yōu)化模型 225672第4章模型求解算法研究 23924.1雙層規(guī)劃模型的求解流程 23154984.2上層模型的求解算法 2496174.3下層模型的求解算法 2410237第5章案例分析 26260225.1案例背景 2696155.2上層規(guī)劃——配送中心選址 26256215.3下層規(guī)劃——配送路徑優(yōu)化 3013045結(jié)論 3225944參考文獻 34第1章緒論1.1研究背景隨著信息技術(shù)的不斷發(fā)展，新興電子商務(wù)已向各個行業(yè)滲透，生鮮電商成為當前社會關(guān)注的熱點之一。自從2016年10月，阿里巴巴集團創(chuàng)始人馬云在杭州演講時第一次提出了新零售商業(yè)模式，即企業(yè)借助互聯(lián)網(wǎng)，通過運用大數(shù)據(jù)、AI、云計算和人工智能等現(xiàn)代化先進科學(xué)信息技術(shù)，對商品從生產(chǎn)到流通、從運營到銷售的整個過程進行升級改造，進一步重塑業(yè)態(tài)結(jié)構(gòu)和生態(tài)圈，并對線上服務(wù)、線下體驗和現(xiàn)代物流進行深度融合的零售新模式[1]。馬云也進一步表示今后的十年、二十年將是新零售的天下，不再僅僅是純電商。2016-2020年中國生鮮電商行業(yè)市場規(guī)模發(fā)展趨勢如下圖1-1：圖1-12016-2020年中國生鮮電商行業(yè)市場規(guī)模示意圖自馬云提出新零售之后，2017年中國生鮮電商行業(yè)的市場規(guī)模比2016年增長45.1%，直到2020年，中國生鮮電商行業(yè)市場規(guī)模高達2034.8億元。據(jù)前瞻產(chǎn)業(yè)研究院發(fā)布的《中國生鮮行業(yè)研究報告》顯示，2020年，我國人均蔬菜占有量將達400公斤，速凍食品的產(chǎn)量也以20%的速度不斷增加，由此可見，中國未來的生鮮行業(yè)市場規(guī)模巨大，生鮮電商市場也將繼續(xù)擴大。多多買菜是拼多多在2020年8月上線的一種線上買菜交易平臺，它采取的是“線上下單+線下自提”的半預(yù)購模式，消費者每天23點前下單，次日便可到最近的自提點取回商品。多多買菜的線下自提模式是通過與農(nóng)村個體超市或者城市社區(qū)超市合作，每天將前一日客戶在線上訂購的產(chǎn)品送至這些合作的提貨點，然后通知用戶在下單的次日去最近的自提點取貨。這種客戶自提的方式，將物流配送的“最后一公里”環(huán)節(jié)省略，消費者可以根據(jù)自己的時間自由地去提貨點取貨，用戶的滿意度也會隨之提高。在各提貨點的上級，多多買菜在每個地區(qū)都會設(shè)置一定數(shù)量的物流配送中心，用來對商品進行流通加工、包裝和分揀，并且每天都會由配送員將線上訂單的商品派送到多個不同的提貨點。拼多多的物流中心是由第三方物流企業(yè)所提供的，所以從物流角度來說，降低其生鮮產(chǎn)品流通成本主要在于兩個方面，一方面是通過優(yōu)化物流配送中心的選址問題，加快配送中心生鮮產(chǎn)品的周轉(zhuǎn)，減少資金的占用；另一方面是對配送路徑進行優(yōu)化，提高生鮮產(chǎn)品的配送效率，降低生鮮產(chǎn)品的貨損率，降低配送成本。目前，我國針對單一的配送中心選址問題和路徑優(yōu)化的研究已經(jīng)相對成熟，但對生鮮產(chǎn)品的配送中心選址及配送路徑聯(lián)合優(yōu)化問題的研究較少，尤其是這種省略“最后一公里”配送的城鄉(xiāng)提貨點的終端配送路徑的研究仍需進一步探索。所以文章基于以上背景，以多多買菜生鮮物流中心選址和配送路徑優(yōu)化為研究內(nèi)容，設(shè)計物流中心選址和配送路徑雙層規(guī)劃目標，通過設(shè)計求解算法，實現(xiàn)生鮮物流系統(tǒng)成本的降低。1.2研究意義物流設(shè)施選址和路徑規(guī)劃問題是物流網(wǎng)絡(luò)優(yōu)化的兩個關(guān)鍵節(jié)點。選址問題是對設(shè)施位置和數(shù)量進行科學(xué)的決策，路徑問題是對配送路線進行優(yōu)化，以提高物流配送的效率。所以，通過對物流網(wǎng)絡(luò)優(yōu)化所涉及的選址和路徑優(yōu)化問題進行集成優(yōu)化，可以有效地避免單獨優(yōu)化所導(dǎo)致的局部最優(yōu)。（1）理論意義目前關(guān)于生鮮產(chǎn)品物流的研究主要集中在供應(yīng)鏈、產(chǎn)品溯源和配送模式研究等問題上，關(guān)于生鮮物流配送中心選址及路徑協(xié)同優(yōu)化問題的研究并不多。本文通過研究選址-路徑模型，以物流系統(tǒng)成本最低為目標，建立選址-路徑雙層目標規(guī)劃模型，對生鮮物流網(wǎng)絡(luò)結(jié)構(gòu)進行優(yōu)化，以實現(xiàn)提高物流運作效率，降低物流配送成本的目的。（2）現(xiàn)實意義本文深入分析了配送中心選址及路徑優(yōu)化問題，構(gòu)建了生鮮產(chǎn)品配送中心選址與路徑優(yōu)化問題的雙層規(guī)劃模型。企業(yè)可以依據(jù)自身情況合理制定配送路徑的方案和適應(yīng)本企業(yè)的配送中心最佳選址方案，為生鮮電商企業(yè)優(yōu)化物流系統(tǒng)提供了新思路和新方法，降低了企業(yè)的物流配送成本，從而提高了企業(yè)的經(jīng)營收益。1.3國內(nèi)外研究現(xiàn)狀1.3.1國外研究現(xiàn)狀物流配送中心選址問題較早是在國外開展研究的，1909年由Weber提出韋伯問題，主要研究單一倉庫與各需求點之間的路徑最短問題[2]。后來，隨著社會的發(fā)展，眾多學(xué)者開始加入自身的考慮因素，不再局限于單一目標，Owensh等在配送中心選址模型中加入了配送途中動態(tài)性以及變動性需求信息[3]。Syam等建立了物流鏈網(wǎng)絡(luò)問題的0-1混合整數(shù)線性規(guī)劃模型，問題的目標函數(shù)是以最低成本選擇開放的設(shè)施（工廠和配送中心）來滿足配送需求，通過運用模擬退火算法對冷鏈物流多設(shè)施選址模型進行求解[4]。車輛路徑規(guī)劃問題是在1959年由著名學(xué)者Dantzig和Rasmer首次提出的。國外學(xué)者對車輛路徑問題較多研究的是現(xiàn)代啟發(fā)式算法，包括遺傳算法、禁忌搜索算法、蟻群算法和人工神經(jīng)網(wǎng)絡(luò)算法等。Lahyani研究了多約束車輛路徑問題的若干變型，形成了一類富有車輛路徑問題[5]。Rahimi-Vahed等對多車輛段車輛路徑問題、周期車輛路徑問題進行了研究，使用模塊化啟發(fā)式算法對問題進行規(guī)劃[6]。1.3.2國內(nèi)研究現(xiàn)狀物流配送中心的選址及配送路徑優(yōu)化問題是整個生鮮物流網(wǎng)絡(luò)規(guī)劃設(shè)計中的兩個重要因素，整個物流系統(tǒng)的效率和效益與這兩個因素之間存在著緊密聯(lián)系。在配送中心的選址、車輛的配送路徑優(yōu)化以及選址-配送模型問題方面國內(nèi)專業(yè)學(xué)者做了大量的研究。馬帥對倉儲、未滿裝載懲罰兩個相互博弈的因素以及時間窗等因素進行分析，建立了配送中心選址及路徑優(yōu)化雙層規(guī)劃模型；然后設(shè)計了枚舉法與遺傳算法相結(jié)合的雙層規(guī)劃模型求解[7]。王萌構(gòu)建了考慮新鮮度和時間窗約束的生鮮物流配送優(yōu)化模型，結(jié)合配送時間對食品腐敗的影響及時間窗約束，并根據(jù)新鮮度變化函數(shù)，構(gòu)造最小化配送成本和最大化新鮮度的生鮮產(chǎn)品配送雙目標模型，然后設(shè)計了雙目標遺傳算法進行求解[8]。李慧針對O2O生鮮電商配送網(wǎng)絡(luò)配送成本過高，配送效率低下等問題，設(shè)計雙層布局規(guī)劃法，上層規(guī)劃考慮社區(qū)之間的物流聯(lián)系，將其作為綜合評價指標對末端節(jié)點的配送范圍進行劃分；下層規(guī)劃以配送成本最低為目標，對整個配送網(wǎng)絡(luò)進行以成本為導(dǎo)向的配送路徑優(yōu)化[9]。丁歡根據(jù)生鮮產(chǎn)品消費者所注重的配送時長問題，構(gòu)建客戶時間滿意度函數(shù)，并從不同客戶對企業(yè)來說存在差異性的實際情況出發(fā)，引入客戶價值的概念，建立客戶價值指標評價體系，又基于冷鏈物流的特點，分析冷鏈配送的成本構(gòu)成，通過推導(dǎo)生鮮食品的新鮮度函數(shù)，描述了因新鮮度下降對客戶需求量的影響；構(gòu)建了包括固定成本、貨損成本、運輸成本、能耗成本的選址成本模型，進而得到考慮客戶時間滿意度和價值權(quán)重的配送中心多目標選址模型[10]。第2章生鮮物流中心選址與配送路徑優(yōu)化問題研究2.1生鮮物流中心選址問題研究2.1.1選址問題概述在物流系統(tǒng)規(guī)劃設(shè)計中，物流節(jié)點的選址是一個重要的決策問題，它決定了整個物流網(wǎng)絡(luò)的結(jié)構(gòu)、模式和形狀。物流節(jié)點的選址決策就是確定整個物流系統(tǒng)中所需的節(jié)點數(shù)量、節(jié)點的地理位置，以及它們的服務(wù)對象分配方案[11]。生鮮物流配送中心是生鮮電商與終端消費者之間的橋梁，是生鮮電商加工處理和配送的關(guān)鍵物流節(jié)點。有效合理地對生鮮配送中心進行選址，可以顯著提高生鮮物流的配送效率，還可以降低車輛配送的成本以及貨物的損耗率，從而實現(xiàn)生鮮電商的效益最大化。物流配送中心選址問題（Location-AllocationProblem,LAP）是配送中心的定位-分配問題，標準的選址問題一般假設(shè)商品在設(shè)施與配送點的關(guān)系屬于點對點的關(guān)系，配送中心的配送模式屬于中心放射狀，在選址時不考慮車輛的路徑規(guī)劃問題。但在確定生鮮配送中心的具體位置后，相應(yīng)的車輛配送方案也會根據(jù)配送中心的位置做出相應(yīng)的調(diào)整。所以，配送中心的選址問題影響著車輛配送路線的規(guī)劃問題。（1）生鮮配送中心選址規(guī)劃的目標配送中心的選址是物流系統(tǒng)規(guī)劃的基礎(chǔ)性工作，對企業(yè)未來的生產(chǎn)和經(jīng)營起到非常重要的作用。1）成本最小化成本最小化是物流節(jié)點選址中最常見的目標，與物流節(jié)點選址規(guī)劃有關(guān)的成本主要包括設(shè)施成本和運輸成本。與設(shè)施相關(guān)的成本有固定成本、存儲成本和搬運成本。固定成本是指那些不隨設(shè)施的經(jīng)營活動水平而改變的成本，比如租金、稅金和折舊費都屬于固定成本。存儲成本與所存儲的貨物相關(guān)，典型的存儲成本有倉儲損耗、庫存占用的資金費用、貨物的保險費等。搬運成本是指隨著設(shè)施吞吐量變化的成本。運輸成本取決于運輸貨物的數(shù)量、運輸距離和運輸單價。所以配送中心的選址直接影響到運輸距離，與運輸成本控制有著密切的聯(lián)系。2）物流量最大化物流量反映了物流節(jié)點的作業(yè)能力。反映物流量的主要指標包括吞吐量和周轉(zhuǎn)量，這兩個指標可以用來測量物流節(jié)點的利用率，通常物流量越大，效益越高。但由于生鮮電商配送具有多品種、小批量、高頻度的特點，所以吞吐量和周轉(zhuǎn)量這兩個指標便無法適應(yīng)這種發(fā)展趨勢，如物流節(jié)點與顧客距離越遠，則周轉(zhuǎn)量越大，但運輸和管理費用也越高。因此，在配送中心選址時，首先要考慮成本最小，再考慮物流量最大。3）服務(wù)最優(yōu)化與物流節(jié)點選址決策直接相關(guān)的服務(wù)指標主要包括送貨時間、距離、速度和準時率。對于生鮮產(chǎn)品，產(chǎn)品的新鮮度是影響客戶滿意度的主要因素，所以運輸速度越快，產(chǎn)品越新鮮，這就要求物流節(jié)點與客戶的距離越近越好。4）發(fā)展?jié)摿ψ畲蠡锪髋渌椭行牟粌H投資大，而且投資回報率相對較低，所以在選址時還要考慮將來的發(fā)展?jié)摿Γㄎ锪鞴?jié)點生產(chǎn)擴展的可行性和消費者需求增長的潛力。（2）常見設(shè)施選址問題1）中值問題該問題是在區(qū)域中選擇若干個設(shè)施位置，使得該位置離需求點到最近設(shè)施的距離（或成本）的加權(quán)和最小。這種加權(quán)和最小的目標通常用于解決企業(yè)問題，所以也稱為“經(jīng)濟效益性”。這類問題是minimum問題，它的目標函數(shù)通常寫成以下形式：式中，：新的待定設(shè)施的位置坐標；：已存在且位置固定的需求點編號；：新設(shè)施在位置時到需求點的距離（或成本）。2）中心問題中心問題是根據(jù)使得被選擇設(shè)施位置離最遠需求點的距離（或成本）集合中取最小的原則，在區(qū)域內(nèi)選擇設(shè)施的位置。中心問題的目標是由可選集合中設(shè)施的單個成本最大的部分組成，它的目標是優(yōu)化最壞的情況，這種目標通常是在軍隊、緊急情況或者公共部門使用。中心問題的目標函數(shù)是：式中，：新的待定設(shè)施的數(shù)量：需求地編號：新設(shè)施在位置時到需求點的距離（或成本）。3）反中心問題反中心問題和中心問題相反，它是根據(jù)在一定區(qū)域內(nèi)使得被選擇設(shè)施位置離最近需求點的距離（或成本）集合中取最大的原則進行選址。它的目標也是優(yōu)化最壞的情況，這種目標通常在有害設(shè)施的選址中使用，其目標函數(shù)如下：式中，：新的待定設(shè)施的數(shù)量：需求地編號：新設(shè)施在位置時到需求點的距離（或成本）。4）覆蓋問題覆蓋問題包括最大覆蓋問題和集合覆蓋問題，它是一類離散點選址問題。最大覆蓋問題是對有限個服務(wù)設(shè)施進行選址，并為盡可能多的需求點提高服務(wù)，但可能無法滿足所有需求點的需求。集合覆蓋問題是選擇盡可能少的設(shè)施來滿足所有需求點的需求。以上問題的具體解法見2.1.2。2.1.2常見求解模型介紹在進行生鮮物流配送中心選址時，除了要考慮配送中心的建設(shè)成本和車輛的運輸成本外，還需要使用合適的數(shù)學(xué)模型來進行求解，以獲得最優(yōu)的決策方案。上文的中值問題、中心和反中心問題的求解模型一般是用于單個設(shè)施節(jié)點的選址，覆蓋模型通常用于多個設(shè)施節(jié)點的選址。下面本文介紹幾種常見的選址模型，分別為重心法、最大覆蓋模型、集合覆蓋模型。（1）重心法重心法適用于單個生鮮物流配送中心的選址研究。假設(shè)每個終端提貨點所覆蓋的范圍需求為，坐標為；配送中心的坐標為，生鮮物流配送中心到第個終端提貨點的距離是，配送單位質(zhì)量的生鮮產(chǎn)品的單位運輸費用為，則利用重心法進行選址的數(shù)學(xué)模型為：（2-1）（2-2）模型中，目標函數(shù)（2-1）表示車輛配送的總費用最小，約束條件（2-2）表示終端提貨點需求量為非負。在對模型求解時，能夠使得達到最小的點即為最佳決策點。重心法由于自身具有缺陷，其沒有對選址的位置進行約束，所以可能導(dǎo)致選址位置的不合理，重心法往往只能作為參考。（2）最大覆蓋模型最大覆蓋模型的目標是選擇有限數(shù)量的物流配送中心，并為盡可能多的需求點服務(wù)，但可能不能滿足所有需求點的需求。最大覆蓋模型的數(shù)學(xué)模型如下：（2-3） S.t. （2-4）（2-5） （2-6）（2-7）（2-8）模型中，：個需求點集合；：第個需求點的需求量；：設(shè)施節(jié)點的容量；：設(shè)施節(jié)點所覆蓋的需求點集合；：可以覆蓋需求點的設(shè)施集合；：允許投建的設(shè)施數(shù)；：節(jié)點需求中被分配給設(shè)施節(jié)點服務(wù)的部分，小于等于1；：節(jié)點是否被選中成為設(shè)施，如選中則為1，否則為0。式（2-3）為目標函數(shù)，其目標是為盡可能多的需求點提供服務(wù)，滿足他們的需求；式（2-4）表示需求點的需求有可能得不到滿足；式（2-5）是對每個設(shè)施的服務(wù)能力的限制；式（2-6）是對允許建設(shè)的設(shè)施的數(shù)量的限制；式（2-7）是指允許一個設(shè)施為某個需求點提供部分需求。以上模型是一個混合的0-1整數(shù)規(guī)劃模型，通?？刹捎镁_求解方法和啟發(fā)式方法求解。Richard和CharlesR.Velle設(shè)計貪婪啟發(fā)式算法，用以對最大覆蓋模型進行求解。貪婪啟發(fā)式算法首先求出可以作為候選點的集合，并以一個空集作為原始解的集合，然后在候選點集合中選擇一個具有最大滿足能力的候選點進入原始解集合，作為二次解，依次重復(fù)進行以上步驟，直到設(shè)施的數(shù)目滿足要求為止。（3）集合覆蓋模型集合覆蓋模型的目標是用盡可能少的設(shè)施去滿足所有需求點的需求，其數(shù)學(xué)模型如下：（2-9）S.t.（2-10）（2-11）（2-12）（2-13）式中，：個需求點集合；：第個需求點的需求量；：設(shè)施節(jié)點的容量；：設(shè)施節(jié)點所覆蓋的需求點集合；：可以覆蓋需求點的設(shè)施集合；：節(jié)點需求中被分配給設(shè)施節(jié)點服務(wù)的部分，小于等于1；：節(jié)點是否被選中成為設(shè)施，如選中則為1，否則為0。模型中，式（2-9）是目標函數(shù)，使被選為設(shè)施的節(jié)點數(shù)最??；式（2-10）保證了每個需求點的需求都能得到滿足；式（2-11）是對每個設(shè)施的服務(wù)能力的限制；（2-12）表示允許一個設(shè)施為某個需求點提供部分需求。對此類帶有約束的極值問題，一種求解方法是用分支定界，能夠找到小規(guī)模問題的最優(yōu)解。第二種求解方法是啟發(fā)式算法，可以用于對大規(guī)模問題的分析與求解，但所得到的結(jié)果不能保證是最優(yōu)解。2.2生鮮物流配送路徑優(yōu)化研究2.2.1路徑優(yōu)化問題概述運輸路線優(yōu)化主要是選擇起點到終點的最短路，最短路的度量單位可能是時間最短、距離最短或費用最小等[11]。運輸問題可以分為點點之間運輸問題、多點之間運輸問題及回路運輸問題。路徑優(yōu)化問題目的是為了通過科學(xué)、合理地對配送路線進行規(guī)劃，在滿足車輛載重和配送時間約束等條件下實現(xiàn)成本最低和收益最大。生鮮物流配送路徑優(yōu)化問題可以描述為：在生鮮物流配送中心和終端提貨點（或客戶）的具體位置和需求量確定時，安排冷藏車為每個終端提供生鮮產(chǎn)品的配送業(yè)務(wù)。每個終端需求點只由一輛車輛配送，在優(yōu)化時要考慮車輛的載重能力限制、行駛距離和配送時間段等約束，最終達到例如配送費用最少、冷藏車輛數(shù)目最小、配送時間最短等優(yōu)化目標。生鮮電商產(chǎn)品配送具有小批量、多品類、多頻率的特點，所以通常屬于是多點之間的運輸問題，最常見的兩種運輸模型為單回路運輸——TSP模型和多回路運輸——VRP模型。（1）TSP模型旅行商問題（TravelingSalesmanProblem,TSP）是單回路運輸問題中最典型的一個模型。其含義為：一個旅行商從某個城市出發(fā)，到n個城市中去售貨，要求訪問每個城市各一次且一次，然后回到原城市，問這個旅行商應(yīng)該走什么樣的路線才能使走過的總里程最短或旅行費用最低[11]。應(yīng)用圖論，可以將以上問題轉(zhuǎn)化為如下描述：在給出一個有n個頂點的連通圖中（有向或無向），尋求一條包含所有n個頂點的具有最小總權(quán)（可以是距離、費用、時間等）的回路。TSP問題的數(shù)學(xué)模型為：（2-14）S.t.（2-15）（2-16）（2-17）（2-18）式中，決策變量表示不連接到的邊；表示連接到的邊。是到邊上的權(quán)數(shù)。（2-15）表示每個頂點只有一條邊出去；（2-16）是指每個頂點只有一條邊進入；式（2-17）用來限制除了起點邊和終點邊以外，其它選中的邊不構(gòu)成回路用來避免出現(xiàn)子回路的現(xiàn)象。上述模型是一個0-1整數(shù)規(guī)劃問題，對于一些小規(guī)模問題的求解，可以用分支定界方法進行求解；而大規(guī)模問題需要使用啟發(fā)式算法，如模擬退火算法、禁忌算法、遺傳算法、蟻群算法等。（2）VRP模型車輛調(diào)度問題（VehicleRoutingProblem,VRP）一般是指對一系列發(fā)貨點和收貨點，組織調(diào)用一定的車輛，安排適當?shù)男熊嚶肪€，使車輛能夠有序地通過，在滿足制定的約束條件下（貨物的需求量與發(fā)貨量、交貨發(fā)貨時間、車輛可載量限制、行駛里程限制、行駛時間限制等），力爭實現(xiàn)一定的目標（如車輛空駛總里程最短、運輸總費用最低、車輛按一定時間到達、使用的車輛數(shù)量最小等）[11]。VRP的數(shù)學(xué)模型如下：配送中心O擁有的車輛數(shù)目是Q，配送點的總數(shù)目為,終端節(jié)點需求量為，配送車輛的最大載重量為，表示終端節(jié)點到節(jié)點的距離。（2-19）S.t.（2-20）（2-21）（2-22）（2-23）（2-24）（2-25）（2-26）上述模型中，式（2-19）為目標函數(shù)，表示配送車輛的配送距離的總和最??；式（2-20）和式（2-21）表示每個終端節(jié)點有且僅有一輛配送車輛服務(wù)；式（2-22）表示所有需求點的需求總和不超過配送車輛的最大承載量；式（2-23）是對可以提供服務(wù)的車輛的數(shù)量限制；式（2-24）表示配送車輛配送路線為回路，即車輛運輸?shù)钠瘘c和終點都是配送中心；（2-25）和（2-26）是模型的決策變量。2.2.2常見求解模型介紹單回路運輸問題主要用于對單一車輛的路徑安排，目標是在該車輛遍歷所有目標終端節(jié)點的同時，實現(xiàn)所行駛的距離最短。多回路運輸問題又可以成為車輛調(diào)度問題，是針對有大量服務(wù)對象的實體。當進行車輛運輸服務(wù)時，由于條件的限制，無法用一條回路來完成任務(wù)，解決此類問題的核心是對車輛的調(diào)度。下面本文將針對兩種回路運輸提出常見的解決方法。（1）最近鄰點法計算步驟：①從零點（即配送中心）開始，作為整個回路的起點。②找到離剛剛加入到回路中的上一個頂點最近的一個頂點，并將其加入到回路中。③重復(fù)②，直到將所有的頂點都加入到回路中。④將最后一個加入的頂點與起點連起來。（2）節(jié)約算法節(jié)約算法的核心思想是將運輸問題中存在的兩個回路與合并成一個回路。然后計算合并后的回路的運輸距離，與原來兩個回路的距離和進行比較，如果合并之后的回路運輸距離下降，則說明節(jié)約了運輸距離。節(jié)約距離的節(jié)約值用表示，計算公式為：2.3生鮮物流配送中心選址及路徑優(yōu)化問題研究2.3.1選址-路徑問題概述由于目前生鮮物流網(wǎng)絡(luò)不斷擴展，城市交通網(wǎng)絡(luò)日益復(fù)雜，所以生鮮物流配送中心選址對車輛路徑規(guī)劃的影響越來越大。例如，若僅考慮配送中心的選址問題則無法對車輛的高油耗和運輸距離進行分析；如果僅從配送路徑分析，則無法將可覆蓋的終端節(jié)點考慮在內(nèi)。因此，在對生鮮產(chǎn)品配送中心選址和車輛配送路線規(guī)劃時，要從集成優(yōu)化的角度出發(fā)，將兩者進行有機結(jié)合統(tǒng)籌規(guī)劃，從而可以避免單獨優(yōu)化帶來的局限和瓶頸。選址-路徑問題（LocationRoutingProblem，LRP）所要解決的問題是從一組備選的設(shè)施中選擇一個或者多個設(shè)施作為配送中心為終端客戶進行服務(wù)，同時合理地規(guī)劃在滿足所有終端客戶需求的同時，實現(xiàn)配送成本的降低。LRP問題可以從供應(yīng)鏈的兩端對生鮮物流網(wǎng)絡(luò)進行集成優(yōu)化，基于系統(tǒng)論，實現(xiàn)整體生鮮物流系統(tǒng)成本的最小化。2.3.2選址-路徑基本模型選址-路徑問題與上文介紹的選址問題和路徑問題有密切的聯(lián)系，但將二者基于系統(tǒng)集成的方法結(jié)合起來所組成的模型也會隨之更為復(fù)雜和困難。選址-路徑數(shù)學(xué)模型如下：（2-27）S.t.（2-28）（2-29）（2-30）（2-31）（2-32）（2-33）模型中，表示客戶與設(shè)施的集合；表示設(shè)施集合；為客戶集合；表示設(shè)施的固定成本；是客戶的需求量；為由運輸?shù)降某杀?；表示車輛集合；為車輛的載重量；為0,1變量。式（2-27）為目標函數(shù)，即系統(tǒng)整體成本最低；式（2-28）是對車輛載重的限制；式（2-29）表示客戶僅由一輛車服務(wù)；式（2-30）和（2-31）是流量守恒公式；最后兩個式子表示車輛完成配送任務(wù)后返回配送中心。本文基于選址-路徑模型，將生鮮物流配送中心的選址與配送運輸路線優(yōu)化結(jié)合起來進行研究。通過建立選址和配送路徑優(yōu)化的雙層目標規(guī)劃，設(shè)計基于最短路徑的算法，最終求解出實現(xiàn)降低物流系統(tǒng)成本的選址和路線規(guī)劃結(jié)果。第3章生鮮物流配送中心選址及路徑優(yōu)化模型分析3.1雙層規(guī)劃模型介紹雙層規(guī)劃模型具有二層傳遞性，其上下層的模型都有各自的目標函數(shù)、約束條件和決策變量。雙層規(guī)劃數(shù)學(xué)模型如下：（3-1）（3-2）其中反應(yīng)函數(shù)由下層規(guī)劃所得：（3-3）（3-4）上述模型中，式（3-1）是上層規(guī)劃模型的目標函數(shù)；式（3-2）是上層規(guī)劃模型的約束條件；（3-3）和（3-4）分別表示下層規(guī)劃模型的目標函數(shù)和約束條件。被稱為反應(yīng)函數(shù)，它是上層和下層模型的共同約束條件，對上層和下層的決策都有影響，可以使可行解在雙重約束條件下達到平衡?？梢詫㈦p層規(guī)劃模型看作一個分層級的系統(tǒng)，由處于兩個層級的決策者進行決策。上層的決策者是領(lǐng)導(dǎo)者，控制變量，下層的決策者稱為跟隨者，控制決策變量。在雙層規(guī)劃模型中，上層規(guī)劃決策時要考慮可能給下層帶來的不利影響，下層規(guī)劃時也要考慮如何在上層決策達到最優(yōu)的前提下可以實現(xiàn)自己的最優(yōu)化。所以，雙層規(guī)劃模型的上下層之間相互制約、相互聯(lián)系，通過雙方結(jié)果的不斷改進，實現(xiàn)整個系統(tǒng)的績效最優(yōu)。3.2模型的構(gòu)建思路上層規(guī)劃模型的目標是確定生鮮物流配送中心的選址位置和數(shù)量，是在給定數(shù)量和位置的需求集合和可選設(shè)施位置集合的前提下，考慮配送中心的固定成本、配送成本和腐敗成本（生鮮產(chǎn)品在運輸途中的損耗成本），用來共同對生鮮物流配送中心選址問題進行優(yōu)化決策。下層規(guī)劃模型是在上層模型確定了配送中心的位置之后，對配送中心的車輛配送路線進行規(guī)劃?？紤]到生鮮產(chǎn)品對時間的高要求，所以以總配送距離最小為目標，并加入車輛配送的固定成本、運輸成本、貨損成本、時間窗懲罰成本。通過雙層模型之間的協(xié)調(diào)優(yōu)化，在保證生鮮產(chǎn)品新鮮度的前提下，將整個成品配送物流系統(tǒng)的總成本降至最低。雙層規(guī)劃模型的構(gòu)造思路如下圖3-1：圖3-1雙層規(guī)劃模型的構(gòu)建思路3.3上層模型的構(gòu)建上層模型要解決生鮮物流配送中心選址問題，其可描述為：在某區(qū)域中，在給定數(shù)量和位置的終端提貨點集合的前提下，從一個候選配送中心位置集合中選擇合適的給定數(shù)量的配送中心位置，并指派每一個提貨點僅被一個配送中心服務(wù)，使得配送中心的總成本最小。3.3.1模型假設(shè)本文在建立區(qū)域生鮮物流配送中心選址模型時，做出如下假設(shè)：（1）配送中心的可選位置局限在一定的范圍之內(nèi)；（2）一個終端提貨點只由一個配送中心提供服務(wù)；（3）所在區(qū)域內(nèi)客戶的需求量可以預(yù)測；（4）區(qū)域內(nèi)配送中心的個數(shù)是有限的；（5）建模時不考慮對客戶的價格折扣和訂購的規(guī)模效應(yīng)；（6）不考慮生鮮商品的存儲成本；（7）不考慮配送中心的吞吐頻率限制。3.3.2符號介紹表3-1上層模型符號說明符號含義表示第個生鮮物流配送中心到第個提貨點的實際行駛里程表示配送中心與終端提貨點之間冷鏈車輛的平均配送速度表示配送中心的集合表示終端提貨點的集合表示提貨點的需求量表示配送中心的固定成本表示第個配送中心到第個提貨點的單位運輸費用表示運輸產(chǎn)品的單價表示生鮮產(chǎn)品的變質(zhì)速率系數(shù)表示區(qū)域生鮮物流配送中心的數(shù)量表示區(qū)域內(nèi)生鮮物流配送中心的吞吐量3.3.3成本分析基于對生鮮物流配送中心運營和配送中存在的成本分析，在建立生鮮物流配送中心選址模型時，將考慮以下幾種成本構(gòu)成，在滿足一定條件的基礎(chǔ)上，實現(xiàn)配送中心成本的最小化。（1）配送中心的固定成本在本文研究背景下，拼多多的物流配送中心是租賃的第三方物流企業(yè)的倉庫，所以此處的配送中心成本主要是由租賃成本、運營成本和購買冷鏈運輸車輛、設(shè)施設(shè)備的成本構(gòu)成。由于成本構(gòu)成較為復(fù)雜，所以此處以表示配送中心的固定成本，所以配送中心的固定成本可以表示為。（2）配送成本配送成本在生鮮電商企業(yè)的日常運營中占據(jù)很大的比重，它能夠衡量一個企業(yè)在配送路徑規(guī)劃方面的能力。配送成本屬于可變成本，它與終端客戶需求量、客戶距離和單位配送成本有關(guān)。此處以表示需求點的需求量，表示從第個配送中心到第個需求點的運輸距離，表示第個配送中心到第個需求點的單位運輸費用。所以，生鮮物流配送中心的配送成本為。（3）腐敗成本腐敗成本也可以看做是貨損成本，由于生鮮產(chǎn)品對溫度和運輸時間的嚴格要求，所以在倉儲和運輸過程中都會存在貨損。本文用腐敗系數(shù)來衡量生鮮產(chǎn)品的貨損成本，根據(jù)國內(nèi)外學(xué)者的研究，得出生鮮產(chǎn)品的腐敗系數(shù)為[12]，其中表示從配送中心到終端客戶運輸?shù)钠骄俣?。用表示運送物品的單價，則腐敗成本可以表示為。3.3.4生鮮物流配送中心選址模型本文研究區(qū)域生鮮物流配送中心的選址問題，由于受到區(qū)域的經(jīng)濟因素和市場需求因素的影響，所以對區(qū)域的生鮮需求可以進行有效的預(yù)測，因此本文研究的問題符合P-中值問題的基本要求。所以本文在P-中值模型的基礎(chǔ)上，在目標函數(shù)中加入了配送中心的固定成本和生鮮產(chǎn)品的腐敗成本，追求在滿足區(qū)域內(nèi)所有終端需求點需求的情況下，實現(xiàn)區(qū)域生鮮物流配送中心的總成本最小。區(qū)域生鮮物流配送中心選址模型如下：（3-5）S.t.（3-6）（3-7）（3-8）（3-9）（3-10）模型中，式（3-5）是目標函數(shù)，目標實現(xiàn)配送中心的固定成本、配送成本和生鮮產(chǎn)品腐敗成本的最小化；式（3-6）是對配送中心數(shù)量的限制；（3-7）是對配送中心吞吐量的約束，要滿足終端客戶的需求；式（3-8）保證每個需求點只能由一個配送中心提供服務(wù)；（3-9）可以有效地保證沒有選中的配送中心候選點不能為需求點提供服務(wù)。模型中的和是0-1決策變量，表示配送中心是否被選中。3.4下層模型的構(gòu)建生鮮產(chǎn)品的物流配送問題可以描述為：配送由一個配送中心和多個終端客戶構(gòu)成，配送中心負責(zé)個終端提貨點的生鮮產(chǎn)品的配送，提貨點的需求量為。配送中心擁有輛車，每輛車被分配一定的配送任務(wù)，可以將每輛車的配送路徑問題看為TSP問題，每輛車從配送中心出發(fā)，遍歷其配送任務(wù)中的所有終端提貨點各一次且一次，然后回到配送中心。配送車輛的最大載重量為，且每個提貨點的需求量不大于每輛車的最大載重量。3.4.1模型假設(shè)（1）配送過程中，訂單都可以一次配送成功；（2）訂單不可拆分，單個訂單的商品量不超過配送車輛的最大載重量；（3）客戶的訂單信息已知，每輛車的任務(wù)已知；（4）每個配送路線由一個配送員工負責(zé)，且只負責(zé)這一條路線；（5）假設(shè)車輛內(nèi)的溫度為恒溫，只考慮配送時間對生鮮產(chǎn)品新鮮度的影響；（6）每輛車輛的配送任務(wù)不超過車輛的最大容量；（7）配送中心的運力充足，可以完成所有的訂單配送。3.4.2符號介紹表3-2下層模型符號說明符號含義表示客戶集合，其中表示客戶點配送中心提貨點的集合，表示配送中心，表示配送車輛集合，表示配送車輛的最大載重量表示車輛的行駛速度表示提貨點的需求量表示車輛的單位運輸成本表示使用車輛的固定成本表示提貨點到提貨點的距離表示車輛從提貨點到提貨點的時間，且提貨點由車輛服務(wù)時取1，否則為0表示車輛到達提貨點的時間表示產(chǎn)品配送到客戶手中的新鮮度車輛從提貨點到取1，否則為03.4.3成本分析生鮮電商產(chǎn)品配送中最注重的是客戶滿意度，考慮到生鮮產(chǎn)品的易腐性，且生鮮產(chǎn)品對配送時間和冷鏈設(shè)備有較高的要求，所以在進行成本分析時要將冷鏈車輛和相關(guān)設(shè)備的成本以及時間窗約束考慮在內(nèi)。（1）固定成本固定成本包括購買和維護車輛的成本、人員的薪酬等。設(shè)為單位配送車輛的固定成本，為0-1變量，表示車輛從車場出發(fā)，則配送中心總的固定成本為。（2）運輸成本生鮮產(chǎn)品配送車輛的運輸成本包括車輛的燃油費用，與行駛里程有關(guān)；冷藏車輛及相關(guān)設(shè)備的制冷費用，與配送時間有關(guān)。設(shè)為單位距離的配送車輛運輸成本；為提貨點到提貨點的行駛距離；為0-1變量，若配送車輛從提貨點行駛到提貨點，則，否則為0。所以，配送車輛的運輸成本為。（3）貨損成本貨損成本是生鮮產(chǎn)品在配送過程中因損或腐敗而造成的，在前文中提到產(chǎn)品的腐敗速率隨時間變化并呈指數(shù)型變化。有學(xué)者曾總結(jié)出貨損函數(shù)為[8],其中表示商品離開車輛送達客戶的時間，是生鮮產(chǎn)品的時間敏感程度，通常與產(chǎn)品的生命周期有關(guān)。因此，生鮮產(chǎn)品的貨損成本可表示為。其中，是生鮮產(chǎn)品的單位價值；是車輛提供給提貨點的商品量；表示提貨點的貨物是否由車輛配送；是車輛為提貨點服務(wù)的時間；為車輛從配送中心出發(fā)的時間；到達提貨點產(chǎn)品新鮮度為。（4）時間懲罰成本多多買菜平臺的產(chǎn)品配送雖然省略了“最后一公里”環(huán)節(jié)，但從配送中心送至各個提貨點的時間仍然受到客戶滿意度時間窗的限制。如果配送車輛提前到達提貨點，則車輛可能會產(chǎn)生一定的機會損失成本，且貨物在沒有溫度控制的情況下會產(chǎn)生更多的損耗；而如果車輛延遲到達，車輛會付出更多的冷藏費用，同時可能造成消費者提貨等待的情況，降低了客戶的滿意度?；旌蠒r間窗懲罰函數(shù)[8]可以表示為如下式：（3-11）上式（3-11）中，是車輛到達提貨點時相應(yīng)的時間窗懲罰成本；是客戶滿意度最優(yōu)的時間窗，若車輛在此時間段內(nèi)到達提貨點，客戶的滿意度最大；是提貨點的可服務(wù)時間窗，只有在此范圍內(nèi)才接受服務(wù)；、分別是配送車輛提前到達和延遲到達的懲罰系數(shù)。3.4.4配送路線優(yōu)化模型參考上文中介紹的TSP模型，在考慮成本時加入了固定成本、貨損成本和配送時間窗懲罰成本，以配送總成本最小化為目標，建立了配送路線規(guī)劃模型。生鮮產(chǎn)品配送路線優(yōu)化模型如下：目標函數(shù)：S.t.（3-12）（3-13）（3-14）（3-15）（3-16）（3-17）（3-18）（3-19）在上述模型中，目標函數(shù)為固定成本、運輸成本、貨損成本和時間窗懲罰成本之和的最小值。式（3-12）表示配送中的車輛數(shù)不超過配送中心的車輛總數(shù)；式（3-13）表示配送車輛從配送中心出發(fā)，完成后再返回配送中心；（3-14）是指每輛車的配送任務(wù)不可超過其最大載重量；（3-15）和（3-16）是指每個提貨點只被一輛配送車服務(wù)，且只服務(wù)一次；（3-17）是生鮮產(chǎn)品的新鮮度函數(shù)，用于求其貨損成本；式（3-18）是車輛從提貨點到提貨點的時間；（3-19）是決策變量。第4章模型求解算法研究4.1雙層規(guī)劃模型的求解流程在雙層規(guī)劃模型中，上層的配送中心選址問題是企業(yè)發(fā)展中的長期規(guī)劃，屬于戰(zhàn)略性決策；下層規(guī)劃中的車輛路徑規(guī)劃問題屬于短期可調(diào)整的規(guī)劃[13]。前文曾說過，上層規(guī)劃相當于領(lǐng)導(dǎo)者，下層規(guī)劃是雙層規(guī)劃中的跟隨者。上層規(guī)劃模型的目標追求的是整體的最優(yōu)化，下層規(guī)劃模型則是跟隨上層給出的方案，追求自身目標的最優(yōu)，并將結(jié)果返回給上層領(lǐng)導(dǎo)者，上層繼續(xù)對方案進行優(yōu)化，依次類推，經(jīng)過多次迭代，最終實現(xiàn)雙層規(guī)劃模型的整體最優(yōu)。（1）雙層規(guī)劃模型的求解思路雙層規(guī)劃模型的一般求解思路為：求出上層模型的最優(yōu)解，將上層規(guī)劃模型的最優(yōu)方案代入下層模型的目標函數(shù)，求出下層模型的最優(yōu)解，從而得出了整個雙層規(guī)劃模型的最優(yōu)解。生鮮物流配送中心選址和配送路線優(yōu)化雙層規(guī)劃模型的詳細求解思路為：1）求解上層模型確定選址方案；2）下層模型根據(jù)上層模型得出的選址方案求解配送路線規(guī)劃方案；3）將下層的配送路線規(guī)劃結(jié)果返回給上層，對上層規(guī)劃模型中的可變成本（配送費用）進行重新求解；4）把上層目標作為整體雙層規(guī)劃的目標進行迭代，直到滿足迭代終止條件。（2）求解算法框架本文建立的選址-路徑雙層規(guī)劃模型是一個典型的NP-hard問題，運用一般的運籌學(xué)方法無法求得其精確結(jié)果，因此本文構(gòu)建了雙層啟發(fā)式算法求解基于雙層規(guī)劃的選址-路徑問題，如圖4-1。上層模型是根據(jù)P-中值模型改進得到的，所以此處采取一種常用于解決P-中值問題的貪婪取走啟發(fā)式算法。通過求解上層規(guī)劃模型得到最優(yōu)選址方案，在此基礎(chǔ)之上求解下層模型。此處的生鮮電商車輛配送問題可以看作是TSP問題，由一輛車從配送中心出發(fā)，向其任務(wù)計劃中的提貨點配送生鮮產(chǎn)品，要求車輛必須經(jīng)過計劃中的所有提貨點各一次且一次，且以行駛距離最短為目標，最終返回到配送中心。在求解TSP問題時，本文采用最近插入法求解車輛的配送路線。圖4-1雙層啟發(fā)式算法框架4.2上層模型的求解算法貪婪取走啟發(fā)式算法（greedydroppingheuristicalgorithm）是一種常用于解決P-中值模型的算法。它是一種不追求最優(yōu)解，目標獲得相對較為滿意的結(jié)果的啟發(fā)式算法。在使用貪婪取走啟發(fā)式算法求解時，首先要明確求解目標，并且制定一個可行的貪婪準則，以當前狀態(tài)為最優(yōu)選擇，不考慮其他各種可能的整體情況，從初始狀態(tài)開始一步步地搜索，直到找到滿足問題要求的目標值。貪婪取走啟發(fā)式算法的基本步驟如下[14]：（1）初始化，令，將所有的候選位置都選中，然后將每個客戶指派給距離最近的一個候選設(shè)施。（2）選擇并取走一個位置點，要求其滿足以下條件：假設(shè)將該點取走，并將它的客戶重新指派給距離最近的一個候選位置，總費用的增量最小。若滿足，則。（3）重復(fù)（2），直到。4.3下層模型的求解算法車輛配送路線規(guī)劃是短期策略，每次的配送路線也要根據(jù)車輛的任務(wù)來重新規(guī)劃，所以本文在研究配送路線優(yōu)化時，僅考慮一輛車的單回路運輸問題。解決TSP問題的常用簡單的啟發(fā)式算法有最近鄰點法和最近插入法，最近插入法雖比鄰點法復(fù)雜，但能夠得到相對比較滿意的結(jié)果。最近插入法的基本原理是：首先找到一個離配送中心最近的點構(gòu)成一個子回路，然后在剩下的提貨點集合中尋找離子回路中的某一點最近的節(jié)點，將其插入到子回路中，依次不斷推進，直到將所有的提貨點都插入到閉合回路中，所形成的回路就是該TPS問題的解。最近插入法的具體步驟[11]如下：（1）找出距離最小的節(jié)點，形成一個子回路；（2）在剩下的節(jié)點中，找出一個距離子回路中的某個節(jié)點最近的節(jié)點；（3）在形成的子回路中找到一條弧，使得最小，然后將節(jié)點加入到子回路中，插入到節(jié)點和之間，用兩條新弧和來代替原來的；（4）重復(fù)（2）和（3）步驟，直到所有的節(jié)點都加入到閉回路中。第5章案例分析基于上文對生鮮電商物流配送中心選址和配送路線規(guī)劃的分析，本文建立了雙層規(guī)劃模型，并研究了對應(yīng)的求解算法。本章以多多買菜在HD區(qū)的生鮮配送中心選址和配送路線優(yōu)化為例，收集整理相關(guān)數(shù)據(jù)，使用本文所建模型和研究算法進行求解，給出多多買菜在HD區(qū)的配送中心選址和配送路線優(yōu)化方案，并對求解結(jié)果進行分析。5.1案例背景案例的分析對象是HD區(qū)的多多買菜，它是拼多多平臺提供的一個線上買菜服務(wù)。拼多多是我國移動互聯(lián)網(wǎng)的主流電子商務(wù)應(yīng)用產(chǎn)品，多多買菜是其在2020年8月上線的一個“線上下單+線下自提”的生鮮產(chǎn)品交易平臺，目前上線的生鮮商品包括蔬菜、水果、肉蛋和乳品，等等。近年來，我國生鮮電商市場規(guī)模不斷擴大，隨之而來的是各個企業(yè)之間的競爭。物流作為企業(yè)的第三利潤源泉，越來越受到生鮮企業(yè)的重視，企業(yè)力圖通過科學(xué)的方法降低生鮮物流的成本，提高生鮮物流運行效率，提高企業(yè)的利潤。本文基于多多買菜“線上下單+線下提貨”的運行模式，研究討論多多買菜在HD區(qū)的生鮮物流配送中心選址和向各個提貨點配送時的路線優(yōu)化問題。本文選取了10個終端提貨點作為主要研究對象，擬建2個配送中心，進行選址-配送的協(xié)同優(yōu)化，給出多多買菜在HD區(qū)較優(yōu)的生鮮物流配送中心選址方案和車輛配送路線優(yōu)化方案，力求實現(xiàn)降低生鮮產(chǎn)品損耗、提高配送效率和降低生鮮物流總成本的目標。5.2上層規(guī)劃——配送中心選址已知多多買菜在HD區(qū)現(xiàn)有10個提貨點，公司擬租賃2個配送倉庫作為多多買菜平臺集散分配的生鮮物流配送中心。公司希望以最低的運輸成本來滿足10個提貨點所覆蓋地區(qū)的需求。經(jīng)過考察篩選后，公司確定了5個候選地，從候選地到各提貨點的單位運輸成本如下表5-1所示，各候選點和提貨點的位置分布如下圖5-1。表5-1各提貨點需求量與單位運輸成本矩陣表需求量3045481035102560703550628152532101145302024122558122560301565301557331365351645282022303520168282518354012302018281518圖5-1候選點和提貨點位置分布圖由3.4.3可知配送中心的固定成本主要是由租賃成本、運營成本和購買運輸車輛和冷藏設(shè)施設(shè)備的成本構(gòu)成。由于5個候選位置的地理位置、交通狀況和經(jīng)濟發(fā)展水平不同，所以其租賃成本、基礎(chǔ)設(shè)施條件也不同。通過綜合分析計算，得到了5個候選位置的固定成本如下表5-2：表5-25個候選位置的固定成本表候選點固定成本（每日）腐敗成本200當日配送生鮮商品總價值的2%250400300500利用層次分析法（AHP）確定配送中心選址三項成本的權(quán)重系數(shù)，，。首先由專家利用數(shù)字1-9對配送成本、固定成本和腐敗成本的重要性進行打分。構(gòu)造出比較判斷矩陣，利用標度值的倒數(shù)作為標度，求出各項成本在決策中所占權(quán)重，求解的判斷矩陣及求解結(jié)果如下表5-3：表5-3三項成本判斷矩陣及權(quán)重表配送成本固定成本腐敗成本配送成本1790.67固定成本1/711/20.165腐敗成本1/9210.165由上表5-3可知，配送成本是在進行生鮮物流配送中心選址時最重要的因素。在4.2中本文研究了貪婪取走啟發(fā)式算法，用來求解改進后的P-中值模型。由層次分析的結(jié)果可知，配送成本在目標函數(shù)中占比高達67%，且各個候選點的固定成本和腐敗成本相差較少，所以本文在進行生鮮物流配送中心選址時主要考慮配送中心的配送成本。利用貪婪取走啟發(fā)式算法求解P-中值問題的具體過程如下：（1）對表5-1中的單位運輸成本進行比較，按照距離最近進行分派，得到的初始化結(jié)果如圖5-2，總費用為：150+100+128+300+270+110+216+320+195+180=1969，k=5圖5-2初始化指派結(jié)果（2）分別移走候選地、、、、，然后對其原本服務(wù)的提貨點進行重新指派，并計算各自的增量。當移走后，受影響的是，將指派給，產(chǎn)生的增量=210-150=60；當移走后，受影響的是，將指派給，產(chǎn)生的增量=375-180=195；當移走后，受影響的是、、，將指派給，指派給，指派給，所產(chǎn)生的增量=390+560+300-195-320-216=519；當移走后，受影響的是，將指派給，產(chǎn)生的增量=300-100=200；當移走后，受影響的是、、、，將指派給，指派給，指派給，指派給，產(chǎn)生的增量=165+500+160+324-110-300-128-270=341；所以，選擇移走后產(chǎn)生的影響最小的點，將其移走后并把重新指派給，K=4。同理，依次取走、，最終將指派給,指派給，給，k=2,循環(huán)結(jié)束。最終的結(jié)果為選擇候選點和，總的運輸成本為2564，的運輸成本為1106，的運輸成本為1458，指派結(jié)果如圖5-3所示。圖5-3指派后的結(jié)果5.3下層規(guī)劃——配送路徑優(yōu)化假設(shè)配送中心，每天用一輛車給其服務(wù)的提貨點配送，要求車輛對每個提貨點只能去一次，送完貨后返回配送中心。配送中心和提貨點、、、之間的距離矩陣如表5-4所示。此類單回路運輸問題一般采用啟發(fā)式算法進行求解，此處采用最近插入法求解，力求獲得相對比較滿意的解。表5-4配送中心與提貨點之間的距離矩陣點元素-9768-10189-912-12-求解過程：車輛從配送中心出發(fā)，最終再回到。觀察上表5-4，比較從出發(fā)的所有的路徑大小，得出，則令配送中心和構(gòu)成一個子回路，即。繼續(xù)考慮剩下的提貨點、、到子回路中某一節(jié)點的最小距離，求得點，，將插入和之間，構(gòu)成新的回路。同理，繼續(xù)找到下一點，，計算分析應(yīng)將插入到回路的哪個位置：①插入之間，②插入之間，③插入之間，將插入到距離增量最小的之間，所