【摘要】：限量弧路由問題(Capacitated Arc Routing Problem,CARP)在現(xiàn)實生活中有著廣泛的應(yīng)用,對緩解能源危機,提高生產(chǎn)效率,創(chuàng)建節(jié)約型社會有著重大的意義。然而,許多實際問題是無法用基本CARP模型解決的,因此結(jié)合實際情況,增加約束條件形成的擴展CARP模型越來越受到人們的重視。目前有許多的擴展CARP模型被提出,如多中心CARP模型,多車型CARP模型(Heterogeneous Vehicle Capacitated Arc Routing Problem,HVCARP),多周期CARP模型,不確定CARP模型等等�；鞠蘖炕÷酚蓡栴}模型的研究已經(jīng)日漸成熟,但是擴展CARP模型相關(guān)的研究成果并不是很多。本論文就常見擴展CARP模型中的多車型CARP模型做了深入的研究。針對多車型CARP模型(HVCARP)提出了一種有效的Memetic算法MAEVSGR(Memetic Algorithm Exchanging Vehicles among Same Group Routes)。首先將多車型CARP模型(HVCARP)的路徑費用分為可變費用和固定費用,通過車輛懲罰系數(shù)緊密聯(lián)系車型和路徑之間的關(guān)系,形成了特有的多車型CARP費用計算公式。針對多車型CARP的特點,本論文提出了一種針對車型的同檔路徑交換車輛算子,該算子根據(jù)路徑負(fù)載以及車隊情況,調(diào)整服務(wù)車型,以實現(xiàn)服務(wù)費用的最優(yōu)化;然后以其為局部搜索算子,設(shè)計了用于求解多車型CARP的Memetic算法;然后,以CARP標(biāo)準(zhǔn)測試集的修改算例進行實驗驗證,大量的實驗結(jié)果表明了本文所提基于同檔路徑交換車輛算子Memetic算法的有效性。針對不確定CARP模型,本論文先描述了基本不確定CARP模型的定義方法。然后介紹了幾種常見的不確定評價標(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é)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：U491

【參考文獻】

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

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

2 金倩倩;林丹;;求解UCARPP問題的變鄰域搜索算法[J];計算機工程;2012年21期

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

4 胡珊;林丹;;求解CARP-RP-ML問題的改進算法[J];計算機工程;2012年07期

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

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

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

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

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

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

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

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

，

本文編號：2484002