【摘要】：物流作為企業(yè)“第三利潤(rùn)源泉”的一部分一直深受企業(yè)的重視,而車輛路徑問(wèn)題作為物流管理領(lǐng)域中關(guān)注的熱點(diǎn)問(wèn)題,因?yàn)樗膹?fù)雜性和多樣性,如何合理地安排車輛和它們的行駛路徑以最低成本收送貨物,是一個(gè)極具有挑戰(zhàn)性的問(wèn)題,自從1959年被提出以來(lái)引起了無(wú)數(shù)國(guó)內(nèi)外學(xué)者的研究。隨著電子商務(wù)的發(fā)展,物流在企業(yè)中的地位進(jìn)一步提升,本文從電子商務(wù)企業(yè)的實(shí)際應(yīng)用出發(fā),對(duì)車輛路徑問(wèn)題進(jìn)行研究。通過(guò)研究車輛路徑問(wèn)題(Vehicle Routing Problem,VRP)的一般模型,在對(duì)電子商務(wù)下的車輛路徑問(wèn)題進(jìn)行分析的基礎(chǔ)上,提出了一種基于客戶滿意度的多對(duì)多的帶時(shí)間窗的集收送貨一體的車輛調(diào)度問(wèn)題(Multi-multi Pickup and Delivery Vehicle Routing Problem with Time WindowsbasedonSatisfaction,MMPDVRPTWS)。本文主要從兩方面對(duì)車輛路徑問(wèn)題進(jìn)行了研究:靜態(tài)車輛調(diào)度和動(dòng)態(tài)車輛調(diào)度。本文首先分析了 MMPDVRPTWS的靜態(tài)情況,即在進(jìn)行配送前所有的顧客需求是已知的,在配送過(guò)程中路徑信息也不會(huì)改變。本文采用兩階段法對(duì)這個(gè)問(wèn)題進(jìn)行了求解,先用一種插入式啟發(fā)算法將顧客按照其需求和位置信息進(jìn)行分組,然后用一種混合遺傳算法對(duì)路徑進(jìn)行優(yōu)化。通過(guò)對(duì)遺傳算法的研究,發(fā)現(xiàn)該算法由于其固有的特點(diǎn),容易陷入局部收斂,導(dǎo)致局部最優(yōu)解的出現(xiàn)。本文采用一種局部搜索算法作為遺傳算法的變異算子,能夠很好地防止局部最優(yōu)解的出現(xiàn)。最后,通過(guò)實(shí)驗(yàn)討論了適應(yīng)度函數(shù)中目標(biāo)加權(quán)值的設(shè)置,并在加權(quán)值相同的情況下與普通遺傳算法的結(jié)果比較,本文提出的混合遺傳算法在求解方面具有一定的優(yōu)越性。接著分析了MMPDVRPTWS的動(dòng)態(tài)情況,由于隨著時(shí)間的推移,在車輛調(diào)度過(guò)程中會(huì)伴隨著新的客戶請(qǐng)求、客戶請(qǐng)求的修改或取消等多種動(dòng)態(tài)事件,同時(shí)路徑信息的變化也會(huì)影響車輛的速度。本文通過(guò)模擬一個(gè)“工作日”內(nèi)的客戶需求情況,并根據(jù)當(dāng)前的路徑信息對(duì)未來(lái)一段時(shí)間內(nèi)的路徑信息做出預(yù)判,通過(guò)將一個(gè)“工作日”分成若干個(gè)“時(shí)間片”,把一個(gè)“時(shí)間片”內(nèi)產(chǎn)生的訂單再插入到車輛還未完成的序列中,并用上面提到的混合遺傳算法對(duì)路徑進(jìn)行優(yōu)化,通過(guò)實(shí)驗(yàn)驗(yàn)證了動(dòng)態(tài)調(diào)度策略的可行性,并與一種變鄰域搜索算法進(jìn)行對(duì)比,結(jié)果顯示本文提出的算法所求的解具有一定的優(yōu)越性。
[Abstract]:As a part of the third profit source of enterprises, logistics has always been attached great importance to by enterprises, and the vehicle routing problem is a hot issue in the field of logistics management, because of its complexity and diversity. How to reasonably arrange vehicles and their paths to receive and deliver goods at the lowest cost is a very challenging problem, which has been studied by numerous scholars at home and abroad since 1959. With the development of E-commerce, the status of logistics in enterprises is further improved. This paper studies the vehicle routing problem from the practical application of E-commerce enterprises. By studying the general model of vehicle routing problem (Vehicle Routing Problem,VRP), based on the analysis of the vehicle routing problem under electronic commerce, This paper presents a many-to-many time-window vehicle scheduling problem (Multi-multi Pickup and Delivery Vehicle Routing Problem with Time WindowsbasedonSatisfaction,MMPDVRPTWS) based on customer satisfaction. In this paper, the vehicle routing problem is studied from two aspects: static vehicle scheduling and dynamic vehicle scheduling. This paper first analyzes the static situation of MMPDVRPTWS, that is, all customer needs are known before distribution, and the path information will not change during the distribution process. In this paper, a two-stage method is used to solve the problem. First, a plug-in heuristic algorithm is used to group customers according to their needs and location information, and then a hybrid genetic algorithm is used to optimize the path. Through the study of genetic algorithm, it is found that the algorithm is easy to fall into local convergence because of its inherent characteristics, resulting in the emergence of local optimal solution. In this paper, a local search algorithm is used as the mutation operator of genetic algorithm, which can prevent the occurrence of local optimal solution. Finally, the setting of target weighting value in fitness function is discussed through experiments, and compared with the results of common genetic algorithm under the same weighted value, the hybrid genetic algorithm proposed in this paper has some advantages in solving the problem. Then, the dynamic situation of MMPDVRPTWS is analyzed. As time goes on, there are many dynamic events in the process of vehicle scheduling, such as new customer request, customer request modification or cancellation, etc. At the same time, the change of the path information will also affect the speed of the vehicle. In this paper, we simulate the customer demand in a "working day" and predict the path information in the future according to the current path information, and divide a "working day" into several "time slices". The order generated in a "time slice" is inserted into the unfinished vehicle sequence, and the hybrid genetic algorithm mentioned above is used to optimize the path. The feasibility of the dynamic scheduling strategy is verified by experiments. Compared with a variable neighborhood search algorithm, the results show that the solution proposed in this paper has some advantages.
【學(xué)位授予單位】：北京郵電大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：F724.6;TP18

