帶硬時(shí)間窗車(chē)輛路線問(wèn)題的模擬退火算法研究

PAGEPAGE2帶硬時(shí)間窗車(chē)輛路線問(wèn)題的模擬退火算法研究摘要：本文在對(duì)硬帶時(shí)間窗車(chē)輛路線問(wèn)題進(jìn)行描述的基礎(chǔ)上，建立了該問(wèn)題的數(shù)學(xué)模型。針對(duì)該模型的NP－h(huán)ard屬性，設(shè)計(jì)了相應(yīng)的模擬退火算法；即利用改進(jìn)節(jié)約法構(gòu)造初始可行解，提高了求解速度；路線內(nèi)和路線間同時(shí)進(jìn)行鄰域搜索，避免了算法陷入局部最優(yōu)；通過(guò)恰當(dāng)?shù)剡x擇技術(shù)參數(shù)，實(shí)現(xiàn)了快速有效地求得問(wèn)題的滿意解。實(shí)例仿真測(cè)算表明本文提出的算法求得的解質(zhì)量較高，從而說(shuō)明了模擬退火算法解決帶硬時(shí)間窗的車(chē)輛路線問(wèn)題具有一定的有效性和實(shí)用價(jià)值。關(guān)鍵詞：車(chē)輛路線問(wèn)題；硬時(shí)間窗；改進(jìn)節(jié)約法；模擬退火算法StudyonvehicleroutingproblemwithhardwindowsbysimulatedannealingalgorithmAbstract:Thispaperdescribesthevehicleroutingproblemwithhardtimewindow,andsetsupthemathematicalmodelofthisproblem.Inviewofthismodel’sNP-hardattribute,thepaperdesignesakindofsimulationannealingalgorithmtosolvethisproblem,ie.theinitialfeasiblesolutionismadeupbyimprovedsavingalgorithm.Neighboursearchingbetweentworoutesandintworoutesareusedatthesametimesothelocaloptimumsolutionisavoided.Bychoosingpropertechnologyparameter,itcanobtainsatisfiedsolutionquicklyandeffectively.Itisindicatedthattheresultsofthispaperisbetterbycalculatingthesimulationexample,andthesimulationannealingalgorithmhascertaineffectiveandpracticalvaluewhensolvingthiskindofproblems.Keywords:vehicleroutingproblem;hardtime-windows;improvedsavingalgorithm;simulatedannealingalgorithm;

