莊夢(mèng)婷

安徽財(cái)經(jīng)大學(xué)統(tǒng)計(jì)與應(yīng)用數(shù)學(xué)學(xué)院，中國(guó)·安徽 蚌埠 233030

1 引言

同城配送存在路徑迂回問(wèn)題，所謂迂回運(yùn)輸就是沒(méi)有從最短的路線運(yùn)輸，而是繞道運(yùn)輸?shù)男问?，如因到達(dá)地區(qū)順序不同而導(dǎo)致的總路徑變長(zhǎng)。物流公司不能以最近的公路運(yùn)輸，將會(huì)直接影響公司的運(yùn)輸效率降低，也會(huì)導(dǎo)致不必要的運(yùn)輸成本增加[1]。而道路迂回問(wèn)題是在很多物流配送過(guò)程中存在的問(wèn)題。

配送車(chē)輛承載量的約束條件：每輛貨車(chē)都存在其重量承載量以及體積承載量，考慮到承載量的問(wèn)題，每輛貨車(chē)所承載的貨物有限。綜合考慮不同城區(qū)物流件數(shù)之間存在的差異，派送車(chē)輛數(shù)量成為一個(gè)問(wèn)題。時(shí)間約束因素包括即物流配送過(guò)程貨物有要求到達(dá)時(shí)間、大部分同城運(yùn)輸都要求在當(dāng)天完成貨物配送，其他因素包括路段時(shí)速限制、堵車(chē)的可能性、天氣限速。

2 研究設(shè)計(jì)

2.1 基于模擬退火模型的單式運(yùn)輸路徑優(yōu)化

針對(duì)起點(diǎn)到終點(diǎn)只有一種運(yùn)輸方式可供選擇，即直達(dá)的情況，我們擬建立模擬退火模型從運(yùn)輸路徑角度進(jìn)行優(yōu)化；綜合考慮車(chē)的承載量以及不同地區(qū)訂單數(shù)存在的差異的問(wèn)題，利用聚類分析，將地區(qū)進(jìn)行分類，在不同地區(qū)上利用模擬退火算法進(jìn)行不同區(qū)域的最短路徑計(jì)算。具體包括：發(fā)貨點(diǎn)和收貨點(diǎn)的設(shè)置；規(guī)劃適當(dāng)?shù)穆肪€；使運(yùn)輸車(chē)輛能夠有序地通過(guò)計(jì)劃中的地點(diǎn)以及完成貨物的需求量和發(fā)貨量，并且滿足交貨時(shí)間，即達(dá)到實(shí)現(xiàn)最短時(shí)間內(nèi)；最短運(yùn)輸成本下完成相應(yīng)的目標(biāo)，去掉在路上的“浪費(fèi)”[2]。

2.2 研究方法：模擬退火算法

模擬退火是一種通用概率算法，用來(lái)在一個(gè)大的搜尋空間內(nèi)找尋命題的最優(yōu)解。其來(lái)源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻。加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小[3]。對(duì)于地點(diǎn)之間的轉(zhuǎn)移概率矩陣兩兩相互之間是互通的，即可得出該轉(zhuǎn)移矩陣對(duì)應(yīng)的有限的馬爾科夫鏈?zhǔn)鞘諗康摹Ｊ諗空f(shuō)明過(guò)程將達(dá)到平衡狀態(tài)，即此后過(guò)程取某一個(gè)狀態(tài)的概率不隨時(shí)間變化[4]。

①解空間S表示為{2,3, ,}n,1 … 的所有起點(diǎn)和終點(diǎn)的循環(huán)排列集合，即：

其中，每一個(gè)循環(huán)排列表示運(yùn)輸完n個(gè)運(yùn)輸點(diǎn)的一個(gè)回路，πi=m 表示在第i-1次運(yùn)輸目標(biāo)m，初始解可選為(1 , 2,3,…, n)，這里使用蒙特卡洛法求得一個(gè)比較好的初始解。

