本文選題：車輛救援 + 弧路線問題　； 參考：《南京農(nóng)業(yè)大學(xué)》2015年碩士論文

【摘要】：在已有帶容量荷載的弧路線問題中,車輛從場站出發(fā),按照一定的行駛規(guī)則,服務(wù)所有的客戶,最終回到場站。而在以故障車輛救援為(Rescue ofbreakdown vehicles,RBV)背景的研究中,共有兩類客戶,分別為點(diǎn)客戶(Node Customer)和弧客戶(Arc Customer)。其中點(diǎn)客戶僅需要送油、送電等不需要移動故障車輛的服務(wù);弧客戶則需要救援車輛將故障車輛從故障現(xiàn)場拖至相應(yīng)維修點(diǎn)的服務(wù),并且每位客戶擁有各自的響應(yīng)時(shí)間要求。本文在這樣的背景下,提出了一種故障車輛救援中的多場站點(diǎn)弧混合路線問題(Multi-depot arc-node routing problem in the rescue of breakdown vehicles,MDANRPRBV)。在此問題中,車輛需要從數(shù)個場站中出發(fā),在車輛最大工作時(shí)間的約束下,按照每個客戶不同的響應(yīng)時(shí)間需求,對兩類客戶提供不同的服務(wù),最終完成后回到出發(fā)時(shí)的場站,目標(biāo)是找出運(yùn)行費(fèi)用最小的路線安排。由于該問題屬于NP-hard問題,本文提出用螢火蟲算法求解。首先,利用一種基于輪盤賭的節(jié)約算法,構(gòu)建出螢火蟲算法的初始解種群集合;其次基于優(yōu)化方向與步長的思想對解的特征值進(jìn)行定義,設(shè)計(jì)確定步長的方法,最后采用貪婪式的移除-插入算法對亮度低的螢火蟲進(jìn)行改進(jìn)并獲得最優(yōu)化的解。本文首先利用小規(guī)模的測試算例,利用CPLEX軟件得到算例的解和最優(yōu)目標(biāo)值,與本文提出的算法得到的解和最優(yōu)目標(biāo)值進(jìn)行比較,驗(yàn)證了數(shù)學(xué)模型的正確性。隨后,本文利用經(jīng)典集散貨物運(yùn)輸問題(Pickup and Delivery Problem,PDP)實(shí)驗(yàn)算例進(jìn)行修正與完善,構(gòu)建出適用于本文的實(shí)驗(yàn)數(shù)據(jù),將本文提出的螢火蟲算法與貪婪式的移除-插入算法以及CPLEX軟件在2小時(shí)內(nèi)得到的最好解進(jìn)行比較,驗(yàn)證算法有效性。實(shí)驗(yàn)結(jié)果表明,本文提出的螢火蟲算法在解決中等規(guī)模的MDANRPRBV問題時(shí),優(yōu)化結(jié)果與貪婪式的移除-插入算法相比,解的平均質(zhì)量有6.57%的改進(jìn);螢火蟲算法的優(yōu)化結(jié)果比CPLEX的得到的優(yōu)化結(jié)果平均改進(jìn)6.69%,且解的方差維持在20左右,說明算法穩(wěn)定性較強(qiáng)。算法平均運(yùn)行時(shí)間為20.23分鐘,遠(yuǎn)低于CPLEX軟件2小時(shí)的運(yùn)算時(shí)間。本文提出的算法可以為道路救援企業(yè)決策者提供理論支持,使企業(yè)在保證客戶滿意度的基礎(chǔ)上,降低運(yùn)營成本,提高救援效率。
[Abstract]:In the existing arc route problem with capacity load, the vehicle starts from the station, serves all the customers according to certain driving rules, and finally returns to the station. There are two types of customers, one is Node customer, the other is Arc customer. Some customers only need to send oil, power transmission and other services do not need mobile vehicles; arc customers need to rescue vehicles from the fault site to the service of the corresponding maintenance point, and each customer has their own response time requirements. Based on this background, this paper presents a multi-site arc hybrid route problem in vehicle rescue with multi-depot arc-node routing problem in the rescue of breakdown vehicle (MDANRPRBV). In this problem, the vehicle needs to start from several stations, under the constraint of the maximum working time of the vehicle, according to the different response time needs of each customer, provide different services to the two types of customers, and return to the starting station after the final completion. The goal is to find out which route is the least expensive. Since the problem belongs to NP-hard problem, this paper proposes a firefly algorithm to solve the problem. Firstly, the initial solution population set of the firefly algorithm is constructed by using a saving algorithm based on roulette. Secondly, the eigenvalue of the solution is defined based on the idea of optimization direction and step size, and the method of determining the step size is designed. Finally, the greedy removal-insertion algorithm is used to improve the low brightness firefly and obtain the optimal solution. In this paper, a small scale test example is first used to obtain the solution and optimal target value of the example by using CPLEX software, which is compared with the solution and the optimal target value obtained by the proposed algorithm, and the correctness of the mathematical model is verified. Then, the experimental example of Pickup and delivery problem (PDP) is used to modify and perfect the experimental data, which is suitable for this paper. The proposed firefly algorithm is compared with the greedy removal-insert algorithm and the best solution obtained by CPLEX software within 2 hours. The validity of the algorithm is verified. The experimental results show that the average quality of the solution is improved by 6.57% compared with the greedy removal and insertion algorithm in solving the medium scale MDANRPRBV problem. The optimization result of the firefly algorithm is 6.69 better than that obtained by CPLEX, and the variance of the solution is about 20, which indicates that the algorithm is stable. The average running time of the algorithm is 20.23 minutes, which is much lower than that of CPLEX software in 2 hours. The algorithm proposed in this paper can provide theoretical support for the decision-makers of road rescue enterprises, and make enterprises reduce operating costs and improve rescue efficiency on the basis of ensuring customer satisfaction.
【學(xué)位授予單位】：南京農(nóng)業(yè)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：U472;U492.22

【參考文獻(xiàn)】

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

1 陳榮章;任寶衛(wèi);張吉;;汽車道路救援服務(wù)網(wǎng)絡(luò)布局研究[J];上海汽車;2014年10期

2 陳榮章;張吉;;國內(nèi)汽車道路救援發(fā)展模式研究[J];上海汽車;2013年04期

3 蔣麗;丁斌;臧曉寧;;基于干擾管理的車輛故障救援模型[J];系統(tǒng)工程;2010年06期

4 李小花;朱征宇;夏夢霜;;多車場CARP問題的改進(jìn)遺傳算法求解[J];計(jì)算機(jī)工程與應(yīng)用;2009年11期

，

本文編號：2002253