基于多線(xiàn)程模擬退火算法在配送路線(xiàn)選擇中的應(yīng)用

摘要:合理的配送路線(xiàn)可以提高物流配送的效率。 針對(duì)標(biāo)準(zhǔn)模擬退火算法串行優(yōu)化單個(gè)解，優(yōu)化過(guò)程較長(zhǎng)、效率較低的弱點(diǎn)，提出一種基于多線(xiàn)程模擬退火的并行機(jī)制。該機(jī)制通過(guò)將單個(gè)解的串行優(yōu)化轉(zhuǎn)化為多個(gè)串行解同時(shí)進(jìn)行的并行的進(jìn)行搜索、優(yōu)化，來(lái)提高算法的整體優(yōu)化效率。利用該算法求解配送路線(xiàn)的選擇問(wèn)題能夠顯著提高優(yōu)化效率，計(jì)算結(jié)果表明該算法是有效的。

關(guān)鍵詞:配送路線(xiàn);模擬退火算法;多線(xiàn)程;物流

中圖分類(lèi)號(hào):TP319文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2009)14-3762-02

An Multithreading Simulated Annealing Algorithm for Delivery Route Selection

CHEN Huo

(School of Software Engineering， Hualian College， Guangzhou 510663， China)

Abstract: Rational delivery route can improve the efficiency of logistics distribution. This article puts forward a new way to improve the Simulated Annealing Algorithm base on the multithreading because of that the standard SA is a serial solving process and the solving process is so long， the efficiency is so low. This way can change a serial solving process into a multi-serial solving process in the same time to search and optimize the global solution. By the results from the experiment， we can draw a conclusion that the Multithreading SA is better than the Standard SA， it can improve the efficiency of solving the Selection of the delivery route.

Key words: delivery route; simulated annealing algorithm; multithreading; logistics

1 引言

物流配送作為一種專(zhuān)業(yè)化、社會(huì)化的服務(wù)模式，適應(yīng)了經(jīng)濟(jì)一體化的需要和社會(huì)化大生產(chǎn)的發(fā)展，所以越來(lái)越受到人們的重視. 配送是物流的關(guān)鍵環(huán)節(jié)，配送方法的好壞直接影響物流效益。 合理選擇配送路徑，對(duì)加快配送速度、提高服務(wù)質(zhì)量、降低配送成本以及增加經(jīng)濟(jì)效益都有很大影響，因此建立科學(xué)、合理、高效的物流配送體系顯得尤為重要，需要在物流配送的各個(gè)環(huán)節(jié)加以?xún)?yōu)化和改進(jìn)。

配送路線(xiàn)選擇問(wèn)題是在配送中心的配送區(qū)域確定以后，對(duì)某個(gè)配送中心每次配送的要求所制定的配送路線(xiàn)的選擇方案. 模型建立的原則是使得確定的配送路線(xiàn)總費(fèi)用最低。求解物流配送路徑優(yōu)化問(wèn)題的方法有很多，常用的有旅行商法、動(dòng)態(tài)規(guī)劃法、節(jié)約法、掃描法、分區(qū)配送法、方案評(píng)價(jià)法等。這些方法的缺點(diǎn)是當(dāng)問(wèn)題的規(guī)模較大時(shí)，很難得到全局最優(yōu)解或滿(mǎn)意解，而且隨著問(wèn)題規(guī)模的增大，算法的計(jì)算時(shí)間將以指數(shù)速度增加。因此研究的重點(diǎn)就轉(zhuǎn)移到各種啟發(fā)式算法上。

本文將在串行模擬退火的基礎(chǔ)上使用多線(xiàn)程(Multithreading)并行求解物流配送的最短路徑——MTSA。

2 物流配送的基本模型

選擇最優(yōu)配送路線(xiàn)的問(wèn)題可以描述如下:設(shè)有n個(gè)配送點(diǎn)，用數(shù)碼1，…，n代表。配送點(diǎn)i和配送點(diǎn)j之間的距離為d(i，j)，i，j=1，…，n。要找遍訪每個(gè)配送點(diǎn)恰好一次的一條回路，且其路徑總長(zhǎng)度為最短，這條回路就是最優(yōu)的配送路線(xiàn). 求解最優(yōu)配送路線(xiàn)的模擬退火算法模型可描述如下:

