本文關(guān)鍵詞：半平面集聚點(diǎn)群TSP幾何方法及其在物流路徑優(yōu)化中的應(yīng)用，由筆耕文化傳播整理發(fā)布。

【摘要】：隨著電子商務(wù)技術(shù)的蓬勃發(fā)展,物流配送已成為國民經(jīng)濟(jì)新興產(chǎn)業(yè),車輛優(yōu)化調(diào)度是物流配送的重要內(nèi)容,物流路徑規(guī)劃是車輛優(yōu)化調(diào)度的基礎(chǔ)。路徑規(guī)劃屬于旅行商問題(Traveling Salesman Problem),從圖論的角度看,是在加權(quán)圖中尋找最優(yōu)哈密爾頓回路問題,常用的方法有最鄰近法、最小樹生成法、最小權(quán)匹配法以及改良圈算法等,這些都是一種近似算法,在圖論中還不能用理論證明某種算法所求取的哈密爾頓回路最優(yōu),被歸屬于組合優(yōu)化領(lǐng)域中的NP難題(Non-deterministic Polynomial),當(dāng)前主要集中于采用優(yōu)化方法求解,如模擬退火、遺傳算法、進(jìn)化計(jì)算、粒子群、螞蟻群等方法,研究對象均是任意的有向圖,未能結(jié)合物流配送目標(biāo)門店的空間分布。因此,研究適用于解決實(shí)際生產(chǎn)活動(dòng)中的物流路徑規(guī)劃問題的方法具有重要意義。在實(shí)際物流配送實(shí)踐中,發(fā)現(xiàn)物流配送具有受車輛裝載容積限制、單次配送門店數(shù)量少、門店相對聚集的特點(diǎn)。依據(jù)圖論生成哈密爾頓環(huán)的相關(guān)理論,簡化物流配載數(shù)學(xué)模型,定義了半平面聚集點(diǎn)群概念,提出了半平面集聚點(diǎn)群TSP幾何求解方法,方法基本出發(fā)點(diǎn)是:以頂點(diǎn)距離作為權(quán)的加權(quán)圖,生成圖的哈密爾頓環(huán)與頂點(diǎn)的空間分布有關(guān),實(shí)際生產(chǎn)環(huán)境中約束圖頂點(diǎn)的空間分布會簡化TSP的求解。半平面集聚點(diǎn)群TSP幾何方法具體做法是:做點(diǎn)群平分線,從點(diǎn)群中找到距離源頂點(diǎn)最遠(yuǎn)的頂點(diǎn),距離為l,以l為長度在角平分線上作點(diǎn)v_f,選擇離點(diǎn)v_f最近的頂點(diǎn)和源頂點(diǎn)形成初始線路,其他各點(diǎn)加入次序?yàn)?加入后使得初始線路的增長量最大,以加入后增加的距離最少最近確定加入回路或去路。從理論上證明了由該方法生成的回路是哈密爾頓環(huán),分析了方法的合理性;給出了方法的程序?qū)崿F(xiàn),計(jì)算了算法的復(fù)雜度;討論了方法應(yīng)用于物流路徑規(guī)劃過程中,出現(xiàn)的不滿足半平面聚集點(diǎn)群的各種情況,提出了分解點(diǎn)群由多個(gè)哈密爾頓環(huán)組合形成回路的解決方案。半平面集聚點(diǎn)群TSP幾何方法通過理論分析以及與貪婪算法、遺傳算法對比實(shí)驗(yàn)驗(yàn)證,有如下結(jié)論:(1)方法利用了頂點(diǎn)空間分布特征,算法復(fù)雜度較低;(2)對于半平面聚集點(diǎn)群,方法所生成的回路是較優(yōu)的哈密爾頓環(huán),方法具有較高的精度和穩(wěn)定性,能適用于實(shí)際的物流路徑規(guī)劃。半平面集聚點(diǎn)群TSP幾何方法針對物流路徑規(guī)劃特點(diǎn),利用圖的頂點(diǎn)空間分布特征,簡化數(shù)學(xué)模型,較好地解決了物流路徑規(guī)劃問題。
【關(guān)鍵詞】：半平面集聚點(diǎn)群 旅行商問題 幾何方法 物流路徑規(guī)劃
【學(xué)位授予單位】：湖南科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：U116.2;F252
【目錄】：

