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

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

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

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