VRP和制造網絡流算法的研究.pdf

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

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