帶時(shí)間窗約束的快遞車輛路徑優(yōu)化及MATLAB求解的實(shí)證研究摘要車輛路徑問(wèn)題一直都是經(jīng)典的問(wèn)題，隨著電子商務(wù)的快速發(fā)展，快遞業(yè)務(wù)也得到了極大的發(fā)展，而快遞的配送是快遞業(yè)務(wù)中極為重要的部分，在滿足客戶的服務(wù)水平的前提下，降低配送成本是各大快遞公司的目標(biāo)，本文考慮了時(shí)間窗約束，以車輛固定成本、運(yùn)輸成本和時(shí)間懲罰成本之和的總成本作為目標(biāo)函數(shù)，在約束條件中加入時(shí)間窗約束，并采用申通快遞（撫州）配送中心和服務(wù)站點(diǎn)的數(shù)據(jù)使用遺傳算法并代入MATLAB求解，結(jié)果表明優(yōu)化后的路徑相比于原路徑降低了16.57%的成本，模型是有效可行的。關(guān)鍵詞：車輛路徑問(wèn)題；時(shí)間窗；快遞配送，遺傳算法目錄1緒論 [12]在研究車輛路徑優(yōu)化問(wèn)題時(shí)，在目標(biāo)函數(shù)里也是考慮了成本最小化，并在約束條件中加入了軟時(shí)間窗約束構(gòu)建模型，并提出相應(yīng)的算法，結(jié)合案例得出使用多車型車輛配送可以降低成本。1.2.3總結(jié)對(duì)以上文獻(xiàn)歸納和分析后進(jìn)行總結(jié)，當(dāng)前國(guó)內(nèi)外對(duì)于車輛路徑優(yōu)化問(wèn)題（VRP）的研究非常豐富，研究方法大多為確定了目標(biāo)函數(shù)和約束條件之后進(jìn)行建模，在引用案例用具體的公司使用模型并用相應(yīng)的算法進(jìn)行求解，得出最優(yōu)路徑達(dá)到降低成本的目標(biāo)，算法有很多種，例如，遺傳算法、蟻群算法等。1.3本文研究?jī)?nèi)容及方法1.3.1研究?jī)?nèi)容圖1.1本文技術(shù)路線圖 圖1.1本文技術(shù)路線圖第一章緒論，主要寫(xiě)了本文的選題背景和研究車輛路徑優(yōu)化問(wèn)題對(duì)于社會(huì)、快遞企業(yè)和客戶的意義，并且查閱了相關(guān)資料，對(duì)目前國(guó)內(nèi)外研究車輛路徑優(yōu)化這一問(wèn)題現(xiàn)狀有了一定的了解，并生成文獻(xiàn)綜述報(bào)告，最后給出本文的研究?jī)?nèi)容和方法。第二章是本篇論文涉及到的基本理論和概念，首先闡述了普通車輛路徑問(wèn)題（VRP）的問(wèn)題描述和組成要素，進(jìn)而引出了帶時(shí)間窗約束的車輛路徑問(wèn)題（VRPTW），并對(duì)該問(wèn)題涉及到的時(shí)間窗類型和目標(biāo)函數(shù)進(jìn)行說(shuō)明，然后對(duì)本論文用到的遺傳算法的基本概念和流程進(jìn)行了闡述。以上三部分的說(shuō)明，為本論文奠定了堅(jiān)實(shí)的理論基礎(chǔ)。第三章申通快遞配送現(xiàn)狀及改進(jìn)方向。首先介紹了申通快遞最近的業(yè)績(jī)情況，并從快遞配送這個(gè)方面分析申通快遞存在的問(wèn)題，然后提供了相應(yīng)的改進(jìn)策略。第四章申通快遞（撫州）案例分析建模。在這章對(duì)本論文選擇的申通快遞（撫州）進(jìn)行分析，并且將該公司案例看做帶時(shí)間窗約束的車輛路徑問(wèn)題（VRPTW），建立相應(yīng)的數(shù)學(xué)模型，在考慮到配送車輛不超載，代理站點(diǎn)服務(wù)時(shí)間窗等約束的條件下，構(gòu)造了以配送成本低化的目標(biāo)函數(shù)，其中包括派遣車輛的固定成本，配送車輛的運(yùn)輸成本和服務(wù)時(shí)間窗的懲罰成本，然后對(duì)遺傳算法相關(guān)參數(shù)進(jìn)行設(shè)置，并使用MATLAB軟件進(jìn)行仿真模擬求解，得出一個(gè)優(yōu)化后的最優(yōu)方案跟最低成本，并把該方案跟原方案進(jìn)行比較，得出該方案確實(shí)可以降低成本，從而驗(yàn)證模型跟算法的有效性和正確性。第五章總結(jié)。總結(jié)該論文內(nèi)容。1.3.2研究方法本輪文在研究車輛路徑優(yōu)化這一問(wèn)題時(shí)主要應(yīng)用了以下方法：文獻(xiàn)閱讀法：在確定論文選題和研究方向之后，使用了文獻(xiàn)閱讀法，去查閱了相關(guān)的期刊文獻(xiàn)資料，對(duì)現(xiàn)在國(guó)內(nèi)外研究車輛路徑優(yōu)化問(wèn)題有了一定的理解，并從中總結(jié)出相應(yīng)的知識(shí)用于本篇論文的撰寫(xiě)。數(shù)學(xué)規(guī)劃法：本文建立了目標(biāo)規(guī)劃數(shù)學(xué)模型，將快遞企業(yè)的決策定位在成本的決策中，并建立成本的目標(biāo)函數(shù)數(shù)學(xué)模型，并在決策變量的選擇設(shè)計(jì)中，采用0-1規(guī)劃的方法進(jìn)行構(gòu)建，來(lái)判斷車輛是否在某兩點(diǎn)之間提供服務(wù)。遺傳算法：本文選擇使用遺傳算法對(duì)建立的車輛路徑優(yōu)化模型進(jìn)行求解，并通過(guò)MATLAB軟件進(jìn)行編程仿真模擬，最終求解出最優(yōu)的配送路徑和最低成本值。2基本理論和概念2.1車輛路徑規(guī)劃問(wèn)題相關(guān)理論2.1.1VRP的相關(guān)概念車輛路徑問(wèn)題是一個(gè)組合最優(yōu)化問(wèn)題，是Dantzig和Ramser在上世紀(jì)五十年代末年提出來(lái)的，是指在配送中心和站點(diǎn)數(shù)量固定，但是各站點(diǎn)的需求量不同時(shí)，配送中心通過(guò)一個(gè)車隊(duì)將需要配送的貨物按時(shí)按量的送到各個(gè)站點(diǎn)，來(lái)滿足所有客戶的需求。而研究VRP問(wèn)題就是需要在滿足客戶服務(wù)水平的基礎(chǔ)上，在配送車輛不超載等一系列的約束條件下，達(dá)到配送總距離最短、配送總時(shí)間最短或者配送總成本最低等一系列目標(biāo)，幫助企業(yè)達(dá)到降低成本進(jìn)而提高核心競(jìng)爭(zhēng)力的效果。并在這里列舉一個(gè)最基本的VRP問(wèn)題，假設(shè)有一個(gè)配送中心，該配送中心配備了K輛車，每輛車都有其各自的容量Q，且該配送中心服務(wù)的客戶數(shù)為N，每個(gè)客戶都有自己的需求量D，一般來(lái)說(shuō)客戶的需求都是不同的。要求所有的配送車輛都從配送中心裝載好貨物后出發(fā)，并且完成配送任務(wù)后需要重新回到配送中心。其他的約束條件有：配送車輛必須滿足所有客戶的需求，并且每個(gè)客戶只能由一輛車提供服務(wù)，每輛車的載重量不能超過(guò)該車的容量限制，在滿足以上條件下，達(dá)到所有配送車輛行駛路程之和最小或者所有車輛配送成本之和最小的目標(biāo)。圖2.1VRP問(wèn)題路徑圖圖2.1VRP問(wèn)題路徑圖2.1.2車輛路徑問(wèn)題的組成要素車輛路徑問(wèn)題的主要構(gòu)成要素有：一個(gè)或多個(gè)配送中心、配送中心配備的用于配送的車輛、配送的貨物、客戶（服務(wù)站點(diǎn)）、目標(biāo)函數(shù)和約束條件。配送中心：配送中心是整個(gè)配送過(guò)程的起點(diǎn)和終點(diǎn)，在這里進(jìn)行分揀和裝卸，并按照客戶的要求進(jìn)行配送。在一個(gè)物流配送系統(tǒng)中，配送中心可以有一個(gè)，也可以有多個(gè)，目的是為了保證可以為所有的客戶提供服務(wù)。可以說(shuō)，配送中心在整個(gè)物流配送系統(tǒng)中是一個(gè)十分關(guān)鍵的要素。配送車輛：配送車輛是一個(gè)配送中心必備的設(shè)備，是整個(gè)物流配送過(guò)程中的主要運(yùn)載工具，在進(jìn)行車輛路徑問(wèn)題的研究中，我們需要考慮到配送車輛很多因素，例如車輛的數(shù)量、容量、速度、油耗成本和使用的固定成本等。配送貨物：貨物是整個(gè)配送過(guò)程中的主體，在研究車輛路徑問(wèn)題時(shí)，需要考慮貨物本身的性質(zhì)和數(shù)量的多少。例如：當(dāng)配送的是生鮮類產(chǎn)品時(shí)，需要考慮到該類產(chǎn)品易腐爛的特性，應(yīng)在溫度不高的時(shí)候盡早配送。而客戶需要的貨物數(shù)量與重量對(duì)配送路徑的規(guī)劃也有影響，當(dāng)客戶的需求較大，一輛配送車輛的載重不夠時(shí)，可以安排多輛車進(jìn)行配送服務(wù)。客戶：客戶在整個(gè)物流配送過(guò)程中也可以稱為配送需求點(diǎn)，在進(jìn)行路徑規(guī)劃的過(guò)程中，需要考慮客戶所在的位置、需求量、服務(wù)時(shí)間窗、客戶滿意度等因素。目標(biāo)函數(shù)：目標(biāo)函數(shù)是進(jìn)行路徑規(guī)劃的歸宿，通常會(huì)用目標(biāo)函數(shù)的最優(yōu)解來(lái)作為整個(gè)問(wèn)題的最優(yōu)決策，在設(shè)置目標(biāo)函數(shù)時(shí)，一般會(huì)考慮以下情況：成本最小化。成本最小化是指完成整個(gè)配送過(guò)程所花費(fèi)的成本最小，成本包括派遣車輛的固定成本和車輛運(yùn)行的運(yùn)輸成本等，在滿足客戶服務(wù)水平的基礎(chǔ)上，成本最小的決策即為整個(gè)決策的最優(yōu)解。成本最小可以幫助企業(yè)降低成本，提高核心競(jìng)爭(zhēng)力。配送時(shí)間最短：如果配送貨物是一些特殊物品，比如生鮮類產(chǎn)品和救災(zāi)應(yīng)急品時(shí)，配送成本也許就沒(méi)有那么重要了，這時(shí)候往往都會(huì)考慮配送時(shí)間最短來(lái)更好的給客戶提供服務(wù)，讓客戶可以盡早的拿到產(chǎn)品，提高客戶對(duì)企業(yè)的滿意度和提升企業(yè)的口碑。多目標(biāo)函數(shù)：顧名思義，就是在構(gòu)建目標(biāo)函數(shù)時(shí)，不僅僅只考慮一個(gè)方面，可以同時(shí)考慮到企業(yè)的成本和客戶的滿意度，比如同時(shí)控制配送成本和配送時(shí)間或者企業(yè)的成本最低和使用的配送車輛最少等等。約束條件：在模型的構(gòu)建過(guò)程中，約束條件是很重要的一個(gè)環(huán)節(jié)，對(duì)于模型的合理性十分重要。一般來(lái)說(shuō)，路徑規(guī)劃問(wèn)題中的約束條件有以下幾個(gè)：配送所需的車輛不超過(guò)配送中心所配備的車輛、配送車輛的載重量不能超過(guò)每輛車規(guī)定的額定容量、配送也不能超時(shí)，配送車輛從配送中心出發(fā)并在完成配送任務(wù)后需要重新回到配送中心等。2.2帶時(shí)間窗約束的車輛路徑問(wèn)題（VRPTW）隨著現(xiàn)在經(jīng)濟(jì)的發(fā)展，人們都在追求更高質(zhì)量的生活，而在物流的方面，很多企業(yè)和客戶也提出了更高的要求，很多客戶不僅要求能盡快的拿到貨物，還要求能在其規(guī)定的時(shí)間內(nèi)得到配送服務(wù)，方面自己能夠進(jìn)行下一步的工作，這就需要引進(jìn)一個(gè)客戶希望得到服務(wù)的時(shí)間窗，時(shí)間窗其實(shí)就是一段時(shí)間，在這個(gè)時(shí)間區(qū)間內(nèi)，左端點(diǎn)是最早服務(wù)時(shí)間，右端點(diǎn)是最晚時(shí)間。在基本的車輛路徑問(wèn)題的基礎(chǔ)上，每個(gè)客戶都加上這個(gè)時(shí)間段約束，要求配送中心必須在這個(gè)時(shí)間段內(nèi)提供服務(wù)，這就產(chǎn)生了VRPTW問(wèn)題。帶時(shí)間窗約束的車輛路徑問(wèn)題是在考慮配送車輛行駛路程最短或者配送成本最小的基礎(chǔ)上，將不同客戶的要求服務(wù)時(shí)間窗也考慮在內(nèi)，并且假設(shè)如果不在這一時(shí)間內(nèi)提供服務(wù)會(huì)產(chǎn)生相應(yīng)的懲罰成本。在現(xiàn)實(shí)生活中，帶時(shí)間窗約束的車輛路徑問(wèn)題的實(shí)用性非常好，在實(shí)際生活應(yīng)用中也很常見(jiàn)，比如郵政信件、申通快遞等。所以，在研究車輛路徑問(wèn)題時(shí)，加入對(duì)客戶服務(wù)時(shí)間窗的考慮非常有必要，因?yàn)橹挥锌紤]了時(shí)間窗約束的車輛路徑問(wèn)題的研究才能適合現(xiàn)在這個(gè)社會(huì)企業(yè)和客戶的需求，而時(shí)間窗約束主要有硬時(shí)間窗約束和軟時(shí)間窗約束兩種。下面我將分別介紹這兩種時(shí)間窗約束，分析他們之間的不同與聯(lián)系。圖2.2硬時(shí)間窗約束成本函數(shù)硬時(shí)間窗約束：硬時(shí)間窗約束是配送車輛只能在這段時(shí)間內(nèi)為客戶提供服務(wù)，如果配送車輛沒(méi)有在這段時(shí)間內(nèi)到達(dá)客戶處提供服務(wù)的話，客戶會(huì)拒絕接受服務(wù)，這樣的話可以認(rèn)為懲罰成本無(wú)限大。其成本函數(shù)如圖2.2圖2.2硬時(shí)間窗約束成本函數(shù)軟時(shí)間窗約束：軟時(shí)間窗約束不會(huì)像硬時(shí)間窗約束那樣嚴(yán)格，軟時(shí)間窗約束時(shí)，配送車輛需要盡量確保在那段時(shí)間到達(dá)，但如果配送車輛由于路上的狀況或者天氣原因沒(méi)有按時(shí)到達(dá)時(shí)，客戶也不會(huì)拒絕接受服務(wù)，只是會(huì)產(chǎn)生相應(yīng)的懲罰成本。如果配送車輛在客戶希望的最早服務(wù)時(shí)間之前就到達(dá)的話，則配送車輛就需要在原地等到客戶希望的最早服務(wù)時(shí)間才能開(kāi)始為客戶提供服務(wù)，而車輛在原地等待的時(shí)間就不能產(chǎn)生收益，則會(huì)產(chǎn)生一定的機(jī)會(huì)成本。倘若配送車輛在客戶希望的最晚服務(wù)時(shí)間之后才到達(dá)客戶點(diǎn)，則客戶會(huì)對(duì)服務(wù)質(zhì)量感到不滿意，也會(huì)產(chǎn)生相應(yīng)的損失。所以，在軟時(shí)間窗約束的車輛路徑規(guī)劃的問(wèn)題中，無(wú)論早到或者晚到都會(huì)產(chǎn)生一定的成本損失。所以需要設(shè)置一個(gè)懲罰成本系數(shù)，而這個(gè)系數(shù)得由客戶對(duì)時(shí)間窗的嚴(yán)格程度來(lái)決定，軟時(shí)間窗約束的成本函數(shù)如圖2.3所示：圖2.3圖2.3軟時(shí)間窗約束成本函數(shù)2.3遺傳算法2.3.1遺傳算法基本思想遺傳算法（GA）最早是在上世紀(jì)七十年代由美國(guó)的Holland提出的，是一種自適應(yīng)的全局概率搜索算法。遺傳算法的基本思想類似于自然界中的基因篩選機(jī)制，用基因來(lái)代表實(shí)際問(wèn)題的解決方案，并對(duì)此進(jìn)行選擇，在眾多的可行方案中選擇其中一個(gè)方案組合，通過(guò)編碼解碼的做法把實(shí)際問(wèn)題轉(zhuǎn)換為基因，并且用來(lái)表示不同實(shí)際問(wèn)題的每個(gè)基因都是不同的，帶有自己的特征。染色體是由幾個(gè)不同的基因片段排列在一起形成的。據(jù)此遺傳算法的思路可以表述為:種群中存在著許多不同的染色體，每條染色體代表的是可行方案，通過(guò)計(jì)算每條染色體的目標(biāo)值，從而篩選出里面基因較好的染色體，并對(duì)篩選出的染色體進(jìn)行一系列的操作，例如遺傳交叉、變異操作等，使其產(chǎn)生具有不同基因片段的新的染色體組成其子代染色體。子代染色體不僅保留了父代染色體的優(yōu)質(zhì)基因，而且適應(yīng)度值有所提升。循環(huán)進(jìn)行此操作直至解出符合條件的最優(yōu)解。遺傳算法主要思路來(lái)源于自然界的生物進(jìn)化理論，模擬基因的遺傳機(jī)制，形成并不斷完善出一種可以用來(lái)求解實(shí)際生活中比較復(fù)雜的極值問(wèn)題的進(jìn)化算法，具有嚴(yán)謹(jǐn)?shù)目茖W(xué)性和廣泛的實(shí)用性。2.3.2遺傳算法的相關(guān)概念a.染色體染色體是我們?cè)诟咧猩飳W(xué)中學(xué)過(guò)的基本概念，它是由由基因組成的，在遺傳算法中一般是由字符串表示的，因?yàn)閷?shí)際問(wèn)題的不同，所以表達(dá)染色體的方法也有很多很多。b.編碼與解碼編碼過(guò)程和解碼過(guò)程是兩個(gè)對(duì)立相反的過(guò)程，由于遺傳空間中只能解決遺傳問(wèn)題，不能直接用實(shí)際問(wèn)題在遺傳空間表示，因此需要在遺傳空間中把實(shí)際問(wèn)題表現(xiàn)出來(lái)，這就是編碼的過(guò)程，而解碼則是跟編碼對(duì)立的過(guò)程，我們?cè)谶z傳空間中解決實(shí)際問(wèn)題后，還需要將經(jīng)過(guò)處理后的問(wèn)題返回映射到實(shí)際問(wèn)題，求出實(shí)際問(wèn)題的近似最優(yōu)解，解決實(shí)際問(wèn)題。c.種群與種群規(guī)模種群也是生物學(xué)概念，種群是個(gè)體的集合，一個(gè)種群是由很多有不同特征的個(gè)體組成的。在使用遺傳算法求解時(shí)，初始解開(kāi)始迭代并且會(huì)產(chǎn)生新的解集，而新的解集就會(huì)和初始解組成一個(gè)新的種群。而種群規(guī)模指的是種群中個(gè)體數(shù)量的多少。種群規(guī)模可大可小，都有其各自的優(yōu)缺點(diǎn)，當(dāng)種群規(guī)模大時(shí)，多樣性高但是在進(jìn)行運(yùn)算時(shí)速度較慢；當(dāng)種群規(guī)模小時(shí)，運(yùn)算速度很快，但是多樣性低，并且求解出來(lái)的結(jié)果可能只是局部最優(yōu)解而不是真正的整體最優(yōu)解。d.適應(yīng)度在生物學(xué)中，適應(yīng)度使一種用來(lái)表示生物對(duì)外界環(huán)境適應(yīng)程度的術(shù)語(yǔ)，由于遺傳算法的依據(jù)是達(dá)爾文的生物進(jìn)化論，所以也引進(jìn)了這個(gè)術(shù)語(yǔ)來(lái)衡量迭代過(guò)程中產(chǎn)生的新種群是否能夠幫助我們找到最優(yōu)解。而在遺傳算法中，衡量適應(yīng)程度的函數(shù)就叫做適應(yīng)度函數(shù)。e.遺傳算子遺傳算子作用于種群里面的個(gè)體，從而產(chǎn)生下一代，然后下一代按照進(jìn)化論中適者生存的原則進(jìn)行進(jìn)化。遺傳算子是遺傳算法與其他算法不同的關(guān)鍵，遺傳算法就是通過(guò)遺傳算子不斷搜索來(lái)接近近似最優(yōu)解的，遺傳算子包括：選擇算子、交叉算子和變異算子。2.3.3遺傳算法的特點(diǎn)遺傳算法的主要思路主要來(lái)源于自然界中的生物進(jìn)化論和生物基因遺傳法則，跟以往的傳統(tǒng)算法跟枚舉法等算法相比，有以下特點(diǎn)：初始種群對(duì)遺傳算法最優(yōu)解的影響較小，無(wú)論采用什么樣的初始種群，都可以經(jīng)過(guò)一系列的操作，最終獲得質(zhì)量不斷得到優(yōu)化的解。算法更加智能，遺傳算法在解決實(shí)際問(wèn)題時(shí)，不需要考慮所有的細(xì)節(jié)，算法本身具有很強(qiáng)的適應(yīng)性，可以很好地解決問(wèn)題。應(yīng)用范圍廣，實(shí)際生活中的絕大多數(shù)問(wèn)題都可以通過(guò)遺傳算法得到最優(yōu)解，經(jīng)常被用在各大領(lǐng)域。對(duì)適應(yīng)度函數(shù)的要求較低，在遺傳算法中，適應(yīng)度函數(shù)不是一定要連續(xù)可微的，而且定義域也可以任意設(shè)定，這就擴(kuò)大了遺傳算法在實(shí)際問(wèn)題中的適用領(lǐng)域。遺傳算法并不是使用確定性的原則來(lái)搜尋優(yōu)化方案，而是通過(guò)選擇算子、交叉算子和變異算子三種遺傳算子按照概率規(guī)則來(lái)進(jìn)行搜尋的。2.3.4遺傳算法求解步驟和過(guò)程遺傳算法的求解過(guò)程是經(jīng)典的迭代過(guò)程，其求解的具體步驟如下：根據(jù)實(shí)際問(wèn)題，構(gòu)造出合適的染色體（個(gè)體）隨機(jī)產(chǎn)生初始種群適應(yīng)度函數(shù)的設(shè)計(jì)，數(shù)值越小，適應(yīng)度越大，且適應(yīng)度是衡量染色體接近最優(yōu)方案的指標(biāo)遺傳操作設(shè)計(jì)，利用選擇、交叉、變異三種算子產(chǎn)生后代設(shè)計(jì)算法規(guī)模控制參數(shù)，例如交叉概率和迭代次數(shù)上限等圖2.3遺傳算法流程圖圖2.3遺傳算法流程圖3申通快遞配送現(xiàn)狀及改進(jìn)方向3.1公司簡(jiǎn)介及現(xiàn)狀表3.1申通快遞業(yè)績(jī)表申通快遞是一家以快遞業(yè)務(wù)為主的企業(yè)，目前申通快遞的業(yè)務(wù)基本覆蓋了全中國(guó)的市區(qū)縣級(jí)城市，甚至在東部一些經(jīng)濟(jì)發(fā)達(dá)地區(qū)實(shí)現(xiàn)了無(wú)盲區(qū)配送。申通快遞在2015年成功上市，并在2019與2020年中國(guó)民營(yíng)企業(yè)500強(qiáng)榜單中占據(jù)一席之地，由此申通快遞也被稱為中國(guó)快遞三通一達(dá)之一。但這都是過(guò)去取得的成績(jī)，2021年4月15日申通快遞發(fā)布了2020年度業(yè)績(jī)快報(bào)。快報(bào)具體內(nèi)容見(jiàn)表3.1表3.1申通快遞業(yè)績(jī)表從上表我們可以看出，申通快遞在2020年的收入和利潤(rùn)等方面跟2019年相比都出現(xiàn)了較大幅度的下降，面對(duì)這樣較為慘淡的業(yè)績(jī)，申通快遞也表示是由于市場(chǎng)競(jìng)爭(zhēng)激烈，市場(chǎng)價(jià)格出現(xiàn)大幅度下降，并且公司將采取相應(yīng)的措施來(lái)解決這一問(wèn)題。當(dāng)然，造成申通快遞的業(yè)績(jī)下降肯定有很多方面的原因，這里我僅就申通快遞（撫州）分公司在配送方面的現(xiàn)狀問(wèn)題進(jìn)行指出和改進(jìn)的方法。3.2公司配送現(xiàn)狀眾所周知，申通快遞主要通過(guò)連鎖加盟的方式來(lái)擴(kuò)大自己的市場(chǎng)份額，各加盟店對(duì)上海總部繳納一定的加盟費(fèi)，總部就對(duì)各加盟店進(jìn)行授權(quán)并進(jìn)行指導(dǎo)。這樣由于各加盟店之間沒(méi)有合作的關(guān)系，大多數(shù)都只會(huì)關(guān)注于自身的利益，而不會(huì)顧全整個(gè)公司的利益；而且各加盟店的資金和技術(shù)參差不齊，很難對(duì)所有客戶都提供很好的服務(wù)，對(duì)公司的口碑也會(huì)有影響。圖3.2申通快遞流程本論文以申通快遞（撫州）分公司為案例進(jìn)行其車輛路徑優(yōu)化，以一名黎川客戶在淘寶購(gòu)買(mǎi)商品為例，介紹申通快遞（撫州）分公司的配送現(xiàn)狀和流程，具體流程見(jiàn)圖3.2.圖3.2申通快遞流程從以上流程可以看出，當(dāng)快遞從南昌集散中心發(fā)到位于撫州宜黃的配送中心時(shí)，配送中心的配送工作也就要開(kāi)始了，該配送中心服務(wù)的站點(diǎn)有包括黎川在內(nèi)的十個(gè)區(qū)縣級(jí)站點(diǎn)，而如上文提到的，申通快遞采取的是加盟式的，所以這十個(gè)站點(diǎn)都只會(huì)顧及自己的利益，希望配送中心盡早的將屬于自己這塊區(qū)域客戶的快遞送至倉(cāng)庫(kù)，以便自己可以盡快的安排配送至驛站，使客戶能夠最快的拿到自己的快遞，從而提高客戶的滿意度，讓客戶下次還能接著選擇申通快遞，提升企業(yè)的口碑，可配送中心當(dāng)然不可能同時(shí)滿足所有加盟站點(diǎn)的愿想，配送中心站在自身的角度來(lái)說(shuō)，肯定希望自己在滿足將所有站點(diǎn)的快遞送達(dá)的情況下，整體的配送成本最小，這就需要代理站點(diǎn)也站在整體的角度，因?yàn)檎军c(diǎn)之間的距離也不是很遠(yuǎn)，先配送其他站點(diǎn)的快遞，再配送本站點(diǎn)的快遞，其實(shí)之間也不會(huì)相差太多的時(shí)間，所以各站點(diǎn)之間也需要相互理解，這樣才可以達(dá)到整體最優(yōu)的結(jié)果。而當(dāng)快遞到達(dá)黎川申通快遞倉(cāng)庫(kù)時(shí)，站點(diǎn)的配送工作就開(kāi)始了，倉(cāng)庫(kù)人員需要將所有的快遞按照客戶地址的不同，以驛站的地址進(jìn)行分揀，讓所有的快遞都能被配送到離客戶最近的驛站，而有時(shí)候可能會(huì)由于分揀人員的失誤而將快遞配送到離客戶較遠(yuǎn)的驛站，給客戶取件帶來(lái)不便。而在最終的配送過(guò)程中，可能會(huì)由于快遞員業(yè)務(wù)水平的不足，在配送途中出現(xiàn)快遞丟失或者破損的情況。3.3解決策略針對(duì)配送中心配送環(huán)節(jié)出現(xiàn)的問(wèn)題，申通快遞已經(jīng)采取了相應(yīng)的措施，申通一直都在推行直營(yíng)化管理，希望能夠提高直營(yíng)化子公司的比例，一直在收購(gòu)非直營(yíng)的的配送中心和網(wǎng)點(diǎn)，打造規(guī)范標(biāo)準(zhǔn)的子公司便于根據(jù)不同地區(qū)的情況因地制宜的制定發(fā)展計(jì)劃，但由于專業(yè)型人才較為缺乏，省區(qū)的執(zhí)行力度還不夠，所以這項(xiàng)舉措還沒(méi)有取得什么實(shí)際性的進(jìn)展。我認(rèn)為，申通快遞應(yīng)該加強(qiáng)這種直營(yíng)化管理，首先：申通快遞應(yīng)該堅(jiān)決收購(gòu)非直營(yíng)的配送中心和網(wǎng)點(diǎn)，建立以省區(qū)為單位的子公司，并且對(duì)所以子公司進(jìn)行績(jī)效考核，刺激子公司的發(fā)展，提高業(yè)務(wù)額。其次，可以鼓勵(lì)加盟網(wǎng)點(diǎn)在上級(jí)配送中心的持有股份，這樣加盟商的利益就跟配送中心的利益聯(lián)系在一起了，這樣配送中心在向各個(gè)站點(diǎn)配送時(shí)就可以考慮整體的利益，來(lái)降低總成本。針對(duì)站點(diǎn)最終的配送環(huán)節(jié)的問(wèn)題，省區(qū)的子公司成立后，可以用直營(yíng)化的方式管理各個(gè)加盟網(wǎng)點(diǎn)，對(duì)參加配送工作的快遞員進(jìn)行統(tǒng)一培訓(xùn)，規(guī)范他們的作業(yè)過(guò)程，提高所有快遞員的專業(yè)水平，盡可能的確保所有參與最終配送的快遞員的業(yè)務(wù)水平合格，滿足客戶的需求，給企業(yè)樹(shù)立好的口碑。4帶時(shí)間窗的車輛路規(guī)劃研究——以申通快遞（撫州）為例4.1問(wèn)題的提出申通快遞在撫州市內(nèi)有1個(gè)配送中心，10個(gè)縣級(jí)代理站點(diǎn)。配送中心每天需要對(duì)快遞按照不同代理站點(diǎn)進(jìn)行分揀裝車，并通過(guò)配送貨車將所有快遞準(zhǔn)確無(wú)誤的送到相應(yīng)的代理站點(diǎn)的倉(cāng)庫(kù)，代理站點(diǎn)再對(duì)快遞進(jìn)行二次分揀，分配給分布在縣城內(nèi)部的網(wǎng)點(diǎn)，最后通知客戶盡快來(lái)網(wǎng)點(diǎn)取自己的快遞。為了節(jié)省物流配送成本，需要對(duì)配送中心到各個(gè)代理站點(diǎn)的路徑進(jìn)行設(shè)計(jì)，由于每個(gè)代理站點(diǎn)的接受服務(wù)的時(shí)間有限制且都有差別，所以可以看成這是一個(gè)帶時(shí)間窗約束的車輛路徑問(wèn)題（VRPTW）。圖4.1是配送中心和及各個(gè)代理站點(diǎn)的地圖，表4.1是配送中心及各個(gè)代理站點(diǎn)的地址，表4.2是配送站點(diǎn)及各個(gè)代理站點(diǎn)的經(jīng)緯度坐標(biāo)及每天的快件量（單位件），表4.3是10個(gè)代理站點(diǎn)的最早和最晚服務(wù)時(shí)間和相應(yīng)的服務(wù)時(shí)長(zhǎng)（以早上八點(diǎn)為基準(zhǔn)，單位分鐘），表4.4是距離矩陣，顯示了配送中心到各個(gè)站點(diǎn)之間的距離和各個(gè)站點(diǎn)之間的距離（單位千米）。圖4.1圖4.1配送中心及站點(diǎn)地圖 表4.1配送中心及站點(diǎn)地址編號(hào)地址0撫州市宜黃縣解放大道69號(hào)1撫州市東鄉(xiāng)區(qū)環(huán)城西路一號(hào)車庫(kù)養(yǎng)護(hù)中心旁2撫州市樂(lè)安縣前坪工業(yè)園區(qū)內(nèi)橫三路3撫州市崇仁縣人民大道86號(hào)4撫州市金溪縣錦繡華城1號(hào)樓5號(hào)5撫州市臨川區(qū)園橫4路6撫州市南城縣交通路199號(hào)7撫州市廣昌縣中央公司6號(hào)8撫州市黎川縣京川大道166號(hào)9撫州市資溪縣建設(shè)中路47號(hào)10撫州市南豐縣竹馬路58號(hào)表4.2經(jīng)緯度坐標(biāo)及需求量（單位件）序號(hào)經(jīng)度緯度快件量0116.23591427.56049601116.59068428.24225110402115.84181327.4263349203116.08117827.7698718104116.80636227.9469896805116.32561527.94538214006116.6527227.572177507116.35864526.8419816208116.91227127.2895826109117.09913627.72758756010116.53813527.214566700表4.3服務(wù)時(shí)間窗及服務(wù)時(shí)長(zhǎng)（以早上8點(diǎn)為基準(zhǔn)）編號(hào)最早服務(wù)時(shí)間最晚服務(wù)時(shí)間服務(wù)時(shí)長(zhǎng)（分鐘）00（8點(diǎn)）0（8點(diǎn)）10190（9點(diǎn)30）120（10點(diǎn)）10245（8點(diǎn)45）75（9點(diǎn)15）10330（8點(diǎn)30）60（9點(diǎn)）10460（9點(diǎn)）90（9點(diǎn)30）10555（8點(diǎn)55）85（9點(diǎn)25）10650（8點(diǎn)50）80（9點(diǎn)20）10790（9點(diǎn)30）120（10點(diǎn)）10865（9點(diǎn)05）95（9點(diǎn)35）109100（9點(diǎn)40）130（10點(diǎn)10）101060（9點(diǎn)）90（9點(diǎn)30）10表4.4距離矩陣（單位千米）編號(hào)0123456789100083.441.627.870.743.741.180.873.28748.7183.40116.872.539.14274.8157.4110.175.9114.4241.6116.8044.9111.274.881.682.7106.9128.372.7327.872.544.90743160.4106.897.8100.376.4470.739.1111.274047.244.3130.673.837.785.6543.74274.83147.2052.512.2793.179.883.9641.174.881.660.444.352.5086.240.147.241.3780.8157.482.7106.8130.612.2786.2074123.745.1873.2110.1106.997.873.893.140.174052.137.998775.9128.3100.337.779.847.2123.752.1079.51048.7114.472.776.485.683.941.345.137.979.50表4.5模型數(shù)據(jù)站點(diǎn)數(shù)10每輛配送車的固定成本150單位運(yùn)行距離成本3元/公里每輛配送車的載重快件量3000件車速60公里/小時(shí)早到懲罰成本系數(shù)30元/小時(shí)遲到懲罰成本系數(shù)60元/小時(shí)配送車輛數(shù)34.2建模4.2.1模型假設(shè)條件為了申通快遞（撫州）案例的帶時(shí)間窗約束的車輛路徑問(wèn)題為數(shù)學(xué)模型，本論文確定了一些模型基本假設(shè)條件：只有一個(gè)配送中心，且配送車輛必須在配送中心裝載好快遞后出發(fā)，并完成配送任務(wù)后在規(guī)定時(shí)間內(nèi)返回配送中心。每輛車的載重量至少可以服務(wù)一個(gè)代理站點(diǎn)。每個(gè)代理站點(diǎn)只能由一輛配送車輛服務(wù)。每輛配送車輛只能服務(wù)一條路徑，不能重復(fù)。每個(gè)站點(diǎn)都規(guī)定了自己希望接受服務(wù)的時(shí)間窗，配送車輛應(yīng)盡量在該時(shí)間窗內(nèi)到達(dá)站點(diǎn)。所有配送車輛的載重量不能超過(guò)車輛的額定載重量。4.2.2模型變量與參數(shù)定義現(xiàn)在對(duì)本論文模型所需的變量和參數(shù)進(jìn)行如下定義。N:本案例中配送中心需要服務(wù)的代理站點(diǎn)數(shù)；i,j:站點(diǎn)i或者j，其中i,j=0,1?Ni,j=0表示配送中心k:配送中心配備的配送車輛的編號(hào)k=1,2?KQ：配送車輛的額定載重量α：派遣每輛車輛的固定成本β：配送車輛行駛單位距離的運(yùn)輸成本cij：配送車輛從站點(diǎn)i行駛到站點(diǎn)j的距離，其中di：站點(diǎn)i的快件量，其中eilisitij:配送車輛從站點(diǎn)i行駛到站點(diǎn)j所需要的時(shí)間，其中uiviT0Tsm：配送車輛在站點(diǎn)規(guī)定的最早服務(wù)時(shí)間之前到達(dá)的單位時(shí)間機(jī)會(huì)成本n：配送車輛在站點(diǎn)規(guī)定的最晚服務(wù)時(shí)間之后到達(dá)的單位時(shí)間懲罰成本其中決策變量xijkx4.2.3目標(biāo)函數(shù)的構(gòu)造本篇論文在構(gòu)造目標(biāo)函數(shù)時(shí)，以配送總成本最小化為目標(biāo)，其中包括派遣車輛的固定成本、車輛進(jìn)行配送的運(yùn)輸成本和時(shí)間窗懲罰成本。（1）派遣車輛的固定成本：車輛的固定成本主要由車輛的日常費(fèi)用組成，其中包括車輛的維修費(fèi)，保養(yǎng)費(fèi)和折舊費(fèi)等費(fèi)用。由于這部分成本一般來(lái)說(shuō)不會(huì)隨行駛距離的改變而變化，所以在本文中設(shè)為常數(shù)，且只跟派遣車輛的數(shù)量有關(guān)。成本如下：Cf=α∑kCfK：配送中心此次任務(wù)派遣的車輛數(shù)j：配送中心此次服務(wù)的站點(diǎn)數(shù)（2）車輛的運(yùn)輸成本：車輛的運(yùn)輸成本及車輛在運(yùn)輸過(guò)程中的變化成本，為了方便后續(xù)模型的建立，在本論文中將配送車輛在運(yùn)輸過(guò)程中的行駛設(shè)定為以每小時(shí)60千米的速度勻速行駛，并且認(rèn)為運(yùn)輸成本只跟車輛行駛的距離有關(guān)。成本如下：Ct=β∑k=1KCt：車輛的運(yùn)輸成本cij（3）時(shí)間窗懲罰成本：本篇論文假設(shè)時(shí)間窗的懲罰成本與配送車輛不在站點(diǎn)時(shí)間窗之內(nèi)到達(dá)的時(shí)間呈線性關(guān)系，懲罰成本隨著時(shí)間線性增長(zhǎng)，在對(duì)懲罰成本函數(shù)定義之前，也需要做出以下假設(shè)：（1）懲罰成本需要用線性函數(shù)表示（2）當(dāng)配送車輛在站點(diǎn)規(guī)定的時(shí)間窗內(nèi)提供服務(wù)時(shí)，不會(huì)產(chǎn)生懲罰成本。（3）無(wú)論配送車輛是在站點(diǎn)規(guī)定的服務(wù)時(shí)間窗之前還是之后到達(dá)，懲罰成本都會(huì)隨著違反時(shí)間長(zhǎng)度線性增加。（4）站點(diǎn)規(guī)定的服務(wù)時(shí)間窗越短，其懲罰成本的邊際作用越大。基于以上假設(shè)，本論文定義的懲罰函數(shù)表達(dá)式如下：Pisi=假如配送車輛k在站點(diǎn)i規(guī)定的最早服務(wù)時(shí)間之前到達(dá)，則該車輛需要在站點(diǎn)i處等到最早服務(wù)時(shí)間在提供服務(wù)，在等待時(shí)會(huì)產(chǎn)生機(jī)會(huì)成本mei?siPisi=mmax?4.2.4數(shù)學(xué)模型綜合以上分析，建立以總成本最小的目標(biāo)函數(shù)，建立的數(shù)學(xué)模型如下：minF(i,j,約束條件如下：∑k=1K?∑j∑j=1N?X0jk=∑k=1K?∑j=1N?∑k=1K?∑i=0N?∑i=0N?∑j=0T0k+∑k=1K?xijk∈0,1i,j∈1,2?NPisi=mmax上述式子含義如下：式（4-5）為目標(biāo)函數(shù)，以最小成本為目標(biāo)，其中包括派遣車輛的固定成本、車輛行駛過(guò)程中的運(yùn)輸成本和時(shí)間窗懲罰成本。約束條件（4-6）表示用來(lái)執(zhí)行配送任務(wù)的車輛數(shù)不能超過(guò)配送中心所配備的車輛數(shù)，（4-7）表示車輛得從配送中心出發(fā)，最終得回到配送中心，（4-8）和（4-9）表示一個(gè)代理站點(diǎn)只能由一輛車提供服務(wù)，（4-10）表示任何配送車輛所執(zhí)行的配送任務(wù)量不能超過(guò)它的額定最大載重量，（4-11）表示配送車輛完成任務(wù)時(shí)得在規(guī)定的時(shí)間內(nèi)返回配送中心，（4-12）表示配送車輛從站點(diǎn)i行駛到站點(diǎn)j的時(shí)間約束，（4-13）表示整數(shù)約束，限制xijk的取值只能是0或者1。（4-144.3最優(yōu)路徑及最低成本本文遺傳算法的各參數(shù)選擇是根據(jù)相關(guān)文獻(xiàn)確定的，其中交叉概率為0.8，變異概率為0.10，種群規(guī)模為200，染色體長(zhǎng)度為13，終止進(jìn)化代數(shù)為200。基于本案例中的數(shù)據(jù)和相應(yīng)參數(shù)設(shè)置，在MATLAB軟件中運(yùn)行出的最優(yōu)結(jié)果是10-8-9-6-0-3-1-4-0-2-7-5-0如下圖4.2所示。配送車輛一路徑：配送中心0-站點(diǎn)10-站點(diǎn)8-站點(diǎn)9-站點(diǎn)6-配送中心0配送車輛二路徑：配送中心0-站點(diǎn)3-站點(diǎn)1-站點(diǎn)4-配送中心0圖4.2路徑圖圖4.2路徑圖從配送路徑圖以及前面所列數(shù)據(jù)可以得知以下信息：車輛一的配送路徑為0-10-8-9-6-0，行駛距離為227千米，運(yùn)載快件量為2620件，車輛滿載率為87.33%，到達(dá)各站點(diǎn)時(shí)間依次為0-0.81167-1.61-2.645-3.5983-4.45（單位小時(shí)）。車輛二的配送路徑為0-3-1-4-0，行駛距離為210.1千米，運(yùn)載快件量為2530件，車輛滿載率為84.33%，到達(dá)各站點(diǎn)時(shí)間依次為0-0.46333-1.8383-2.6567-4.002（單位小時(shí)）。第三輛車的配送路徑為0-2-7-5-0，行駛距離為180.27千米，運(yùn)載快件量為2940件，車輛滿載率為98.00%，到達(dá)各站點(diǎn)時(shí)間依次為：0-0.69333-2.2383-2.6095-3.5048（單位小時(shí)）。圖4.3迭代圖圖4.3迭代圖從運(yùn)行結(jié)果可以看出，配送總成本為2632.03元，其中派遣車輛固定成本為450元，運(yùn)輸成本為1852.11元，時(shí)間窗懲罰成本為329.92元，其中各配送車輛路線成本見(jiàn)表4.6：表4.6優(yōu)化方案各車輛具體成本車輛編號(hào)固定成本運(yùn)輸成本時(shí)間窗懲罰成本總成本（元）1150681171.85791002.85792150630.370.503850.8033150540.8187.55778.364.4結(jié)果對(duì)比現(xiàn)列出該公司原方案，對(duì)比現(xiàn)方案與原方案成本，來(lái)驗(yàn)證模型是否可行有效。4.4.1原方案（1）第一輛車路徑為0-1-5-0，行駛距離為169.1千米，快件量為2440件，車輛滿載率為81.33%（2）第二輛車路徑為0-2-3-4-9-0，行駛距離為285.2千米，快件量為2970件，車輛滿載率為99%（3）第三輛車路徑為0-7-10-8-6-0，行駛距離為245千米，快件量為2680件，車輛滿載率為89.33%，各車輛在配送過(guò)程中的成本如下表4.7表4.7原方案各車輛具體成本車輛編號(hào)固定成本運(yùn)輸成本時(shí)間窗懲罰成本總成本（元）1150507.353.72711.022150855.6227.0031232.6033150735325.6881210.688結(jié)合上表計(jì)算可知原方案總成本為711.02+1232.603+1210.688=3154.311元。4.4.2方案對(duì)比圖表4.8方案對(duì)比成本類別原方案優(yōu)化方案節(jié)約的成本車輛固定成本4504500運(yùn)輸成本2097.91852.11245.79懲罰成本606.411329.92276.491總成本3154.3112632.03522.281從上表的方案對(duì)比我們可以看出，使用遺傳算法求解出來(lái)的最優(yōu)方案跟現(xiàn)方案對(duì)比，固定成本沒(méi)有改變，但是運(yùn)輸成本和懲罰成本都有所降低，最終的總成本降低了522.281元，節(jié)省了16.57%的成本，證明本文所優(yōu)化的模型是可行有效的。5總結(jié)本論文首先介紹了選題的背景和研究的意義，然后通過(guò)查閱相關(guān)文獻(xiàn)資料了解到國(guó)內(nèi)外目前對(duì)于車輛路徑問(wèn)題的研究現(xiàn)狀，在對(duì)所查閱文獻(xiàn)總結(jié)之后，明確了本論文的研究?jī)?nèi)容跟研究方法，然后就介紹了車輛路徑問(wèn)題的相關(guān)理論知識(shí)和相關(guān)因素以及遺傳算法的基本理論。其次，分析了本論文所選案例申通快遞公司的基本情況和造成這些情況的基本原因和解決策略，接著按照案例實(shí)際情況，建立相應(yīng)的數(shù)學(xué)模型，并采用上文提及的遺傳算法，代入MA