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

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

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

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