發(fā)布時間：2018-04-13 22:39

  本文選題：車輛路徑問題 + 和聲搜索算法��； 參考：《浙江師范大學》2015年碩士論文

【摘要】：物流有企業(yè)“第三利潤源泉”之稱。在現(xiàn)代商業(yè)發(fā)展環(huán)境中,如何優(yōu)化物流系統(tǒng),降低物流成本已經(jīng)成為企業(yè)要考慮的重要問題。車輛路徑問題(Vehicle routing problem, VRP)是物流配送中的核心問題,合理安排配送車輛的路徑對企業(yè)降低運營成本,提高服務質(zhì)量有著重要意義。車輛路徑問題是典型的NP難解問題,大多用啟發(fā)式算法求解。和聲搜索算法是一種新穎的啟發(fā)式算法,最近幾年得到了迅速發(fā)展,但是新提出的新和聲算法在求解車輛路徑問題方面研究并不充分。本文研究了基于和聲搜索算法求解車輛路徑問題的方法,并且提出了有效的改進方法。主要研究內(nèi)容包括：(1)研究了和聲算法、多種改進的和聲搜索算法,在原算法的基礎上,加入了2-opt算子,應用到VRP問題求解中,實驗表明和聲搜索算法能求得較高質(zhì)量的可行解。(2)對帶有容量限制的車輛路徑問題(CVRP),提出了一種改進的全局最優(yōu)和聲搜索算法。該算法采用自然數(shù)編碼,在新和聲的生成過程中,增加了和聲約束,避免了不可行解的生成,并利用2-opt算子對新的和聲進行了優(yōu)化,從而壓縮了搜索空間,提高了算法效率。實驗表明改進后的算法提高了搜索效率。(3)針對和聲搜索算法容易陷入局部最優(yōu)以及自然數(shù)編碼不便于結(jié)合其他算法等問題,提出了螢火蟲和聲搜索算法(FGHS)來求解CVRP。算法采用了實數(shù)編碼,在新解生成過程中,引入了螢火蟲算法的更新公式,利用螢火蟲的仿生特性改進和聲搜索算法的音調(diào)調(diào)節(jié),使算法不易陷入局部最優(yōu)；提出了一種和聲庫重置方法,在算法陷入局部最優(yōu)時,利用混沌擾動系統(tǒng)增加和聲記憶庫中解的多樣性來幫助算法跳出局部最優(yōu),同時用局部搜索來增強尋優(yōu)能力。
[Abstract]:Logistics has the enterprise "the third profit source" said.In the modern commercial development environment, how to optimize the logistics system and reduce the logistics cost has become an important issue for enterprises to consider.Vehicle routing problem (VRP) is the core problem in logistics distribution. It is of great significance for enterprises to reduce operation cost and improve service quality by reasonably arranging vehicle routing.Vehicle routing problem is a typical NP-hard problem, which is mostly solved by heuristic algorithm.Harmony search algorithm is a new heuristic algorithm, which has been developed rapidly in recent years. However, the new harmonic algorithm is not enough to solve the vehicle routing problem.In this paper, the method of solving vehicle routing problem based on harmony search algorithm is studied, and an effective improvement method is proposed.The main research contents include: (1) the harmonic algorithm is studied, and many improved harmonic search algorithms are studied. Based on the original algorithm, the 2-opt operator is added to solve the VRP problem.Experiments show that the harmonic search algorithm can obtain a high quality feasible solution. (2) for the vehicle routing problem with capacity constraints, an improved global optimal harmonic search algorithm is proposed.The algorithm uses natural number coding. In the process of generating new harmony, it adds harmony constraints, avoids the generation of infeasible solutions, and optimizes the new harmony by using 2-opt operator, thus compressing the search space and improving the efficiency of the algorithm.Experiments show that the improved algorithm improves the search efficiency. (3) aiming at the problems that harmony search algorithm is easy to fall into local optimum and natural number coding is not easy to combine with other algorithms, a firefly harmonic search algorithm (FGHS) is proposed to solve CVRPs.In the process of generating the new solution, the update formula of the firefly algorithm is introduced, and the tone adjustment of the harmonic search algorithm is improved by using the bionic characteristic of the firefly, which makes the algorithm difficult to fall into local optimum.In this paper, a harmonic sound bank reset method is proposed. When the algorithm falls into a local optimum, the chaos disturbance system is used to increase the diversity of the solution in the harmonic memory bank to help the algorithm jump out of the local optimum, and the local search is used to enhance the searching ability.
【學位授予單位】：浙江師范大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：F259.23;TP301.6

【參考文獻】

相關期刊論文 前2條

1 李永林;葉春明;劉長平;;輪盤賭選擇自適應和聲搜索算法[J];計算機應用研究;2014年06期

2 姜大立,楊西龍,杜文,周賢偉;車輛路徑問題的遺傳算法研究[J];系統(tǒng)工程理論與實踐;1999年06期

，

本文編號：1746548