1、糧食是國(guó)家重要的經(jīng)濟(jì)和戰(zhàn)略物資.糧食調(diào)運(yùn)問(wèn)題是國(guó)家糧食管理部門和糧食企業(yè)急需解決的重要問(wèn)題.隨著電子商務(wù)和第三方物流的興起,出現(xiàn)了專業(yè)化的糧食物流企業(yè),為糧食物流的專業(yè)化運(yùn)行和成本節(jié)約開(kāi)創(chuàng)了新的模式.在糧食物流決策中,需要同時(shí)考慮運(yùn)行時(shí)間、成本和風(fēng)險(xiǎn)等因素,這樣,就將傳統(tǒng)單目標(biāo)的運(yùn)輸路徑問(wèn)題轉(zhuǎn)變成了多目標(biāo)問(wèn)題.同時(shí),時(shí)間因素對(duì)糧食運(yùn)輸?shù)闹T多因素都會(huì)產(chǎn)生一定的影響.因此研究具有時(shí)變特性的糧食運(yùn)輸問(wèn)題具有極強(qiáng)的社會(huì)背景和應(yīng)用前景.目前文獻(xiàn)中

2、研究的時(shí)變性物流調(diào)度往往以城市交通為背景.城市交通狀況變化的特點(diǎn)是以一天為一個(gè)周期,因而調(diào)度也在一天內(nèi)進(jìn)行.糧食運(yùn)輸與市內(nèi)物流不同,由于它是跨城市、跨地區(qū)的,運(yùn)行時(shí)間相對(duì)比較長(zhǎng),一次運(yùn)輸要經(jīng)歷多個(gè)周期.因此,針對(duì)糧食運(yùn)輸?shù)奶攸c(diǎn),有必要研究周期性時(shí)變網(wǎng)絡(luò)中的物流調(diào)度問(wèn)題.本論文從這種特殊時(shí)變網(wǎng)絡(luò)中的最短路問(wèn)題入手,從數(shù)學(xué)模型及算法設(shè)計(jì)方面開(kāi)展研究.主要研究成果如下:首先建立周期性時(shí)變網(wǎng)絡(luò)中最速路問(wèn)題的數(shù)學(xué)模型,其中主要運(yùn)用整數(shù)的模運(yùn)算,得

3、到動(dòng)態(tài)的狀態(tài)轉(zhuǎn)移方程.設(shè)一個(gè)周期分為K個(gè)時(shí)段k=0,1,…,K-1.已知t(i,j,k)為車輛在時(shí)段(狀態(tài))k從頂點(diǎn)i出發(fā)運(yùn)行到頂點(diǎn)j的時(shí)間長(zhǎng)度,則到達(dá)頂點(diǎn)j的時(shí)段(狀態(tài))為k’=[k+t(i,j,k)](modK).通過(guò)引進(jìn)車輛在時(shí)段k進(jìn)入邊e(i,j)的指示變量x(i,j,k)以及車輛在時(shí)刻k經(jīng)過(guò)頂點(diǎn)i的指示變量y(i,k),可得到最速路的數(shù)學(xué)模型:其中目標(biāo)函數(shù)(0.0.1)表示所選出邊的運(yùn)行時(shí)間之和最小;約束條件(0.0.2)表示

4、在時(shí)刻0從起點(diǎn)s出發(fā);(0.0.3)表示可在任意時(shí)段到達(dá)終點(diǎn)d;條件(0.0.4)表示車流經(jīng)過(guò)的頂點(diǎn);條件(0.0.5)表示狀態(tài)轉(zhuǎn)移關(guān)系:x(i,j,k)=1(?)y(j,k’)=1;條件(0.0.6)為(0,1)變量約束.這是一個(gè)(0,1)整數(shù)規(guī)劃.其次,由于(0,1)整數(shù)規(guī)劃不便求解,我們將其轉(zhuǎn)化為圖論模型.其主要思想是將頂點(diǎn)處于的不同狀態(tài)看做不同頂點(diǎn),按照狀態(tài)轉(zhuǎn)移方程來(lái)連邊.這樣便得到一個(gè)周期性時(shí)變網(wǎng)絡(luò).然后在其中運(yùn)用已知的最短路