本文選題：車輛路徑問(wèn)題 + 多目標(biāo)優(yōu)化問(wèn)題��； 參考：《東北大學(xué)》2014年碩士論文

【摘要】：車輛路徑問(wèn)題(Vehicle routing problem, VRP)是一個(gè)經(jīng)典的運(yùn)籌學(xué)問(wèn)題,它是指若干個(gè)客戶各自有著不同的貨物需求,若干個(gè)配送中心向客戶提供貨物,由車隊(duì)負(fù)責(zé)分送貨物,組織適當(dāng)?shù)男熊嚶肪�,目標(biāo)是使得客戶的需求得到滿足,并能在一定的約束下,達(dá)到諸如路程最短、成本最小、耗費(fèi)時(shí)間最少等目的。VRP問(wèn)題在科學(xué)和工程應(yīng)用領(lǐng)域具有非常廣泛的應(yīng)用,很多實(shí)際的物流運(yùn)輸問(wèn)題都可以轉(zhuǎn)化成各種VRP問(wèn)題來(lái)進(jìn)行解決。由于VRP已經(jīng)被證明是NP難的,所以對(duì)于大規(guī)模VRP問(wèn)題往往考慮利用各種智能優(yōu)化算法來(lái)進(jìn)行求解。隨著經(jīng)濟(jì)的發(fā)展、科學(xué)技術(shù)的進(jìn)步以及人們需求的日益多元化,越來(lái)越多實(shí)際應(yīng)用問(wèn)題往往需要考慮多個(gè)優(yōu)化目標(biāo),多目標(biāo)優(yōu)化正在成為近年來(lái)運(yùn)籌學(xué)領(lǐng)域一個(gè)研究熱點(diǎn)。需要注意的是目前關(guān)于多目標(biāo)VRP問(wèn)題的研究文獻(xiàn)并不多,在很多方面尤其是求解算法設(shè)計(jì)方面亟需開展進(jìn)一步深入的研究。本文采納系統(tǒng)工程的思想,利用運(yùn)籌學(xué)、進(jìn)化計(jì)算等領(lǐng)域的相關(guān)研究成果,設(shè)計(jì)和開發(fā)一種能夠有效求解多目標(biāo)VRP問(wèn)題的遺傳算法(Genetic algorithm,GA)。本文的主要內(nèi)容可以歸納如下幾個(gè)方面：(1)相關(guān)工作綜述部分。主要介紹了VRP問(wèn)題及求解算法、多目標(biāo)優(yōu)化理論與方法等方面的研究工作。(2)問(wèn)題建模部分。在給出一般VRP以及帶有時(shí)間窗約束VRP問(wèn)題數(shù)學(xué)模型的基礎(chǔ)上,建立一個(gè)以最小化配送成本和最大化客戶滿意度為目標(biāo)函數(shù)的多目標(biāo)VRP問(wèn)題的數(shù)學(xué)模型。(3)算法設(shè)計(jì)部分。研究一般VRP問(wèn)題的求解算法,考慮到編碼和解碼是求解VRP問(wèn)題的GA設(shè)計(jì)中所面臨的主要挑戰(zhàn),對(duì)三種不同編碼方法的有效性進(jìn)行對(duì)比仿真實(shí)驗(yàn)。在上述研究結(jié)論的基礎(chǔ)上,通過(guò)結(jié)合一種經(jīng)典多目標(biāo)進(jìn)化算法(MOEA/D)的相關(guān)思想,提出一種能夠求解多目標(biāo)VRP問(wèn)題的新型多目標(biāo)GA算法。(4)仿真實(shí)驗(yàn)部分。利用一組根據(jù)VRPLIB中標(biāo)準(zhǔn)測(cè)試問(wèn)題構(gòu)造的多目標(biāo)VRP問(wèn)題,對(duì)所提出的多目標(biāo)GA算法進(jìn)行仿真實(shí)驗(yàn)以檢驗(yàn)其性能。此外,還在仿真實(shí)驗(yàn)中分析所提出的算法中關(guān)鍵參數(shù)及算子對(duì)算法性能的影響。(5)結(jié)論部分。對(duì)本文研究的主要工作進(jìn)行總結(jié),指出存在的不足之處,并對(duì)下一步的研究工作進(jìn)行展望。
[Abstract]:Vehicle routing problem (VRP) is a classic operational research problem. It means that several customers have different goods needs, several distribution centers provide goods to customers, and the team is responsible for distributing goods and organizing proper traffic route. The goal is to make customers meet the needs and can be certain. Under the constraints, the.VRP problem, such as the shortest path, the least cost, and the least time consuming, has a very wide application in the field of science and engineering applications. Many practical logistics and transportation problems can be transformed into various VRP problems to be solved. Because VRP has been proved to be difficult for NP, so the problem of large-scale VRP problem is bound to With the development of economy, the progress of science and technology and the increasing diversity of people's needs, more and more practical applications often need to consider multiple optimization targets. Multi objective optimization is becoming a hot topic in the field of operational research in recent years. There are few research literatures on the multi-objective VRP problem, and in many aspects, especially the design of solving algorithms, we need to carry out further research. This paper adopts the idea of system engineering, and designs and develops a genetic algorithm (Ge), which can effectively solve the multi-objective VRP problem by using the related research results in the fields of operational research, evolutionary computation and so on. Netic algorithm, GA). The main contents of this paper can be summed up as follows: (1) a summary of the related work. It mainly introduces the research work of the VRP problem and the solving algorithm, the theory and method of multi-objective optimization. (2) the modeling part of the problem is based on the mathematical model of the general VRP and the VRP problem with time window constraints. In order to minimize the cost of distribution and maximize customer satisfaction as the objective function, a mathematical model for the multiobjective VRP problem is established. (3) the algorithm design part. The algorithm of solving the general VRP problem is studied. The main challenge in the GA design for solving the VRP problem is the encoding and decoding, and the effectiveness of the three different coding methods is given. On the basis of the above conclusions, a new multi-objective GA algorithm which can solve the multi-objective VRP problem is proposed on the basis of the relevant ideas of a classical multi-objective evolutionary algorithm (MOEA/D). (4) the simulation experiment part. A set of multi-objective VRP problems which are constructed according to the standard test problem in VRPLIB is proposed. The multi objective GA algorithm is simulated to test its performance. In addition, the influence of the key parameters and operators in the proposed algorithm on the performance of the algorithm is also analyzed. (5) conclusion part. The main work of this paper is summarized, the shortcomings of the existing research are pointed out, and the next step of the research work is prospected.