1.引言車(chē)輛路線問(wèn)題（VehicleRoutingProblem，簡(jiǎn)稱(chēng)VRP）最早由Dantzig于1959年提出[1]。所謂VRP是指對(duì)一系列特定位置和需求量的客戶(hù)點(diǎn)，調(diào)用一定數(shù)量的車(chē)輛，從中心倉(cāng)庫(kù)出發(fā)，選擇最優(yōu)的行車(chē)路線，使車(chē)輛有序地訪問(wèn)各客戶(hù)點(diǎn)，在滿足特定的約束條件（如客戶(hù)的需求量，車(chē)輛載重限制等）下，使得貨物盡快達(dá)到客戶(hù)點(diǎn)并且運(yùn)輸總費(fèi)用最低。帶時(shí)間窗的車(chē)輛路線問(wèn)題（VehicleRoutingProblemwithTimeWindows，簡(jiǎn)稱(chēng)VRPTW）是在VRP的基礎(chǔ)上增加了時(shí)間窗約束的一種變化形式，是運(yùn)籌學(xué)和物流管理學(xué)科的研究熱點(diǎn)問(wèn)題之一。VRPTW給定了各客戶(hù)點(diǎn)的需求量和允許服務(wù)的時(shí)間范圍，求車(chē)輛從站點(diǎn)出發(fā)并回到站點(diǎn)的一組行車(chē)路線，滿足各車(chē)輛不超載，并使總費(fèi)用最少。VRPTW在實(shí)際的物流配送決策中經(jīng)常遇到，是典型的組合優(yōu)化問(wèn)題。Saveslbergh（1985）已經(jīng)證明VRPTW是一個(gè)NP難題[2]。在規(guī)模較小時(shí)，用精確解法可以求得問(wèn)題的最優(yōu)解；在求解大規(guī)模VRPTW時(shí)，無(wú)法避開(kāi)指數(shù)爆炸問(wèn)題，而啟發(fā)式算法總可以在有限時(shí)間里，找到滿意的次優(yōu)解或可行解，這是精確算法難以做到的。求解VRPTW的啟發(fā)式算法主要可以分為三類(lèi)：=1\*GB3①路線生成算法，包括節(jié)約算法和插入算法；②路線改進(jìn)算法，有2－Swap、2－opt、2－opt*、or－opt等；③現(xiàn)代優(yōu)化算法，包括禁忌搜索、遺傳算法、模擬退火算法和蟻群算法等。本文設(shè)計(jì)了一種改進(jìn)模擬退火算法，它首先應(yīng)用路線生成方法產(chǎn)生初始解，然后結(jié)合2－opt*、2－Swap和or－opt改進(jìn)策略用模擬退火算法對(duì)初始解進(jìn)行優(yōu)化，從而求得VRPTW的優(yōu)化解；最后用文獻(xiàn)[3]的數(shù)據(jù)對(duì)此算法進(jìn)行驗(yàn)證，說(shuō)明此算法的有效性。2.數(shù)學(xué)模型VRPTW可簡(jiǎn)單的描述如下：用于服務(wù)的若干車(chē)輛從站點(diǎn)出發(fā)，為處在不同地理位置、具有不同貨物需求和不同服務(wù)時(shí)間窗要求的所有顧客提供服務(wù)，然后返回站點(diǎn)。其目標(biāo)是在時(shí)間窗內(nèi)為顧客提供服務(wù)時(shí)，使車(chē)輛的行駛距離最短。首先，對(duì)數(shù)學(xué)模型中的決策變量和參數(shù)定義如下：I表示站點(diǎn)和客戶(hù)的集合，即，0表示站點(diǎn)；J表示客戶(hù)集合，即；K表示車(chē)輛集合，即；C表示車(chē)輛的最大容量；表示從客戶(hù)i到客戶(hù)j的運(yùn)輸成本；表示客戶(hù)j的需求量；為決策變量，車(chē)輛k從i到j(luò)時(shí)取1，否則取0；取1表示客戶(hù)j由車(chē)輛k提供服務(wù)，否則取0；表示客戶(hù)i接受服務(wù)的最早時(shí)間，i＝0時(shí)表示車(chē)輛從站點(diǎn)出發(fā)時(shí)間；表示客戶(hù)i接受服務(wù)的最遲時(shí)間；表示車(chē)輛k服務(wù)客戶(hù)i的開(kāi)始時(shí)間，要求落在區(qū)間內(nèi)；表示完成i點(diǎn)任務(wù)所需時(shí)間；表示車(chē)輛從客戶(hù)i行駛到客戶(hù)j的行駛時(shí)間；根據(jù)問(wèn)題描述，建立帶時(shí)間窗車(chē)輛路線問(wèn)題的數(shù)學(xué)模型如下[4]：Min（2-1）（2-2）（2-3）（2-4）（2-5）（2-6）（2-7）（2-8）（2-9）（2-10）式（2-1）為目標(biāo)函數(shù)，表示總配送距離最小；式（2-2）表示一個(gè)客戶(hù)只能由一個(gè)車(chē)輛提供服務(wù)；（2-3）、（2-4）和（2-5）表示車(chē)輛從站點(diǎn)0出發(fā)，服務(wù)完所有客戶(hù)后，最后回到站點(diǎn)；式（2-6）表示若車(chē)輛正在從客戶(hù)i到客戶(hù)j途中，它不能先于時(shí)間到達(dá)客戶(hù)j；式（2-7）保證滿足每輛車(chē)的容量限制；式（2-8）表示滿足客戶(hù)的時(shí)間窗要求；式（2-9）和（2-10）為0、1約束。3.模擬退火算法求解3.1模擬退火算法的原理[5]模擬退火算法（simulatedannealing）是局部搜索算法的擴(kuò)展。它不同于局部搜索算法之處是以一定的概率選擇鄰域中費(fèi)用值大的狀態(tài)。理論上講，它是一個(gè)全局最優(yōu)算法。模擬退火算法最早的思想由Metropolis在1953年提出，Kirkpatrick在1983年成功地應(yīng)用到組合優(yōu)化問(wèn)題中。退火是一種物理過(guò)程，一種金屬物體在加熱至一定的溫度后，它的所有分子在其狀態(tài)空間中自由運(yùn)動(dòng)。隨著溫度的下降，這些分子逐漸停留在不同的狀態(tài)。在溫度最低時(shí)，分子重新以一定的結(jié)構(gòu)排列。統(tǒng)計(jì)力學(xué)的研究表明，在同一個(gè)溫度，分子停留在能量小狀態(tài)的概率比停留在能量大狀態(tài)的概率要大。當(dāng)溫度相當(dāng)高時(shí)，每個(gè)狀態(tài)的概率基本相同，都接近平均值。當(dāng)溫度趨向0時(shí)，分子停留在最低能量狀態(tài)的概率趨向于1。模擬退火算法是一種基于上述退火原理建立的隨機(jī)搜索算法。組合優(yōu)化問(wèn)題與金屬物體的退火過(guò)程可進(jìn)行如下類(lèi)比：組合優(yōu)化問(wèn)題的解類(lèi)似于金屬物體的狀態(tài)，組合優(yōu)化問(wèn)題的最優(yōu)解類(lèi)似于金屬物體的能量最低狀態(tài)，組合優(yōu)化問(wèn)題的費(fèi)用函數(shù)類(lèi)似于金屬物體的能量。模擬退火算法的直觀理解是：在一個(gè)給定的溫度，搜索從一個(gè)狀態(tài)隨機(jī)地變化到另一個(gè)狀態(tài)，每一個(gè)狀態(tài)到達(dá)的次數(shù)服從一個(gè)概率分布，當(dāng)溫度很低時(shí)，以概率1停留在最優(yōu)解。為了克服局部搜索算法極易陷入局部最優(yōu)解的缺點(diǎn)，模擬退火算法使用基于概率的雙方向隨機(jī)搜索技術(shù):當(dāng)基于鄰域的一次操作使當(dāng)前解的質(zhì)量提高時(shí)，模擬退火算法接受這個(gè)被改進(jìn)的解作為新的當(dāng)前解；在相反的情況下，算法以一定的概率接受相對(duì)于當(dāng)前解來(lái)說(shuō)質(zhì)量較差的解作為新的當(dāng)前解，其中△c為鄰域操作前后解的評(píng)價(jià)值之差，T為退火過(guò)程的控制參數(shù)(即溫度)。模擬退火算法已在理論上被證明是一種以概率1收斂于全局最優(yōu)解的全局優(yōu)化算法。3.2VRPTW模擬退火算法設(shè)計(jì)（1）解的表示[6]啟發(fā)式算法求解車(chē)輛路線問(wèn)題時(shí)常用的解的表示方法有三種。=1\*GB3①客戶(hù)與虛擬物流中心共同排列；=2\*GB3②車(chē)輛和客戶(hù)對(duì)應(yīng)排列；=3\*GB3③客戶(hù)直接排列?？蛻?hù)直接排列的表示方法占用的計(jì)算機(jī)存儲(chǔ)量較少，表示直觀，而且容易產(chǎn)生可行解，因此本文解的表示采用客戶(hù)直接排列的方法。這種表示方法是直接產(chǎn)生L個(gè)1—L間互不重復(fù)的自然數(shù)的排列，該客戶(hù)排列就構(gòu)成一個(gè)解，并對(duì)應(yīng)一種配送路線方案。按照帶時(shí)間窗車(chē)輛路線問(wèn)題的約束條件，可依次將解的元素（客戶(hù)）劃入各臺(tái)車(chē)輛的配送路線中。例如，對(duì)于一個(gè)用3臺(tái)車(chē)輛向9個(gè)客戶(hù)送貨的帶時(shí)間窗車(chē)輛路線問(wèn)題，設(shè)某解中的客戶(hù)排列為412876935，可用如下方法得到其對(duì)應(yīng)的配送路線方案:首先將客戶(hù)4(解中的第1個(gè)客戶(hù))作為第1臺(tái)配送車(chē)輛服務(wù)的第1個(gè)客戶(hù)，然后判斷能否滿足問(wèn)題的約束條件，即客戶(hù)4的需求量是否超過(guò)第1臺(tái)車(chē)輛的最大載重量，且客戶(hù)4的服務(wù)時(shí)間窗能否被滿足，設(shè)能夠滿足，這時(shí)可將客戶(hù)1(解中的第2個(gè)客戶(hù))作為第1臺(tái)配送車(chē)輛服務(wù)的第2個(gè)客戶(hù)，然后判斷能否滿足問(wèn)題的約束條件，依此類(lèi)推。當(dāng)不能滿足問(wèn)題的約束條件時(shí)，這說(shuō)明客戶(hù)2不能由第1臺(tái)配送車(chē)輛服務(wù)，由此可得第1臺(tái)車(chē)輛的配送路線:0-4-1-0；然后，將客戶(hù)2作為第2臺(tái)配送車(chē)輛服務(wù)的第1個(gè)客戶(hù)，仍按上述方法可將解中的其它客戶(hù)也依次加入到其它車(chē)輛的配送路線中。若某個(gè)解中的排在最后的若干個(gè)客戶(hù)不能納入到車(chē)輛的配送路線中，則說(shuō)明該解為一個(gè)不可行解。（2）解的評(píng)價(jià)用上述表示方法所確定的配送路線方案，能夠滿足每條配送路線上各客戶(hù)需求量之和不超過(guò)配送車(chē)輛的最大載重量，并且滿足每個(gè)客戶(hù)的時(shí)間窗約束，但不能保證所有的客戶(hù)全部都能得到配送服務(wù)。對(duì)于某個(gè)解，若全部客戶(hù)均能納入到車(chē)輛的配送路線中，則該配送路線方案為一個(gè)可行解，計(jì)算該配送路線方案的目標(biāo)函數(shù)值，即為該解的評(píng)價(jià)值。（3）初始解的生成本文采用改進(jìn)節(jié)約法[7]構(gòu)造初始解，其詳細(xì)步驟如下：1）初始化，N個(gè)需求點(diǎn)構(gòu)造N條路線，每條路線只包含一個(gè)需求點(diǎn)；2）計(jì)算任意兩點(diǎn)間的節(jié)約值，令，并在內(nèi)將按大小順序排列；其中。3）若為空集，則算法終止，否則考查對(duì)應(yīng)的（i，j），若滿足下列條件之一：①點(diǎn)i和點(diǎn)j均不在已構(gòu)成的線路上；②點(diǎn)i或點(diǎn)j在已構(gòu)成的線路上，但不是線路的內(nèi)點(diǎn)；③點(diǎn)i和點(diǎn)j在已構(gòu)成的線路上，但均不是內(nèi)點(diǎn)，且一個(gè)是起點(diǎn)，一個(gè)是終點(diǎn)。則轉(zhuǎn)步驟4）；否則轉(zhuǎn)步驟6）；4）檢查點(diǎn)i和點(diǎn)j連接后路線上的客戶(hù)總需求量，若，則轉(zhuǎn)步驟5）；否則轉(zhuǎn)步驟6）；5）計(jì)算點(diǎn)j及其之后的點(diǎn)的時(shí)間窗約束，若滿足則連接點(diǎn)i、j，轉(zhuǎn)步驟6）；否則直接轉(zhuǎn)步驟6）；6）令，轉(zhuǎn)步驟3）。（4）鄰域解的構(gòu)造1）路線間將當(dāng)前路線中的k條邊用另外k條邊代替，這種變換稱(chēng)為k-opt[8],最為常見(jiàn)的是2-opt，即將邊(i,i+1)、(j,j+1)用(i,j)、(i+1,j+1)代替。然而這種交換使得原來(lái)路線中邊(i+1,j)的方向發(fā)生變化，由于VRPTW問(wèn)題中有時(shí)間窗約束，這種方向的改變很可能導(dǎo)致所得路線不可行。因而在求解VRPTW問(wèn)題時(shí)，使用2－opt*[9]比2－opt更有效。2－opt*變換是用邊(i,j+1)、(j,i+1)代替邊(i,i+1)、(j,j+1),即將兩條路線中顧客i、j后的所有顧客整體交換，如圖1所示?？梢钥吹?，這種交換保持了原來(lái)路線中顧客的先后次序，所以變換后路線的可行性得到了保證。因而適用于帶時(shí)間窗的車(chē)輛路線問(wèn)題的路線間優(yōu)化。iiii+1i+1j+1jj+1j代表選中DC，代表客戶(hù)，和代表路線圖12－opt*交換法示意圖2）路線內(nèi)①Or-opt法Or-opt法是考慮一條路線中任意一個(gè)點(diǎn)（或多個(gè)點(diǎn)）插入到其他弧中的方法。在本文中任意選擇路線中的一個(gè)點(diǎn)，考慮其插入到其他弧中的目標(biāo)函數(shù)值，如果滿足時(shí)間窗同時(shí)得到更小的目標(biāo)函數(shù)值則更新當(dāng)前路線。這種交換只改變了所要交換的點(diǎn)的優(yōu)先順序，并不改變其他點(diǎn)的順序，也能滿足帶時(shí)間窗路線問(wèn)題的要求。Or－opt的插入過(guò)程如圖2所示（需求點(diǎn)3插入到弧1－2中）。224312431代表選中DC，代表客戶(hù)，和代表路線圖2Or-opt交換示意圖②2－Swap2-Swap指任意選擇一條路線，從中任意選擇兩個(gè)不同的客戶(hù)，交換它們的位置。2－Swap交換過(guò)程的示意圖如圖3所示。（5）溫度參數(shù)的控制1）初始溫度的選取初始溫度值的設(shè)置是影響模擬退火算法全局搜索性能的重要因素之一。初始溫度高，則算法搜索到全局最優(yōu)解的可能性大，但因此要花費(fèi)大量的計(jì)算時(shí)間；反之，則可節(jié)約計(jì)算時(shí)間，但全局搜索性能可能受到影響。實(shí)際應(yīng)用過(guò)程中，需要依據(jù)實(shí)驗(yàn)結(jié)果進(jìn)行若干次調(diào)整。從理論上說(shuō)，初始溫度t0應(yīng)保證平穩(wěn)分布中每一狀態(tài)的概率相等，即滿足，據(jù)此可以很容易地得到初始溫度的一個(gè)估計(jì)值，即，，K為充分大的正數(shù)，實(shí)際計(jì)算中可取K=10,20,100,?等實(shí)驗(yàn)值。334214231代表選中DC，代表客戶(hù)，和代表路線圖32-Swap法示意圖，實(shí)際計(jì)算中，對(duì)的值可以簡(jiǎn)單地加以估計(jì)。2)溫度下降規(guī)則本文采用下式實(shí)現(xiàn)模擬退火算法的溫度下降過(guò)程，，式中是迭代次時(shí)的當(dāng)前溫度，一個(gè)小的時(shí)間常數(shù)。3）每一溫度的迭代步長(zhǎng)采用上述溫度下降規(guī)則，用以下退火策略：①若在溫度時(shí)，隨機(jī)進(jìn)行次循環(huán)，就認(rèn)為在該溫度下，每個(gè)分子都已經(jīng)有足夠的機(jī)會(huì)達(dá)到最佳位置。因而可以將溫度下降到。②若在溫度時(shí)，成功地對(duì)解改進(jìn)次。這相當(dāng)于退火過(guò)程中，已有足夠的分子達(dá)到了最佳位置。在這時(shí)，也將溫度下降到。（6）停止規(guī)則算法停止規(guī)則是當(dāng)溫度降至終止溫度時(shí)，表示已經(jīng)達(dá)到最低溫度，算法停止。3.3模擬退火算法的實(shí)現(xiàn)步驟模擬退火算法的詳細(xì)步驟如下，程序框圖見(jiàn)圖4。Step1：設(shè)置控制參數(shù)。包括初始溫度、溫度衰減系數(shù)、終止溫度，當(dāng)前溫度迭代次數(shù)，當(dāng)前成功迭代次數(shù)；Step2：初始解的產(chǎn)生。用改進(jìn)節(jié)約法產(chǎn)生；；Step3：構(gòu)造鄰域解。按照上述方法進(jìn)行路線內(nèi)和路線間調(diào)整得到一個(gè)鄰域解，且；Step4：判斷時(shí)間窗約束。若不滿足時(shí)間窗約束，轉(zhuǎn)Step3；Step5：比較。如果，則轉(zhuǎn)Step6；否則，記錄當(dāng)前解為最優(yōu)解，，轉(zhuǎn)Step7；Step6：Metropolis準(zhǔn)則檢驗(yàn)。計(jì)算，若時(shí)，則，；否則不接受；轉(zhuǎn)Step7；Step7：溫度下降規(guī)則。若或時(shí)，，，，轉(zhuǎn)Step8；否則返回Step3；Step8：算法終止規(guī)則。若當(dāng)前溫度時(shí)，算法終止；否則返回Step3。用用改進(jìn)節(jié)約方法產(chǎn)生初始解；,,,,,路線內(nèi)2－Swap法Or-opt法路線間2-opt*算法,判斷算法終止判斷溫度下降，是輸出解否否否Metropolis準(zhǔn)則否是是是時(shí)間窗是否圖4模擬退火算法求解VRPTW程序框圖4.程序?qū)崿F(xiàn)及實(shí)例計(jì)算本文對(duì)所設(shè)計(jì)的算法采用C＋＋語(yǔ)言編程進(jìn)行驗(yàn)證，運(yùn)用文獻(xiàn)[3]中的數(shù)據(jù)（見(jiàn)表1）進(jìn)行測(cè)算。其中，站點(diǎn)坐標(biāo)為（30，50），車(chē)輛的最大載重量為5，車(chē)輛的行駛速度為1.經(jīng)反復(fù)試驗(yàn)，初始溫度取50，溫度衰減系數(shù)取0.95，當(dāng)前溫度最大迭代次數(shù)U和最大成功迭代次數(shù)L分別取100和35，得到表2的計(jì)算結(jié)果，其路線如圖5。表1有關(guān)客戶(hù)點(diǎn)的數(shù)據(jù)客戶(hù)編號(hào)123456789101112131415橫坐標(biāo)193335537027105616684183257370縱坐標(biāo)032119944469481761043912918需求量1.01.60.9開(kāi)始時(shí)刻24582476273562957126458154677結(jié)束時(shí)刻9412811513611715212978103121171158125136167表2文獻(xiàn)[3]的結(jié)果和本文的結(jié)果比較算法禁忌搜索算法（文獻(xiàn)[3]）改進(jìn)節(jié)約法（初始解）模擬退火算法（優(yōu)化解）使用的車(chē)輛數(shù)455配送總距離585.77566.972525.638禁忌搜索算法路線（文獻(xiàn)[3]）節(jié)約法路線（初始解）模擬退火路線（優(yōu)化解）圖5三種算法行駛路線圖

