帶時間窗的車輛路徑問題的研究與應用.pdf

1、車輛路徑問題是研究如何優(yōu)化物流運輸?shù)暮诵膯栴}。研究車輛路徑問題對于降低物流公司的運輸成本，提高物流公司的服務質量都有重要意義。
　　本文重點研究了帶時間窗的車輛路徑問題。針對在物流運輸中的實際情況，本文提出了一種新的帶時間窗車輛路徑問題的雙目標規(guī)劃模型。第一個優(yōu)化目標是使配送過程中總的車輛使用數(shù)目最小。在實際的貨物運輸中，由于汽車的油箱容量限制、司機的工作時間等，配送車輛的行駛距離往往會受到限制。因此，在每輛車都有行駛距離限制的約

2、束下，用最少的車輛來完成配送任務能最大程度的節(jié)約運輸成本。此外，本文考慮了每個用戶都有自己的期望服務時間。盡可能的使得顧客在自己期望時間內被服務，從而提高物流公司的服務滿意度，這是本文提出的規(guī)劃模型的另一個優(yōu)化目標。基于上述的規(guī)劃模型，本文提出了一種雙標準近似算法。該算法可以在多項式時間內給出上述問題的近似最優(yōu)解。本文通過嚴格的理論分析證明了該算法的近似比為（O(log1/ε),1+ε），并通過模擬實驗分析了算法的運行效率。