【學(xué)位授予單位】：東北大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：U116.2;TP18

【參考文獻(xiàn)】

相關(guān)期刊論文 前7條

1 肖曉偉;肖迪;林錦國(guó);肖玉峰;;多目標(biāo)優(yōu)化問(wèn)題的研究概述[J];計(jì)算機(jī)應(yīng)用研究;2011年03期

2 馬磊;;車輛路徑問(wèn)題(VRP)算法研究[J];電腦知識(shí)與技術(shù);2009年19期

3 公茂果;焦李成;楊咚咚;馬文萍;;進(jìn)化多目標(biāo)優(yōu)化算法研究[J];軟件學(xué)報(bào);2009年02期

4 李家齊;;VRP求解的有效途徑研究[J];中國(guó)物流與采購(gòu);2008年16期

5 劉云忠,宣慧玉;車輛路徑問(wèn)題的模型及算法研究綜述[J];管理工程學(xué)報(bào);2005年01期

6 鄒彤,李寧,孫德寶;不確定車輛數(shù)的有時(shí)間窗車輛路徑問(wèn)題的遺傳算法[J];系統(tǒng)工程理論與實(shí)踐;2004年06期

7 魏明,高成修,胡潤(rùn)洲;一種帶時(shí)間窗和容量約束的車輛路線問(wèn)題及其TabuSearch算法[J];運(yùn)籌與管理;2002年03期

，

本文編號(hào)：1785185