②目標(biāo)函數(shù)：目標(biāo)函數(shù)為一次走過(guò)所有運(yùn)輸點(diǎn)的路徑長(zhǎng)度，即：

③新解的產(chǎn)生。設(shè)上一步迭代的解為：

應(yīng)用變換法時(shí)，任選序號(hào)u,v交換u和v之間的順序，變成逆序，此時(shí)的新路徑為：

④代價(jià)函數(shù)差：對(duì)于2變換法，路徑差可表示為：

⑤接受準(zhǔn)則：

⑥降溫：利用選定的降溫系數(shù)α進(jìn)行降溫，取新的溫度T為αT（這里T為上一步迭代的溫度），這里選定α = 0.999。

⑦結(jié)束條件：用選定的終止溫度e = 10-30，判斷退火過(guò) 程是否結(jié)束。若T＜e，則算法結(jié)束，輸出當(dāng)前狀態(tài)[5]。

求解過(guò)程如模擬退火流程圖1所示。

圖1 模擬退火流程圖

2.3 數(shù)據(jù)的搜集和處理

由案例以及網(wǎng)上搜索可得到中國(guó)北京市某次單運(yùn)輸方式任務(wù)的物流采購(gòu)點(diǎn)以及產(chǎn)品運(yùn)輸點(diǎn)，并將中國(guó)北京市需要運(yùn)輸?shù)倪\(yùn)輸點(diǎn)以坐標(biāo)點(diǎn)的形式寫(xiě)在一個(gè)平面上。

根據(jù)上述流程圖，我們?yōu)榭臻g設(shè)計(jì)了LINGO自動(dòng)診斷的代碼，只要將某次需要向外運(yùn)輸或者采購(gòu)原材料的運(yùn)輸點(diǎn)坐標(biāo)數(shù)據(jù)輸入并在程序中加入循環(huán)語(yǔ)句，運(yùn)行出運(yùn)行結(jié)果，得到最短運(yùn)輸路徑。這條運(yùn)輸路徑能保證運(yùn)輸人員在無(wú)一運(yùn)輸點(diǎn)遺漏的情況下，所走的運(yùn)輸路徑最短，也就是說(shuō)此時(shí)達(dá)到了路徑的優(yōu)化。

3 算例分析

為了更好地體現(xiàn)模擬退火模型在單一運(yùn)輸方式上的運(yùn)輸效果，我們以中國(guó)北京市某次運(yùn)輸案例為例，運(yùn)用模擬退火模型對(duì)路徑進(jìn)行優(yōu)化設(shè)計(jì)。選取中國(guó)北京市為例，提貨區(qū)為朝陽(yáng)區(qū)，剩余地區(qū)為所需配送地區(qū)。

距離矩陣如下表1所示。

表1 北京市各區(qū)距離矩陣

3.1 單一式配送

在不考慮訂單量的約束條件下，貨物從起點(diǎn)出發(fā)，送達(dá)各目的地對(duì)應(yīng)的編號(hào)如表2所示[6]。

表2 地區(qū)編號(hào)

目標(biāo)函數(shù)為尋找從點(diǎn)出發(fā)，遍歷中間點(diǎn)，返回n的最短路徑。在計(jì)算機(jī)上運(yùn)行以上程序，總運(yùn)輸距離為462km，運(yùn)輸路徑為1-15-14-3-2-7-6-8-16-13-5-12-11-10-4-9，表明從朝陽(yáng)區(qū)出發(fā)，經(jīng)過(guò)東城區(qū)、西城區(qū)、海淀區(qū)、豐臺(tái)區(qū)、大興區(qū)、房山區(qū)、石景山區(qū)、門(mén)頭溝區(qū)、延慶區(qū)、昌平區(qū)、懷柔區(qū)、密云區(qū)、平谷區(qū)、順義區(qū)，最終回到通州區(qū)。

3.2 多車(chē)配送

