帶時(shí)間窗的車輛路徑問題的研究與應(yīng)用.pdf

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

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