5結(jié)論本文以總行駛距離最短為目標(biāo)，構(gòu)建了帶硬時(shí)間窗車(chē)輛路線問(wèn)題的數(shù)學(xué)模型并設(shè)計(jì)了求解該模型的模擬退火算法。通過(guò)實(shí)例對(duì)VRPTW模型進(jìn)行求解，得到如下結(jié)論：（1）采用改進(jìn)節(jié)約法產(chǎn)生初始可行解，使模擬退火算法能夠快速有效地得到滿意解；（2）表2和圖5的對(duì)比表明：在滿足容量和時(shí)間窗約束的條件下，模擬退火算法所得的車(chē)輛路線劃分區(qū)域明顯優(yōu)于文獻(xiàn)[3]的禁忌搜索算法，兩者路線總長(zhǎng)相差10％左右；（3）模擬退火算法求解速度快。對(duì)于帶硬時(shí)間窗車(chē)輛路線問(wèn)題，在Pentinum4CPU3.00GHZ的計(jì)算機(jī)上運(yùn)行本實(shí)例只需1.125s；（4）優(yōu)化過(guò)程中，在路線間采用2－opt*、路線內(nèi)采用or－opt和2－Swap方法搜索鄰域解，擴(kuò)大了搜索空間，避免了局部最優(yōu)解，提高了解的精度。因此本文提出的算法計(jì)算效率較高，收斂速度較快，計(jì)算結(jié)果穩(wěn)定，具有較強(qiáng)的實(shí)用價(jià)值。

