隨著現(xiàn)代物流行業(yè)的崛起,企業(yè)為了降低運(yùn)輸成本,越來越重視對車輛路徑問題(Vehicle Routing Problem,簡稱 VRP)的研究。弧路徑問題(Arc Routing Problem,簡稱ARP)與VRP問題一樣,同樣有著重要的現(xiàn)實(shí)意義和研究價(jià)值。二者的不同之處在于,VRP以點(diǎn)為服務(wù)對象,而ARP以邊為服務(wù)對象。經(jīng)典的弧路徑問題只有一個(gè)倉庫點(diǎn),但實(shí)際應(yīng)用中的很多問題需要利用多個(gè)倉庫點(diǎn)的弧路徑問題建立數(shù)學(xué)模型。因此,本文研究了多倉庫帶容量約束弧路徑問題(Multi-depot Capacitated Arc Routing Problem,簡稱MCARP),將經(jīng)典的弧路徑問題推廣到更為實(shí)際的多倉庫情形。針對MCARP的不同變形問題,我們提出了近似算法和多項(xiàng)式算法。本文主要分為以下七個(gè)章節(jié)。第一章介紹了研究背景并對組合最優(yōu)化問題進(jìn)行了簡單描述,還闡述了本文相關(guān)問題的最新研究進(jìn)展。第二章描述了本文所涉及的符號和概念。第三章介紹了非固定終點(diǎn)MCARP問題,給定一倉庫點(diǎn)集D,每輛車可從任一倉庫出發(fā),最終可返回至任意倉庫,目的是找到服務(wù)了所有需求邊的若干條路徑,使得總路徑長度最短。將非固定...

【文章頁數(shù)】：44 頁

【學(xué)位級別】：碩士

【部分圖文】：

圖５．?１算法ＭＲＰＰ１的一個(gè)例子??

第１６頁???華東理工大學(xué)碩士學(xué)位論文??：二－…藝??ｉ?ｄ３?ｄ２??（ａ）需求邊集；？和倉庫點(diǎn)集￡）?（ｂ）完全圖Ｇ??ｄｉ?ｄ２?ｃ／３?ｔ?（ｊ２??ｎ３＊?ｎ５?＂３?‘?ｎ５?１??（ｃ）最小權(quán)約束生成森林Ｆ?（ｄ）?Ｆ上奇度點(diǎn)的完美匹配Ｍ??■翁??ｒ？５?Ｖ４?....

本文編號：4013972