2022西北大學(xué)數(shù)學(xué)建模競(jìng)賽(陳思李瑤張瑜)

2022西北大學(xué)數(shù)學(xué)建模競(jìng)賽（陳思李瑤張瑜）物資配送路徑問題的研究摘要本文建立了物資配送路線最優(yōu)解問題的數(shù)學(xué)模型，應(yīng)用C++軟件解決模型問題，結(jié)合森林救火模型與遺傳模型，求解該數(shù)學(xué)模型的算法。該模型就實(shí)際問題給出一個(gè)合理的優(yōu)化路線，在需求量、接貨時(shí)間段、各種費(fèi)用消耗已知的情況下，引入0-1變量，建立各個(gè)約束條件，包括車輛的容量限制，到達(dá)每個(gè)客戶的車輛和離開每個(gè)客戶的車輛均為1的限制，總車輛數(shù)的限制，目標(biāo)函數(shù)為費(fèi)用的最小化，費(fèi)用包括車輛的行駛費(fèi)用，車輛早到或晚到造成的損失，最后求出最優(yōu)解的近似解，對(duì)于初始數(shù)據(jù)的選取采用帶限制條件的隨機(jī)組合的方法，使模型的求解具有普遍性，這樣模型才會(huì)有具有可信度。本文提出的算法求解不需要像枚舉法那樣麻煩，它的高效性、普遍性是無可厚非的。該模型用C++計(jì)算出的結(jié)果為：路線一：0、6、4、0；路線二：0、3、1、2、0路線三：0、8、5、7、0目標(biāo)函數(shù)總成本為910關(guān)鍵字：物資配送問題、車輛路徑、最優(yōu)解、森林救火模型、遺傳算法一、問題重述某物流中心擁有一支貨運(yùn)車隊(duì)，每臺(tái)貨運(yùn)車輛的載重量（噸）相同、平均速度（千米/小時(shí)）相同，該物流中心用這樣的車為若干個(gè)客戶配送物資，物流中心與客戶以及客戶與客戶之間的公路里程（千米）為已知。每天，各客戶所需物資的重量（噸）均已知，并且每個(gè)客戶所需物資的重量都小于一臺(tái)貨運(yùn)車輛的載重量，所有送貨車輛都從物流中心出發(fā)，最后回到物流中心，車輛必須在一定時(shí)間范圍內(nèi)到達(dá)，早于或晚于到達(dá)會(huì)受到相應(yīng)的懲罰，要求此配送方案是配送費(fèi)用最少的。1.建立送貨車輛每天總運(yùn)行里程最短的一般數(shù)學(xué)模型，并給出求解方法。2.具體求解以下算例，并給出你們實(shí)際使用的軟件名稱、命令和編寫的全部計(jì)算機(jī)源程序。qi噸（qiQs），在第i個(gè)客戶處卸貨時(shí)間為i小時(shí)，第i個(gè)客戶要求送貨車輛到達(dá)的時(shí)間范圍ai,bi給出。物流中心與各客戶以及各客戶間的公路里程（單位：千米）由表2給出。問當(dāng)日如何安排送貨車輛（包括出動(dòng)車輛的臺(tái)數(shù)以及每一臺(tái)車輛的具體行駛路徑）才能使總運(yùn)行里程最短。二、問題分析物流中心呢，有一個(gè)，同時(shí)有八個(gè)客戶需要該物資，每個(gè)客戶的需求量都不超過車的最大承載量，貨運(yùn)車隊(duì)到每個(gè)客戶點(diǎn)都有一定的卸載停留時(shí)間，同時(shí)，每個(gè)客戶都有他的要求車輛到達(dá)時(shí)間范圍，每輛車的最大載重量為8噸，平均速率為50千米/小時(shí)，現(xiàn)在要做的就是如何在等待損失最小的情況下，使配送費(fèi)用最小。本題主要是研究使派送費(fèi)用最小的車輛行駛路徑問題。車輛行駛派送的費(fèi)用主要包括運(yùn)輸成本、車輛在客戶要求到達(dá)時(shí)間之前到達(dá)產(chǎn)生的等待損失和車輛在客戶要求到達(dá)時(shí)間之后到達(dá)所受懲罰等等。為滿足派送費(fèi)用最小的需求，即要使所選行車路徑產(chǎn)生的總費(fèi)用最小，從而確定出最佳的車輛派送方案?？蛻鬷的貨物需求量Di固定時(shí)，首先，我們根據(jù)題意，取若干輛車進(jìn)行送貨，然后，主要考慮每輛車各負(fù)責(zé)哪些客戶的送貨任務(wù)，我們可以給出滿足題中限制條件的很多參考方案供選用，并考慮以所選行車路徑產(chǎn)生的總費(fèi)用最小為目標(biāo)的情況下，建立最優(yōu)化模型確定最佳的車輛派送方案。三、基本假設(shè)A、客戶的需求量已知；B、每個(gè)車輛的容量都一樣，且都已知；C、每個(gè)客戶站點(diǎn)僅允許一輛車經(jīng)過一次并配送貨物；D、車輛的載貨量不允許超過車輛的最大載貨量；E、站點(diǎn)和客戶的相對(duì)位置坐標(biāo)已知；F、每輛車都從物流中心出發(fā)最后回到物流中心；G、配送中心有足夠的資源以供配送；H、物流中心的車輛總數(shù)大于或等于當(dāng)派送路程最小時(shí)所需的車輛數(shù);I、每輛車送貨時(shí)行駛的路程不超過它所能行駛的最遠(yuǎn)路程；G、每個(gè)客戶要求車輛到達(dá)的時(shí)間范圍已知。四、符號(hào)說明I、n：客戶或站點(diǎn)的集合其中i、j分別為兩相鄰站點(diǎn)的集合2、k：車輛的集合3、q：車輛額定載貨量4、Mij:從i到j(luò)的運(yùn)輸成本；5、Di：客戶需求量；6、Tijk:車輛到達(dá)客戶站點(diǎn)的時(shí)間，要求盡量落在【ai，bi】?jī)?nèi)；7、Xijk8、Yijk：9、f：車輛遲到單位時(shí)間應(yīng)承擔(dān)的懲罰；10、t車輛早到單位時(shí)間產(chǎn)生的等待損失；11、C運(yùn)送貨物產(chǎn)生的總損失；12、Ui：車輛在第i個(gè)客戶站點(diǎn)等待的時(shí)間；13、Vi：車輛在第i個(gè)客戶站點(diǎn)遲到的時(shí)間；14、G：車輛行駛單位距離的運(yùn)輸成本；15、S：車輛行駛的路程。五、模型建立與分析確定約束條件minC二Mij+f+t②DiWqaiWTijkWbi④Xijk=1⑤Yijk=1模型建立：本模型思路如下：I、每條路線客戶總需求必須小于等于運(yùn)輸車最大裝載量；II、每個(gè)客戶都必須且只能由一輛車運(yùn)輸貨物；III、每輛車運(yùn)輸?shù)娇蛻粽军c(diǎn)的時(shí)間應(yīng)盡量在客戶要求時(shí)間范圍內(nèi)；由以上分析可以得到很多組解，但我們使用最優(yōu)解來逼近真實(shí)解。模型圖解如下：模型分析I、車輛數(shù)目的確定：根據(jù)問題要求已知客戶總需求量為2+1.5+4.5+3+1.5+4+2.5+3=21，再根據(jù)客戶所需到貨時(shí)間段和客戶離物流中心距離可以推算出3輛車比較合理，并且滿足配送費(fèi)用及運(yùn)輸成本盡可能最少。II、引入0—1變量：l)xijk表示車輛k是否從客戶i行駛到客戶j。定義其為0—1變量,則車輛k從客戶i行駛到客戶j1Xijk0反之2)yijk表示客戶i的任務(wù)由車輛k完成。同樣定義其為0—1變量，則客戶i的任務(wù)由車輛k完成1Yijk0反之III、目標(biāo)函數(shù)建立：假設(shè)M為運(yùn)輸成本，F(xiàn)為等待損失，E為遲到所受懲罰，則MGSii1kFfminVii1nnEeminUii1所以，總費(fèi)用C最小為：C=M+F+E5.4模型求解根據(jù)遺傳算法、森林救火算法用C++編程【附錄二】運(yùn)行后得結(jié)果如下：路線一：0、6、4、0；路線二：0、3、1、2、0路線三：0、8、5、7、0目標(biāo)函數(shù)總成本為910。六、模型的評(píng)價(jià)