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

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