• 摘要5-6
• ABSTRACT6-10
• 第1章 緒論10-16
• 1.1 研究背景和意義10-11
• 1.1.1 研究背景10
• 1.1.2 研究意義10-11
• 1.2 國內(nèi)外研究現(xiàn)狀11-13
• 1.3 研究內(nèi)容和論文結(jié)構(gòu)13-16
• 1.3.1 研究內(nèi)容13-14
• 1.3.2 論文結(jié)構(gòu)14-16
• 第2章 物流路徑規(guī)劃理論基礎(chǔ)16-28
• 2.1 圖論基礎(chǔ)16-21
• 2.1.1 基本概念16-18
• 2.1.2 哈密爾頓環(huán)18-21
• 2.2 TSP常用求解方法21-26
• 2.2.1 貪婪算法22-24
• 2.2.2 遺傳算法24-26
• 2.3 本章小結(jié)26-28
• 第3章 半平面集聚點(diǎn)群TSP幾何求解方法28-38
• 3.1 半平面集聚點(diǎn)群28-29
• 3.2 幾何求解方法29-35
• 3.2.1 算法思想29-30
• 3.2.2 算法詳細(xì)步驟30-35
• 3.2.3 算法理論依據(jù)35
• 3.3 算法時(shí)間復(fù)雜度35-36
• 3.4 本章小結(jié)36-38
• 第4章 TSP幾何求解方法在物流路徑規(guī)劃中的應(yīng)用38-64
• 4.1 物流路徑規(guī)劃實(shí)現(xiàn)38-43
• 4.1.1 數(shù)據(jù)組織39-42
• 4.1.2 地圖渲染42
• 4.1.3 實(shí)現(xiàn)效果42-43
• 4.2 門店分布特征分類及處理方法43-52
• 4.2.1 門店集聚分布的區(qū)域43-44
• 4.2.2 門店分布在倉庫兩側(cè)的區(qū)域44-47
• 4.2.3 初始途徑點(diǎn)分布在派車區(qū)域集聚點(diǎn)群邊界上47-52
• 4.3 實(shí)驗(yàn)對比與分析52-63
• 4.3.1 貪婪算法路徑規(guī)劃實(shí)驗(yàn)52-54
• 4.3.2 遺傳算法路徑規(guī)劃實(shí)驗(yàn)54-56
• 4.3.3 實(shí)驗(yàn)結(jié)果對比與分析56-63
• 4.4 本章小結(jié)63-64
• 第5章 結(jié)論和展望64-66
• 5.1 主要研究成果及創(chuàng)新點(diǎn)64
• 5.2 后續(xù)工作64-66
• 參考文獻(xiàn)66-70
• 致謝70-72
• 附錄A：攻讀碩士學(xué)位期間的研究成果72

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 張偉;;基于蟻群算法的物流配送中車輛路徑優(yōu)化問題研究[J];物流科技;2015年10期

2 董妍汝;;基于選擇算子的遺傳算法改進(jìn)[J];辦公自動(dòng)化;2015年16期

3 李金旭;黃悅悅;;求解TSP的貪心模擬退火算法[J];河南工程學(xué)院學(xué)報(bào)(自然科學(xué)版);2015年01期

4 蘇曉勤;孫鶴旭;潘旭華;;改進(jìn)蜂群算法的旅行商問題仿真[J];計(jì)算機(jī)工程與設(shè)計(jì);2013年04期

5 傅剛;;PSO-TSP問題綜述[J];黑龍江科技信息;2012年31期

6 馬冬青;王蔚;;基于改進(jìn)粒子群算法的物流配送車輛調(diào)度[J];計(jì)算機(jī)工程與應(yīng)用;2014年11期

7 趙吉東;;蟻群算法的改進(jìn)策略研究[J];中國科技信息;2012年12期

8 劉紅軍;趙帥;趙雷;;一種基于GA-SA-TS算法的車間調(diào)度方法的研究[J];制造技術(shù)與機(jī)床;2012年03期

9 杜占瑋;楊永健;孫永雄;張池軍;;基于互信息的混合蟻群算法及其在旅行商問題上的應(yīng)用[J];東南大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年03期

10 趙宜鵬;孟磊;彭承靖;;遺傳算法原理與發(fā)展方向綜述[J];黑龍江科技信息;2010年13期

  本文關(guān)鍵詞：半平面集聚點(diǎn)群TSP幾何方法及其在物流路徑優(yōu)化中的應(yīng)用，，由筆耕文化傳播整理發(fā)布。

本文編號：271514