求解VRP問(wèn)題的改進(jìn)和聲搜索算法的研究.pdf

1、物流有企業(yè)“第三利潤(rùn)源泉”之稱(chēng)。在現(xiàn)代商業(yè)發(fā)展環(huán)境中，如何優(yōu)化物流系統(tǒng)，降低物流成本已經(jīng)成為企業(yè)要考慮的重要問(wèn)題。車(chē)輛路徑問(wèn)題(Vehicle routing problem，VRP)是物流配送中的核心問(wèn)題，合理安排配送車(chē)輛的路徑對(duì)企業(yè)降低運(yùn)營(yíng)成本，提高服務(wù)質(zhì)量有著重要意義。
　　車(chē)輛路徑問(wèn)題是典型的NP難解問(wèn)題，大多用啟發(fā)式算法求解。和聲搜索算法是一種新穎的啟發(fā)式算法，最近幾年得到了迅速發(fā)展，但是新提出的新和聲算法在求解車(chē)輛路徑

2、問(wèn)題方面研究并不充分。
　　本文研究了基于和聲搜索算法求解車(chē)輛路徑問(wèn)題的方法，并且提出了有效的改進(jìn)方法。主要研究?jī)?nèi)容包括:
　　(1)研究了和聲算法、多種改進(jìn)的和聲搜索算法，在原算法的基礎(chǔ)上，加入了2-opt算子，應(yīng)用到VRP問(wèn)題求解中，實(shí)驗(yàn)表明和聲搜索算法能求得較高質(zhì)量的可行解。
　　(2)對(duì)帶有容量限制的車(chē)輛路徑問(wèn)題(CVRP)，提出了一種改進(jìn)的全局最優(yōu)和聲搜索算法。該算法采用自然數(shù)編碼，在新和聲的生成過(guò)程中，增加

3、了和聲約束，避免了不可行解的生成，并利用2-opt算子對(duì)新的和聲進(jìn)行了優(yōu)化，從而壓縮了搜索空間，提高了算法效率。實(shí)驗(yàn)表明改進(jìn)后的算法提高了搜索效率。
　　(3)針對(duì)和聲搜索算法容易陷入局部最優(yōu)以及自然數(shù)編碼不便于結(jié)合其他算法等問(wèn)題，提出了螢火蟲(chóng)和聲搜索算法(FGHS)來(lái)求解CVRP。算法采用了實(shí)數(shù)編碼，在新解生成過(guò)程中，引入了螢火蟲(chóng)算法的更新公式，利用螢火蟲(chóng)的仿生特性改進(jìn)和聲搜索算法的音調(diào)調(diào)節(jié)，使算法不易陷入局部最優(yōu);提出了一種和