求解VRP問題的改進和聲搜索算法的研究.pdf

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

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

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