帶時間窗車輛路徑問題的多目標文化基因算法＊

王 君

（天津財經(jīng)大學(xué)商學(xué)院，天津300222）

1 引言

隨著顧客對物流配送要求的提高，帶時間窗的車輛路徑問題VRPTW（Vehicle Routing Problem with Time Windows）一直是物流與供應(yīng)鏈管理的熱點問題。VRPTW是典型的組合優(yōu)化問題，主要采用啟發(fā)式優(yōu)化算法進行求解。啟發(fā)式算法分為以禁忌搜索TS（Tabu Search）［1］為代表的局部搜索和以遺傳算法GA（Genetic Algorithm）［2］為代表的種群搜索兩大類。現(xiàn)在更加趨向于多種搜索機制的結(jié)合，以彌補單一啟發(fā)式算法的不足。

文化基因算法MA（Memetic Algorithm）是以文化進化思想為指導(dǎo)的智能優(yōu)化算法，用局部搜索來模擬文化進化過程，既具有群體算法搜索范圍大的優(yōu)點，又具有局部算法搜索的深度優(yōu)勢［3］，目前已經(jīng)出現(xiàn)了用MA求解車輛路徑問題的研究［4］。多目標文化基因算法MOMA（Multi－Objective MA）是采用多目標優(yōu)化機制的MA算法，已經(jīng)成功應(yīng)用到車間調(diào)度［5］、物流網(wǎng)絡(luò)設(shè)計［6］、飛機航線調(diào)度［7］等多目標優(yōu)化問題中。

VRPTW需要同時考慮車輛的使用數(shù)和車輛行駛距離兩個目標，因此它也是一個多目標優(yōu)化問題，現(xiàn)有研究大部分采用多目標進化算法求Pareto最優(yōu)解集［8，9］，然而用MOMA解決VRPTW的研究十分罕見。本文基于以上研究成果，提出求解VRPTW的一種MOMA算法，運用不同的適應(yīng)度函數(shù)分別支持種群和局部精英解的選擇。對國際通用的benchmark數(shù)據(jù)進行仿真對比實驗，表明本文提出的MOMA算法是求解VRPTW問題的有效方法。

2 問題描述與數(shù)學(xué)模型

一個VRPTW描述為：設(shè)G＝｛I，E｝為一個完備的無向圖，其中，I＝｛0，1，2，…，n｝為節(jié)點集；E＝｛i，j｝為邊集，i，j∈I且i≠j。0代表車庫點，其余為顧客點，一隊具有相同裝載能力的車輛從車庫點出發(fā)，實現(xiàn)對所有顧客點的配送服務(wù)，最終回到車庫。……