【摘要】：限量弧路由問(wèn)題(Capacitated Arc Routing Problem,CARP)在現(xiàn)實(shí)生活中有著廣泛的應(yīng)用,對(duì)緩解能源危機(jī),提高生產(chǎn)效率,創(chuàng)建節(jié)約型社會(huì)有著重大的意義。然而,許多實(shí)際問(wèn)題是無(wú)法用基本CARP模型解決的,因此結(jié)合實(shí)際情況,增加約束條件形成的擴(kuò)展CARP模型越來(lái)越受到人們的重視。目前有許多的擴(kuò)展CARP模型被提出,如多中心CARP模型,多車型CARP模型(Heterogeneous Vehicle Capacitated Arc Routing Problem,HVCARP),多周期CARP模型,不確定CARP模型等等。基本限量弧路由問(wèn)題模型的研究已經(jīng)日漸成熟,但是擴(kuò)展CARP模型相關(guān)的研究成果并不是很多。本論文就常見(jiàn)擴(kuò)展CARP模型中的多車型CARP模型做了深入的研究。針對(duì)多車型CARP模型(HVCARP)提出了一種有效的Memetic算法MAEVSGR(Memetic Algorithm Exchanging Vehicles among Same Group Routes)。首先將多車型CARP模型(HVCARP)的路徑費(fèi)用分為可變費(fèi)用和固定費(fèi)用,通過(guò)車輛懲罰系數(shù)緊密聯(lián)系車型和路徑之間的關(guān)系,形成了特有的多車型CARP費(fèi)用計(jì)算公式。針對(duì)多車型CARP的特點(diǎn),本論文提出了一種針對(duì)車型的同檔路徑交換車輛算子,該算子根據(jù)路徑負(fù)載以及車隊(duì)情況,調(diào)整服務(wù)車型,以實(shí)現(xiàn)服務(wù)費(fèi)用的最優(yōu)化;然后以其為局部搜索算子,設(shè)計(jì)了用于求解多車型CARP的Memetic算法;然后,以CARP標(biāo)準(zhǔn)測(cè)試集的修改算例進(jìn)行實(shí)驗(yàn)驗(yàn)證,大量的實(shí)驗(yàn)結(jié)果表明了本文所提基于同檔路徑交換車輛算子Memetic算法的有效性。針對(duì)不確定CARP模型,本論文先描述了基本不確定CARP模型的定義方法。然后介紹了幾種常見(jiàn)的不確定評(píng)價(jià)標(biāo)準(zhǔn)。最后結(jié)合多車型CARP模型提出了不確定多車型CARP模型。
[Abstract]:The limited-arc routing problem (CARP) has a wide application in real life. It is of great significance to alleviate the energy crisis, improve the production efficiency and create an economical society. However, many practical problems can not be solved by the basic CARP model, so the extended CARP model, which is formed by adding the constraint conditions, is more and more important to people. There are many extended CARP models, such as the multi-center CARP model, the multi-model CARP model, the multi-cycle CARP model, the CARP model and so on. The research on the basic limit arc routing problem model is becoming more and more mature, but the research results related to the extension of the CARP model are not much. This paper makes an in-depth study of the multi-model CARP model in the common extended CARP model. A valid Memetic algorithm MAEVSGR is proposed for the multi-model CARP model (HVCARP). First, the route cost of the multi-model CARP model (HVCARP) is divided into the variable cost and the fixed cost, and the relationship between the vehicle model and the route is closely connected through the vehicle penalty coefficient, and the specific multi-model CARP cost calculation formula is formed. In view of the characteristics of the multi-model CARP, this paper presents a vehicle operator with the same gear path for the model, which is based on the path load and the vehicle fleet, and the service model is adjusted so as to realize the optimization of the service cost; and then it is a local search operator. In this paper, a Memetic algorithm for solving the multi-model CARP is designed, and the experimental verification is carried out with the modified example of the CARP standard test set. In order not to determine the CARP model, the definition method of the CARP model is described in this paper. Several common uncertain evaluation criteria are then presented. Finally, a multi-model CARP model is proposed in combination with the multi-model CARP model.
【學(xué)位授予單位】：安慶師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：U491

【參考文獻(xiàn)】

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

1 劉天堂;江志斌;耿娜;劉冉;劉樹(shù)軍;;帶有異質(zhì)固定車隊(duì)的能力約束弧路徑問(wèn)題[J];上海交通大學(xué)學(xué)報(bào);2012年11期

2 金倩倩;林丹;;求解UCARPP問(wèn)題的變鄰域搜索算法[J];計(jì)算機(jī)工程;2012年21期

3 段淵;向毅;;不同遺傳算子組合求解TSP問(wèn)題的比較研究[J];科技通報(bào);2012年05期

4 胡珊;林丹;;求解CARP-RP-ML問(wèn)題的改進(jìn)算法[J];計(jì)算機(jī)工程;2012年07期

5 徐凱;朱征宇;;改進(jìn)遺傳算法對(duì)帶服務(wù)時(shí)間約束的弧路徑問(wèn)題的求解[J];微處理機(jī);2010年05期

6 金毅;;對(duì)“中國(guó)郵遞員問(wèn)題”的數(shù)理分析[J];科技經(jīng)濟(jì)市場(chǎng);2009年03期

7 朱征宇;楊永;鄧欣;謝志華;夏夢(mèng)霜;李小花;;一種求解多車型CARP問(wèn)題的高效進(jìn)化算法[J];計(jì)算機(jī)工程與應(yīng)用;2008年08期

8 孫海雷;劉瓊蓀;胡上尉;;TSP問(wèn)題的順序插入交叉算子[J];計(jì)算機(jī)工程與應(yīng)用;2007年08期

9 李念祖;;關(guān)于中國(guó)郵遞員問(wèn)題的最優(yōu)完全子圖算法[J];上海師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年04期

10 魏平,李利杰,熊偉清;求解TSP問(wèn)題的一種混合遺傳算法[J];計(jì)算機(jī)工程與應(yīng)用;2005年12期

相關(guān)博士學(xué)位論文 前1條

1 梅一;基于元啟發(fā)式方法對(duì)限量弧路由問(wèn)題的求解[D];中國(guó)科學(xué)技術(shù)大學(xué);2010年

，

本文編號(hào)：2484002