【參考文獻(xiàn)】

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

1 王仁民;閉應(yīng)洲;劉阿寧;李杰;;改進(jìn)變鄰域搜索算法求解動(dòng)態(tài)車輛路徑問(wèn)題[J];計(jì)算機(jī)工程與應(yīng)用;2014年02期

2 楊燁;李霞;;具有可調(diào)軟時(shí)間窗的動(dòng)態(tài)車輛調(diào)度問(wèn)題模型及算法[J];物流技術(shù);2013年21期

3 呂雄偉;趙達(dá);李軍;;基于多態(tài)蟻群算法的多目標(biāo)郵政物流車輛路徑問(wèn)題研究[J];計(jì)算機(jī)應(yīng)用研究;2009年06期

4 譚國(guó)真,張永強(qiáng),高文;考慮網(wǎng)絡(luò)流量的最優(yōu)路徑求解模型和算法[J];小型微型計(jì)算機(jī)系統(tǒng);2003年11期

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

1 王曉博;電子商務(wù)下物流配送系統(tǒng)優(yōu)化模型和算法研究[D];哈爾濱工業(yè)大學(xué);2008年

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

1 胡夏云;基于蟻群算法的動(dòng)態(tài)車輛調(diào)度問(wèn)題的研究[D];廣東工業(yè)大學(xué);2013年

，

本文編號(hào)：2418543