具有時(shí)間窗的集送貨VRP問(wèn)題的并行算法研究.pdf

1、在經(jīng)濟(jì)全球化和信息化的推動(dòng)下，現(xiàn)代物流已從為社會(huì)提供傳統(tǒng)運(yùn)輸服務(wù)，擴(kuò)展到以現(xiàn)代科技為支柱的綜合物流系統(tǒng)。為了降低物流運(yùn)輸企業(yè)的成本，提高運(yùn)作效率，全面提高客戶(hù)滿(mǎn)意度，車(chē)輛調(diào)度與路徑優(yōu)化問(wèn)題越來(lái)越受到人們的關(guān)注。
　　 本文首先回顧了國(guó)內(nèi)外有關(guān)車(chē)輛路徑問(wèn)題（VRP）的研究成果，對(duì)VRPSDP和VRPTW的基本概念、主要分類(lèi)、研究的發(fā)展和現(xiàn)狀進(jìn)行了系統(tǒng)、詳細(xì)的介紹，并指出了目前研究中存在的問(wèn)題。針對(duì)這些問(wèn)題，本文做了以下幾方面的工作

2、：
　　 設(shè)計(jì)了帶有時(shí)間窗約束的VRPSDP（VRPTWSDP）的并行分枝定價(jià)算法。根據(jù)所使用并行開(kāi)發(fā)工具的特點(diǎn)，在搜索樹(shù)構(gòu)造的層次上以主從式策略實(shí)現(xiàn)了分枝定價(jià)算法的并行化。利用雙向動(dòng)態(tài)規(guī)劃算法求解作為定價(jià)子問(wèn)題的帶有時(shí)間和容量?jī)深?lèi)資源約束的最短路徑問(wèn)題。根據(jù)VRPTWSDP的特點(diǎn)，開(kāi)發(fā)了按時(shí)間資源進(jìn)行分枝的方法，并在實(shí)驗(yàn)中與完全按弧分枝的方法在計(jì)算效果上進(jìn)行了對(duì)比。在并行分枝定價(jià)算法求解VRPTWSDP實(shí)例的有效性實(shí)驗(yàn)中，詳細(xì)

3、分析了算法并行化對(duì)生成的節(jié)點(diǎn)數(shù)、加速比和相對(duì)加速比的影響。以AHGA和CGPGA為基礎(chǔ)，設(shè)計(jì)了VRPTWSDP的串、并行遺傳算法。
　　 設(shè)計(jì)了求解VRPSDP的粗粒度并行遺傳算法（CGPGA）。并行算法以單向環(huán)作為連接拓?fù)?，各子群體獨(dú)立進(jìn)行遺傳操作，遷移算子用于群體間的信息交流，采用多樣性替換的方法進(jìn)行個(gè)體替換。本文給出了CGPGA算法在集群系統(tǒng)上的重復(fù)非阻塞MPI實(shí)現(xiàn)。對(duì)典型VRPSDP實(shí)例進(jìn)行測(cè)試的結(jié)果表明，該遺傳算法能較