參考文獻(xiàn)：[1]DantizigG.,RamserJ..Thetruckdispatchingproblem[J].ManagementScience,1959,6:80~91.[2]賓松，符卓.求解帶軟時(shí)間窗的車(chē)輛路徑問(wèn)題的改進(jìn)遺傳算法[J].系統(tǒng)工程.2021.11.[2]BingSong,FuZhuo.Animprovedgeneticalgorithmforvehicleroutingproblemwithsofttimewindows[J].SystemEngineering.2021.11.[3]徐巖山，張良心.車(chē)材配送調(diào)度優(yōu)化問(wèn)題的一種改進(jìn)禁忌搜索算法[J].軍事運(yùn)籌與系統(tǒng)工程.2021.9.[3]XuYanshan,ZhangLiangxin.Animprovedtabusearchalgorithmforvehicleroutingproblemwithtimewindows[J],MilitaryOperationsResearchandSystemsEngineering.2021.9.[4]PaoloToth,DanieleVigo,2021,Thevehicleproblem[M],Copyright?2021bySocietyforIndustryandAppliedMathematics.2021:158~160.[5]邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計(jì)算方法[M].北京：清華大學(xué)出版社，2021.8.[5]XingWenxun,XieJinxing.ModernoptimizationAlgorithm[M].QinghuaUniversity[6]郎茂祥，物流配送車(chē)輛調(diào)度問(wèn)題的模型和算法研究[D]，北京：北方交通大學(xué)博士學(xué)位論文，2021.2.[6]LangMaoxiang,Themodelsandalgorithmsforphysicaldistributionvehicleschedulingproblem[D],BeiJing:DoctordegreepaperinBeiJingtrafficUniversity,2021.2.[7]李軍，郭耀煌.物流配送車(chē)輛優(yōu)化調(diào)度理論與方法[M].北京：中國(guó)物資出版社，2021.11.[7]LiJun,GuoYaohuang.Thetheoryandmethodsforphysicaldistributionvehiclescheduling[M].BeiJing:Chinamaterialspublishinghouse,2021.11.[8]S.Lin,Computersolutionsofthetravelingsalesmanproblem.BellSystemTech.[J].1964:2245-2246.[9]J.Potvin,J.Rousseau.Anexchangeheuristicforroutingproblemswithtimewindows[J].JournaloftheOperationalResearchSociety1995,46(12):1433-1466.

