VRP和制造網(wǎng)絡(luò)流算法的研究.pdf

1、VRP問題是為固定的車輛集,設(shè)計一些起始于中心站的路徑,要求在顧客的需求已知,且每一個顧客最多被服務(wù)一次,車的裝載量不允許超過車輛容量的情況下,使總費用最小.VRP在大規(guī)模物資調(diào)運、勞務(wù)人員的任務(wù)分配等方面具有重要的使用價值.當(dāng)VRP的一些量為隨機變量時,車輛路徑問題就轉(zhuǎn)化為隨機車輛路徑問題(SVRP).如需求、時間是隨機變量,或者每一個顧客以一個概率p<,i>出現(xiàn)等.在SVRP模型中我們希望車輛旅行的期望費用值(期望路徑總長度)最小.

2、制造網(wǎng)絡(luò)流問題用于解決水源的調(diào)度及工廠的產(chǎn)品運輸、分配、合成等問題.該文首先提出一個新的VRP模型及其啟發(fā)式算法.并證明了在距離約束的VRP情形下對于目標(biāo)函數(shù)MV(車輛數(shù)最小),其任一有多項式時間的啟發(fā)式算法H得到的車輛數(shù)目K<'H>和最優(yōu)車輛數(shù)目K<'V>滿足關(guān)系K<'H>/K<'V>≥2,我們還給出了MD(總距離最小)的一個動態(tài)規(guī)劃算法.對隨機車輛路徑問題,該文給出了一個基于隨機需求的SVRP的禁忌算法,并提出了基于這種模型的車輛旅