解空間:解空間S是遍訪每個(gè)配送點(diǎn)恰好一次的所有回路，是{1，…，n} 的所有循環(huán)排列的集合，S 中的成員記為(X1，X2，…，Xn) ，并記Xn+1=X1。初始解可選為(1，…，n)。

新解的產(chǎn)生:新路徑的產(chǎn)生:隨機(jī)產(chǎn)生1和n之間的兩相異數(shù)k和m，不妨假設(shè)k

變?yōu)樾侣窂?(X1，X2，…，Xm，Xk+1，…，Xk，Xm+1，…，Xn)上述變換方法就是將k和m對(duì)應(yīng)的兩個(gè)配送點(diǎn)在路徑序列中交換位置，稱(chēng)為2-opt映射。

目標(biāo)函數(shù):目標(biāo)函數(shù)為訪問(wèn)訪問(wèn)所有配送點(diǎn)的路徑總長(zhǎng)度或稱(chēng)為代價(jià)函數(shù)，其值最小:

3 標(biāo)準(zhǔn)模擬退火算法實(shí)現(xiàn)過(guò)程

①初始化:初始溫度T(T為足夠大)，初始解狀態(tài)S，每個(gè)T值的迭代次數(shù)L;

②對(duì)k = 1，2，…，L 作③～⑥步;

③對(duì)當(dāng)前狀態(tài)S隨機(jī)擾動(dòng)產(chǎn)生一個(gè)新解S';

④計(jì)算增量Δt'=C(S')-C(S)，其中C(S)為評(píng)價(jià)函數(shù);

⑤若Δt'< 0，則接受S'作為新的當(dāng)前解，否則以概率exp(-Δt'/T)接受S'作為新的當(dāng)前解;

⑥如果滿(mǎn)足終止條件，則輸出當(dāng)前解作為最優(yōu)解， 結(jié)束程序。終止條件通常取為連續(xù);

若干個(gè)新解都沒(méi)有被接受時(shí)終止算法;

⑦T逐漸減少，且T→0，然后轉(zhuǎn)第②步。

以上步驟稱(chēng)為Metropolis過(guò)程。按照一定的退火方案逐步降低溫度，重復(fù)Metropolis過(guò)程，就構(gòu)成了模擬退火優(yōu)化算法。當(dāng)系統(tǒng)溫度足夠低時(shí)，可認(rèn)為達(dá)到了全局最優(yōu)狀態(tài)。

4 基于多線(xiàn)程的模擬退火算法方法

標(biāo)準(zhǔn)模擬退火算法求解最優(yōu)路徑的算法比較耗時(shí)，很難在短時(shí)間內(nèi)就求出最優(yōu)解。主要體現(xiàn)在溫度的控制以及迭代次數(shù)的設(shè)置。例如初始溫度高，則算法搜索到全局最優(yōu)解的可能性大，但因此要花費(fèi)大量的計(jì)算時(shí)間;反之，則可節(jié)約計(jì)算時(shí)間，但全局搜索性能可能受到影響。從模擬退火的原理可以知道，是否接收新解是與上次解以及當(dāng)前溫度有關(guān)，這些決定了標(biāo)注的模擬退火是一個(gè)串行方式，不可能采用并行的方式;故在適當(dāng)?shù)慕档统跏紲囟?，減少迭代次數(shù)，而又不影響搜索全局最優(yōu)解，采用多線(xiàn)程方式(MTSA)，在同一臺(tái)服務(wù)器上，同時(shí)執(zhí)行多個(gè)串行模擬退火，達(dá)到并行搜索運(yùn)行的效果。

4.1 MTSA算法過(guò)程

Step 1:根據(jù)配送點(diǎn)的數(shù)目確定線(xiàn)程數(shù)目，取threadCount=(int)n/10;啟動(dòng)線(xiàn)程;

Step 2:每一線(xiàn)程啟動(dòng)一個(gè)完成的串行模擬退火過(guò)程。

①初始化:初始溫度T(T為足夠大)，初始解狀態(tài)S，每個(gè)T值的迭代次數(shù)L;

②k = 1，2，…，L 作③～⑥步;

③對(duì)當(dāng)前狀態(tài)S 隨機(jī)擾動(dòng)產(chǎn)生一個(gè)新解S';