本科生學(xué)位論文論多媒體技術(shù)在教學(xué)中的應(yīng)用姓名：指導(dǎo)教師：專(zhuān)業(yè)：教育管理專(zhuān)業(yè)年級(jí)：完成時(shí)間：

論多媒體技術(shù)在教學(xué)中的應(yīng)用[摘要]多媒體不再是傳統(tǒng)的輔助教學(xué)工具，而是為構(gòu)造一種新的網(wǎng)絡(luò)教學(xué)環(huán)境創(chuàng)造了條件，特別是對(duì)于教育社會(huì)化來(lái)說(shuō)，多媒體網(wǎng)絡(luò)是一種更理想的傳播工具。多媒體本身具有：融合性、非線性化，無(wú)結(jié)構(gòu)性、相互交涉性、可編輯性、實(shí)時(shí)性等特點(diǎn)；同時(shí)運(yùn)用在教育教學(xué)上又有其特長(zhǎng)：利于信息的存儲(chǔ)利用、是培養(yǎng)發(fā)散性思維的工具、促使學(xué)習(xí)個(gè)別化的實(shí)現(xiàn)。多媒體在教學(xué)中的應(yīng)用有著多種的形式，它在提高學(xué)生學(xué)習(xí)興趣上有著積極的作用，同時(shí)它還能促進(jìn)學(xué)生知識(shí)的獲取與保持、對(duì)教學(xué)信息進(jìn)行有效的組織與管理、建構(gòu)理想的學(xué)習(xí)環(huán)境，促進(jìn)學(xué)生自主學(xué)習(xí)等多方面的效果。立足未來(lái)發(fā)展，利用多媒體網(wǎng)絡(luò)技術(shù)，開(kāi)展教學(xué)試驗(yàn)。[關(guān)鍵詞]多媒體網(wǎng)絡(luò)教學(xué)系統(tǒng)資源共享多媒體技術(shù)主要指多媒體計(jì)算機(jī)技術(shù)，加工、控制、編輯、變換，還可以查詢(xún)、檢索。人們借助于多媒體技術(shù)可以自然貼切地表達(dá)、傳播、處理各種視聽(tīng)信息，并具有更多的參與性和創(chuàng)造性。當(dāng)今多媒體已成為廣泛流傳的名詞，但人們對(duì)于它的認(rèn)識(shí)，特別是對(duì)于它在教育教學(xué)方面如何更好應(yīng)用，未知的因素還很多。