考慮到訂單量的情況下，將中國(guó)北京市16各地區(qū)首先要根據(jù)地理位置進(jìn)行分類，再結(jié)合訂單多、少相互配合，聚類圖如下圖2所示[7]。

圖2 聚類結(jié)果圖

將地區(qū)分為三類：

第一類為順義區(qū)、平谷區(qū)、密云區(qū)、柔懷區(qū)、昌平區(qū)、延慶區(qū)，這些地區(qū)中，順義區(qū)訂單最多，其余地區(qū)訂單較少，恰好滿足貨車(chē)的承載量需求。

第二類為在滿足貨車(chē)承載量的前提下訂單量較多的通州區(qū)和大興區(qū)。

第三類為東城區(qū)，西城區(qū)、海淀區(qū)訂單較多和門(mén)頭溝區(qū)和房山區(qū)訂單較少的地區(qū)組成。重復(fù)上述計(jì)算過(guò)程，得出每個(gè)區(qū)的最短路徑和總路徑。

結(jié)果顯示，第一類的路徑為朝陽(yáng)區(qū)、順義區(qū)、平谷區(qū)、密云區(qū)、柔懷區(qū)、昌平區(qū)、延慶區(qū)，最終回到朝陽(yáng)區(qū)，路徑長(zhǎng)度為333km。第二類路徑為從朝陽(yáng)區(qū)出發(fā)，先結(jié)果通州區(qū)，再到大興區(qū)，最后回到朝陽(yáng)區(qū)，路徑長(zhǎng)度為98km。第三類路徑為朝陽(yáng)區(qū)、東城區(qū)、海淀區(qū)、石景山區(qū)、門(mén)頭溝區(qū)、房山區(qū)、豐臺(tái)區(qū)、西城區(qū)，最后回到朝陽(yáng)區(qū)，該路徑長(zhǎng)度為127km。三類區(qū)域總路徑為558km。

4 結(jié)語(yǔ)

由算例分析，我們可以發(fā)現(xiàn)模擬退火算法的優(yōu)點(diǎn)和在應(yīng)用中進(jìn)行推廣的原因：

①在用模擬退火模型處理最短路徑問(wèn)題的時(shí)候，編程工作量少，且易于實(shí)現(xiàn)，統(tǒng)計(jì)上可以保證找到全局最優(yōu)解。

②模擬退火算法是一種新的隨機(jī)搜索方法，適合于解決大規(guī)模組合優(yōu)化問(wèn)題的通用而有效的近似算法。因此，也適用于論文中的運(yùn)輸優(yōu)化問(wèn)題。

③與以往的近似算法相比,模擬退火算法具有描述簡(jiǎn)單、使用靈活、運(yùn)用廣泛、運(yùn)行效率高和較少受到初始條件約束等優(yōu)點(diǎn)。

④模擬退火在找到最優(yōu)解時(shí)需要花費(fèi)非常多的時(shí)間，當(dāng)冷卻速度過(guò)快時(shí)，會(huì)導(dǎo)致模擬退火無(wú)法找到最優(yōu)解，但速度過(guò)慢，又會(huì)導(dǎo)致運(yùn)行時(shí)間變長(zhǎng)。

此模型可以對(duì)各類運(yùn)輸問(wèn)題的路徑進(jìn)行優(yōu)化，只要將運(yùn)輸點(diǎn)數(shù)量輸入程序和將運(yùn)輸點(diǎn)變換為坐標(biāo)格式，就能得到一次性走過(guò)各點(diǎn)的最短路徑，避免了重復(fù)走在運(yùn)輸上的“浪費(fèi)”，這也是基于節(jié)能減排理念的一種物流優(yōu)化。利用此方法，可以將很多交通以及其他方面的交通運(yùn)輸問(wèn)題達(dá)到路徑最優(yōu)化，從而實(shí)現(xiàn)高效的交通運(yùn)輸速度。