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

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

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