一、多媒體的教育特長(zhǎng)任何一種媒體不管其怎樣先進(jìn)，它只能是作為一種工具被應(yīng)用到教育領(lǐng)域，能不能促進(jìn)教育的改革，。。。。。。應(yīng)當(dāng)吸取教訓(xùn)，加強(qiáng)理論研究，充分認(rèn)識(shí)多媒體的特性及其教育特長(zhǎng)，以便更好地在教育領(lǐng)域開(kāi)發(fā)應(yīng)用多媒體。

1、多媒體的特性

（1）融合性多種符號(hào)系統(tǒng)的融合是多媒體的特性之一，多媒體的這一特性區(qū)別于過(guò)去媒體符號(hào)系統(tǒng)的單一性或復(fù)合性。也就是說(shuō)多媒體技術(shù)不是將符號(hào)系統(tǒng)疊加，而是具有整體性的融合。

（2）非線性化，無(wú)結(jié)構(gòu)性因?yàn)槎嗝襟w是在超文本、，其組合結(jié)構(gòu)是固定的、不變的。

（5）實(shí)時(shí)性多媒體信息中的聲音、活動(dòng)視瀕、動(dòng)畫(huà)于時(shí)間有密切聯(lián)系，對(duì)它們進(jìn)行呈現(xiàn)、交互等集成處理是實(shí)時(shí)的。在顯示某一主體內(nèi)容時(shí)，其視聽(tīng)信息具有同步性。

2、多媒體的教育特長(zhǎng)

（1）信息的存儲(chǔ)利用便利多媒體特別是多媒體WWW網(wǎng)絡(luò)信息的存儲(chǔ)、提取、雙向傳輸非常便利，它應(yīng)用于教育，更利于教學(xué)信息傳播機(jī)制的建立。

（2）發(fā)散性思維的工具在培養(yǎng)學(xué)習(xí)者發(fā)散性思維方面…………或創(chuàng)造性思維的基礎(chǔ)。