④計(jì)算增量Δt'= C(S')-C(S)，其中C(S)為評(píng)價(jià)函數(shù);

⑤若Δt'<0，則接受S'作為新的當(dāng)前解，否則以概率exp(-Δt'/T)接受S'作為新的當(dāng)前解;

⑥如果滿(mǎn)足終止條件，則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。終止條件通常取為連續(xù)若干個(gè)新解都沒(méi)有被接受時(shí)終止算法;

⑦T逐漸減少，且T→0，然后轉(zhuǎn)第②步。

Step 3:比較計(jì)算每個(gè)線(xiàn)程最終搜索到的最優(yōu)解，得到該次的全局最優(yōu)解。

4.2 MTSA算法流程圖

圖1為MTSA算法流程圖。

5 算法應(yīng)用

根據(jù)本算法步驟，采用J2SE1.6分別編寫(xiě)了標(biāo)準(zhǔn)模擬退火算法以及基于多線(xiàn)程模擬退火算法的配送路線(xiàn)求解程序，并隨機(jī)生成了10個(gè)和51個(gè)、99個(gè)配送點(diǎn)作為實(shí)驗(yàn)對(duì)象。線(xiàn)程數(shù)目threadCount=配送點(diǎn)數(shù)目除以10取整;初始溫度T0=20*(配送點(diǎn)數(shù)目*(配送點(diǎn)之間距離最大值-配送點(diǎn)之間距離最小值))[12];迭代次數(shù)Iterative=配送點(diǎn)數(shù)目*配送點(diǎn)數(shù)目*10;計(jì)算結(jié)果見(jiàn)表1。

6 結(jié)束語(yǔ)

物流配送中，配送路線(xiàn)的選擇對(duì)于企業(yè)配送車(chē)輛的調(diào)度是非常重要的，優(yōu)化的配送路線(xiàn)能夠最大程度的提高車(chē)輛利用率，降低運(yùn)輸成本，提高配送效率，是企業(yè)利潤(rùn)的源泉之一。本文在傳統(tǒng)模擬退火方法的基礎(chǔ)上采用基于多線(xiàn)程模式，它的優(yōu)點(diǎn)主要表現(xiàn)在傳統(tǒng)的串行搜索模式轉(zhuǎn)變?yōu)椴⑿心Ｊ?，即在同一臺(tái)服務(wù)器上，同時(shí)進(jìn)行多個(gè)串行模擬退火算法，達(dá)到更高的搜索效率，同時(shí)也避免在初始溫度不夠高的情況下陷入局部收斂，提高整體的搜索效率。 但是過(guò)多的線(xiàn)程會(huì)使整臺(tái)機(jī)子的性能急速下降，這樣采用分布式并行模擬退火可能更好的處理這個(gè)問(wèn)題。

參考文獻(xiàn):

[1] 王之泰. 現(xiàn)代物流學(xué)[M]. 北京:中國(guó)地質(zhì)出版社，2003.

[2] 劉凱. 現(xiàn)代物流技術(shù)基礎(chǔ)[M]. 北京: 清華大學(xué)出版社，北京交通大學(xué)出版社，2004.

[3] 王豐元，潘福全. 基于交通限制的路網(wǎng)最優(yōu)路徑算法[J]. 交通運(yùn)輸工程學(xué)報(bào)，2005(1):92-95.

[4] 高國(guó)華，沈林成，常文森. 求解TSP的空間銳化模擬退火算法[J]. 自動(dòng)化學(xué)報(bào)，1999，25(3):425-428.

[5] 高尚. 求解旅行商問(wèn)題的模擬退火算法[J]. 華東船舶工業(yè)學(xué)院學(xué)報(bào)，2003，17(3):13-16.

[6] 張霖斌，姚振興，紀(jì)晨，等. 快速模擬退火算法及其應(yīng)用[J]. 石油地球物理勘探，1997，32(5):654-660.

[7] 張德富，顧衛(wèi)剛，沈平. 一種解旅行商問(wèn)題的并行模擬退火算法[J]. 計(jì)算機(jī)研究與發(fā)展，1995，32(2):1-4.

[8] 李樹(shù)有，都志輝，吳夢(mèng)月，等. 模擬退火算法的并行實(shí)現(xiàn)及其應(yīng)用[J]. 物理學(xué)報(bào)，2001，50(7):1260-1263.