nsga2演算法車輛路徑問題

Ⅰ 車輛路徑問題的車輛路徑問題的發展

1959年Dantzig和Ramse首次對閉合式VRP進行了研究，描述的是將汽油送往各個加油站的實際問題，並首次提出了相應的數學規劃模型以及求解演算法。
1964年，Clark和Wright[4]一種對Dantzig-Ramse方法改進的有效的啟發式演算法Clark-Wright節約演算法。
正是由於以上兩篇開創性論文的發表，使得VRP成為運籌學以及組合優化領域的前沿和研究熱點課題。
1969年，Christofides和Eilon應用2-opt[5]和3-opt[6]處理車輛路徑問題。
1970年，提出了兩階段方法求解車輛路徑問題，包括先分組後定路線（clusterfirst-route second）和先定路線後分組（routefirst-cluster second）兩種啟發式策略。
1981年，Fisher和Jaikumar提出以數學規劃為主的最優化方法來處理包含大約50個顧客點的問題,同樣其運算效率是一個亟待解決的問題。同年，Gullen，Jarvis和Ratliff建立了人機互動的啟發式方法。
1981年，Bodin and Golden將眾多的VRP求解方法進行了歸納。分為以下七種：數學解析法（Exact Procere）；人機互動法（Interactive Optimization）；先分群再排路線（Cluster First–Route Second）；先排路線再分群（Route First–Cluster Second）；節省法或插入法（Saving or Insertion）；改善或交換法（Improvement or Exchanges）；數學規劃近似法（Mathematical programming）。
1990年以來，人工智慧方法在解決組合優化問題上顯示出強大功能，在各個領域得到充分應用，很多學者也將人工智慧引入車輛路線問題的求解中，並構造了大量的基於人工智慧的啟發式演算法。 禁忌搜索法（TS）基本上是屬於一種人工智慧型（AI）的局部搜尋方法，Willard首先將此演算法用來求解VRP 。袁慶達[7]等設計了考慮時間窗和不同車輛類型的禁忌演算法，這種演算法主要採用GA方法產生初始解，然後禁忌演算法對初始解優化。模擬退火方法具有收斂速度快，全局搜索的特點，Osman[8]對VRP的模擬退火演算法進行了研究。遺傳演算法具有求解組合優化問題的良好特性，Holland首先採用遺傳演算法（GA）編碼解決VRPTW 問題。現在多數學者採用混合策略，分別採用兩種人工智慧方法進行路線分組和路線優化。Ombuki[9]提出了用GA進行路線分組，然後用TS方法進行路線優化的混合演算法。Bent和Van Hentenryck[10]則首先用模擬退火演算法將車輛路線的數量最小化，然後用大鄰域搜索法（largneighborhood search）將運輸費用降到最低。
綜合過去有關VRP的求解方法，可以將其分為精確演算法（exact algorithm）與啟發式演算法（heuristics），其中精確演算法有分支界限法、分支切割法、集合涵蓋法等；啟發式演算法有節約法、模擬退火法、確定性退火法、禁忌搜尋法、基因演算法、神經網路、螞蟻殖民演算法等。

Ⅱ (轉)車輛路徑問題及行業應用

轉自：吉勍Personal http://www.jiqingip.com/page9001?article_id=96

車輛路徑問題是運行日常操作所需的操作決策的一部分，都是執行層面的優化問題。先決條件如下：通常情況下，已知資源不能在短時間內擴充，因此資源稀缺是無法避免的。此外，還提供了關於需要滿足的需求的詳細信息。決策優化的核心挑戰是在日常基礎上使需求與現有資源相匹配。在這里，必須解決兩個基本的決策任務：（1）必須給需求分配資源，（2）必須制定日程安排。日程安排描述了執行分配任務的順序，以及啟動單個操作的起點。最大的挑戰是確保不超過現有資源，並以最高效率部署這些資源。

問題描述

車輛路徑問題（VRP）是一個組合優化和整數規劃問題（解決的是「為了交付給定的一組客戶，車輛車隊的最佳路線集是什麼？」）。它概括了眾所周知的旅行推銷員問題（TSP）。它最初出現在1959年George Dantzig和John Ramser的論文中《The Truck Dispatching Problem》。這篇論文首先編寫了演算法，並將其應用於汽油交付。通常，這個問題的背景是將位於中央倉庫的貨物交付給已經訂購此類貨物的客戶。該問題的目標是最小化總路由成本。車輛路徑規劃問題在物流領域和生產散枝橘領域的應用非常廣泛。所以在實際應用中也出現了一些在標准問題的基礎上增加了某些變化之後的變型問題。其中較為常見的包括：

1.         CVRP：Capacitated

VRP, 限制配送車輛的承載體積、重量等。

2.         VRPTW：VRP with

Time Windows, 客戶對貨物的送達時間有時間窗要求。

3.         VRPPD：VRP with

Pickup and Delivery, 車輛在配送過程中可以一邊攬收一邊配送，在外賣O2O場景中比較常見。

4.         MDVRP： Multi-Depot

VRP, 配送網路中有多個倉庫，同樣的貨物可以在多個倉庫取貨。

5.         OVRP：Open VRP, 車輛完成配送任務之後不需要返回倉庫。

6.         VRPB： VRP with

backhauls, 車輛完成配送任務之後回程取貨。

車輛路徑問題

模型描述

TSP問題

TSP問題模型的基本思想是，節點集中包含的每個弧（i; j）要麼包含在漢密爾頓路徑中（通過所有N個節點的往返行程），要麼不包含。在提到的第一種情況下，節點j在節點i之後立即被訪問，但是在後一種搭辯情況下，節點j在i離開之後不立即被訪問。 TSP決策問題可以簡化為以下問題：哪些弧形成了請求的哈密頓沖團路徑，哪些弧被忽略了。為了表示這些二元決策，引入了二元決策變數xij（i∈{1，...，N}系列。每個決策變數xij為0或1，xij表示是否為arc（i ; j）是否包含在漢密爾頓路徑中，並且僅當在漢密爾頓路徑中包含arc（i; j）時，才將xij聲明為1；如果不成立，則等於0。d(i,j)表示節點i和節點j之間的距離。

優化目標使所有在哈密頓路徑中的所有弧的行程距離之和最小。約束保證了漢密爾頓迴路經過所有節點，且每個節點只經過一次。後兩條約束保證了漢密爾頓迴路是連續而非中斷的。

VRP問題

標準的車輛路徑規劃問題可以使用如下數據模型的形式描述：

在此公式中，（1），（2），（3）和（5）定義了一個修改的分配問題，約束（4）是子行程消除約束：v（S）是在最佳解決方案中訪問S的所有頂點所需的車輛數量的適當下限。其他變型VRP問題則可以在此模型基礎上做適當的調整。

演算法服務

有很多實際的業務場景，即時配、大件配送、冷鏈配送、門店補貨等，都可以通過VRP問題優化其配送成本。這些業務場景屬於不同的業態，所使用的業務系統也不盡相同，因此構建可靈活配置的VRP演算法服務平台，可達成一次構建，多業務系統調用，多場景應用的效果。

行業應用

克里斯蒂娜在RED SEA BUS

TRAVEL（RSBT）工作。該公司在洪加達地區提供運輸服務。國際旅行社預訂RSBT服務業務，以確保將他們的遊客轉移到他們偏愛的度假區。克里斯蒂娜（Christina）被分配到洪加達市中心的RSBT計劃和調度辦公室。經過數年的復雜經營，RSBT發現來自旅行社的預訂量不斷增加，但來自個人客戶的預訂量卻不斷增加。這些預訂可以分為以下四個類別：

1)         豪華轎車服務（LS）

2)         觀光游覽（SST）

3)         機場到達接送（AAT）

4)         機場出發接送（ADT）

Christina現在的任務是分析LS，SST，AAT和ADT這四種產品，並就如何進行可用巴士（它們是可用資源）的日常部署提出建議。在滿足所有預訂要求的同時，以最有效的方式使用這些資源。克里斯蒂娜（Christina）在RSBT的第一周就曾陪同過幾項運輸服務，她發現了四個業務領域的核心規劃挑戰：

LS：通過當地道路網路從豪華轎車服務總部到機場的最短（最快）路徑是什麼？如何確定此路徑？

SST：應該以什麼順序參觀所有的旅遊景點，以便遊客有足夠的時間在酒店享受休閑時光？

AAT：將與入境航班相關的所有入境旅客帶到酒店的最小旅行距離是多少？最少需要多少輛巴士？

ADT：如果客戶在預定航班起飛前不超過5小時不接受接送服務，那輛巴士應該接送哪家酒店的客人以准時送他們到機場？

通過分析發現，克里斯蒂娜（Christina）需要解決的問題通過VRP演算法平台可以有效的給出計劃和調度方案。

首先從業務生產系統錄入相關信息，這些信息經過數據資產管理處理後，將數據傳給VRP演算法中台，經演算法中台處理後再返回給業務生產系統，生成業務系統的業務數據給業務系統使用。

Ⅲ 車輛路徑問題代表的是哪一類的問題

車輛路徑問題（vehicle routeing problem，VRP）通常指帶有容量約束的車輛路徑問題（capacitied vehicle routeing problem，CVRP）。這一問題與旅行商問題（travel salesman problem，TSP）具有一定淵源，TSP可以看作是VRP的特殊情況。

先說TSP吧，在一個平整表面，有若干個點，任意兩點間均可到達，我們的旅行商現在正在0點處，他想順次走完所有的點，而且一個點不想走兩遍，最後回到0點，求怎麼走總路徑最短。
CVRP類似，平面內由一系列顧客點（costumer），以及一個車場（depot），一系列車輛想從車場出發不重不漏地訪問所有顧客點最後回到車場。與TSP不同的是，每個顧客點都有一個可量化的需求，而每輛車能滿足需求的能力有限，比如顧客點是消費者，車場是快遞站，快遞員從快遞站出發為消費者送快遞，但是快遞員每次能拿的貨是有限的，就需要好多快遞員同時從快遞站點出發，每個快遞員訪問一系列不同的消費者，最後回到快遞站點。求怎麼走總路徑最短。

Ⅳ 我在做一個車輛路徑問題,用遺傳演算法的,不會MATLAB編程,有人能幫我一下嗎

% Optimizing a function using Simple Genetic Algorithm with elitist preserved
%Max f(x1,x2)=10-x1*x1-x2*x2+x1*x2; -2.0480<=x1,x2<=2.0480
clc;clear all;
format long;%Set the data format(設定數據顯示格式)
%parameters Initialization (初始化參數)
T=100;% Generation( 模擬代數)
N=80;% Population size ( 群體規模)
pm=0.05;pc=0.8;%Crossover and mutation probability(交叉變異概率)
umax=2.048;umin=-2.048;%Parameter range(參數取值范圍)
L=10;%Single parameter string length, the total coding length is 2L(單個參數字串長度，總編碼長度2L)
bval=round(rand(N,2*L));%Population Initialization(初始種群)
bestv=-inf;%Optimal fitness Initialization(最優適應度初值)
%Iteration stsar(迭代開始)
for ii=1:T
%Decoding, and the fitness calculation(解碼，計算適應度)
for i=1:N
y1=0;y2=0;
for j=1:1:L
y1=y1+bval(i,L-j+1)*2^(j-1);
end
x1=(umax-umin)*y1/(2^L-1)+umin;
for j=1:1:L
y2=y2+bval(i,2*L-j+1)*2^(j-1);
end
x2=(umax-umin)*y2/(2^L-1)+umin;
obj(i)=10-x1*x1-x2*x2+x1*x2; %The objective function(目標函數)
xx(i,:)=[x1,x2];
end
func=obj;%Objective function into the fitness function(目標函數轉換為適應度函數)
p=func./sum(func);
q=cumsum(p);%Cumulative(累加)
[fmax,indmax]=max(func);%seeking the best in this generation(求當代最佳個體)
if fmax>=bestv
bestv=fmax;%So far, the best fitness value(到目前為止最優適應度值)
bvalxx=bval(indmax,:);%So far the best bit string(到目前為止最佳位串)
optxx=xx(indmax,:);%So far the optimal parameters(到目前為止最優參數)
end
Bfit1(ii)=bestv; % So far the optimal parameters(存儲每代的最優適應度)
%%%%Genetic operation starts(遺傳操作開始)
%Roulette wheel selection(輪盤賭選擇)
for i=1:(N-1)
r=rand;
tmp=find(r<=q);
newbval(i,:)=bval(tmp(1),:);
end
newbval(N,:)=bvalxx;%Optimal retention(最優保留)
bval=newbval;
%Single-point crossover(單點交叉)
for i=1:2:(N-1)
cc=rand;
if cc<pc
point=ceil(rand*(2*L-1));%To obtain one integer from 1 to 2L-1(取得一個1到2L-1的整數)
ch=bval(i,:);
bval(i,point+1:2*L)=bval(i+1,point+1:2*L);
bval(i+1,point+1:2*L)=ch(1,point+1:2*L);
end
end
bval(N,:)=bvalxx;%Optimal retention(最優保留)
%Locus mutation(位點變異)
mm=rand(N,2*L)<pm;%N lines(N行)
mm(N,:)=zeros(1,2*L);%Variation of the last line not change set to 0(最後一行不變異，強制賦0)
bval(mm)=1-bval(mm);
end

%Output(輸出)
plot(Bfit1);% Draw the best fitness evolution curves(繪制最優適應度進化曲線)
bestv %Output the optimal fitness value(輸出最優適應度值)
這個遺傳的我沒試過
下面這個是蟻群的結果
function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)
%%=========================================================================
%% ACATSP.m
%%-------------------------------------------------------------------------
%% 主要符號說明
%% C n個城市的坐標，n×2的矩陣
%% NC_max 最大迭代次數
%% m 螞蟻個數
%% Alpha 表徵信息素重要程度的參數
%% Beta 表徵啟發式因子重要程度的參數
%% Rho 信息素蒸發系數
%% Q 信息素增加強度系數
%% R_best 各代最佳路線
%% L_best 各代最佳路線的長度
%%=========================================================================

%%第一步：變數初始化
C=[1304,2312;3639,1315;4177,2244;3712,1399;3488,1535;3326,1556]
NC_max=200;
m=31;
Alpha=1;
Beta=5;
Rho=0.1;
Q=100;

n=size(C,1);%n表示問題的規模（城市個數）
D=zeros(n,n);%D表示完全圖的賦權鄰接矩陣
for i=1:n
for j=1:n
if i~=j
D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
else
D(i,j)=eps;
end
D(j,i)=D(i,j);
end
end
Eta=1./D;%Eta為啟發因子，這里設為距離的倒數
Tau=ones(n,n);%Tau為信息素矩陣
Tabu=zeros(m,n);%存儲並記錄路徑的生成
NC=1;%迭代計數器
R_best=zeros(NC_max,n);%各代最佳路線
L_best=inf.*ones(NC_max,1);%各代最佳路線的長度
L_ave=zeros(NC_max,1);%各代路線的平均長度

while NC<=NC_max%停止條件之一：達到最大迭代次數
%%第二步：將m只螞蟻放到n個城市上
Randpos=[];
for i=1:(ceil(m/n))
Randpos=[Randpos,randperm(n)];
end
Tabu(:,1)=(Randpos(1,1:m))';

%%第三步：m只螞蟻按概率函數選擇下一座城市，完成各自的周遊
for j=2:n
for i=1:m
visited=Tabu(i,1:(j-1));%已訪問的城市
J=zeros(1,(n-j+1));%待訪問的城市
P=J;%待訪問城市的選擇概率分布
Jc=1;
for k=1:n
if length(find(visited==k))==0
J(Jc)=k;
Jc=Jc+1;
end
end
%下面計算待選城市的概率分布
for k=1:length(J)
P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);
end
P=P/(sum(P));
%按概率原則選取下一個城市
Pcum=cumsum(P);
Select=find(Pcum>=rand);
to_visit=J(Select(1));
Tabu(i,j)=to_visit;
end
end
if NC>=2
Tabu(1,:)=R_best(NC-1,:);
end

%%第四步：記錄本次迭代最佳路線
L=zeros(m,1);
for i=1:m
R=Tabu(i,:);
for j=1:(n-1)
L(i)=L(i)+D(R(j),R(j+1));
end
L(i)=L(i)+D(R(1),R(n));
end
L_best(NC)=min(L);
pos=find(L==L_best(NC));
R_best(NC,:)=Tabu(pos(1),:);
L_ave(NC)=mean(L);
NC=NC+1

%%第五步：更新信息素
Delta_Tau=zeros(n,n);
for i=1:m
for j=1:(n-1)
Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);
end
Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);
end
Tau=(1-Rho).*Tau+Delta_Tau;

%%第六步：禁忌表清零
Tabu=zeros(m,n);
end

%%第七步：輸出結果
Pos=find(L_best==min(L_best));
Shortest_Route=R_best(Pos(1),:)
Shortest_Length=L_best(Pos(1))
subplot(1,2,1)
DrawRoute(C,Shortest_Route)
subplot(1,2,2)
plot(L_best)
hold on
plot(L_ave)

function DrawRoute(C,R)
%%=========================================================================
%% DrawRoute.m
%% 畫路線圖的子函數
%%-------------------------------------------------------------------------
%% C Coordinate 節點坐標，由一個N×2的矩陣存儲
%% R Route 路線
%%=========================================================================

N=length(R);
scatter(C(:,1),C(:,2));
hold on
plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)])
hold on
for ii=2:N
plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)])
hold on
end

Ⅳ 基於DEAP庫的Python進化演算法從入門到入土--（六）多目標遺傳演算法 NSGA-II

在很多實際工程問題中，我們的優化目標不止一個，而是對多個目標函數求一個綜合最優解。例如在物流配送問題中，不僅要求配送路徑最短，還可能需要參與運輸車輛最少等。

多目標優化問題的數學模型可以表達為：

多目標優化問題通常具有如下特點：

對於多目標優化問題，傳統方法是將原問題通過加權方式變換為單目標優化問題，進而求得最優解。該方法具有兩大問題：

遺傳演算法具有多點多方向搜索的特徵，在一次搜索中可以得到多個Pareto最優解，因此更適合求解多目標優化問題。

而當前用於求解多目標優化問題的遺傳演算法一般有兩種思路：

NSGA-II(nondominated sorting genetic algorithm II)是2002年Deb教授提出的NSGA的改進型，這個演算法主要解決了第一版NSGA的三個痛點：

針對這三個問題，在NSGA-II中，Deb提出了快速非支配排序運算元，引入了保存精英策略，並用「擁擠距離」(crowding distance)替代了共享(sharing)。

在介紹NSGA-II的整體流程之前，我們需要先了解快速非支配排序和擁擠距離的定義。

解的支配關系與Pareto最優解

下圖表示了解之間的支配和強支配關系：

下圖表示了一個最小化問題解集中的Pareto最優解和Pareto弱最優解：

快速非支配排序步驟

快速非支配排序就是將解集分解為不同次序的Pareto前沿的過程。

它可以描述為：

DEAP實現

DEAP內置了實現快速非支配排序操作的函數 tools.emo.sortNondominated

tools.emo.sortNondominated(indivials, k, first_front_only=False)

參數：

返回：

擁擠距離的定義

在NSGA II中，為了衡量在同一個前沿中各個解質量的優劣，作者為每個解分配了一個擁擠距離。其背後的思想是 讓求得的Pareto最優解在objective space中盡量分散 。也就有更大可能讓解在Pareto最優前沿上均勻分布。

DEAP實現

DEAP中內置了計算擁擠距離的函數 tools.emo.assignCrowdingDist

tools.emo.assignCrowdingDist(indivials)

參數：

返回：

比較操作

根據快速非支配排序和擁擠距離計算的結果，對族群中的個體進行排序：

對兩個解 ，

在每個迭代步的最後，將父代與子代合為一個族群，依照比較操作對合並後族群中的個體進行排序，然後從中選取數量等同於父代規模的優秀子代，這就是NSGA-II演算法中的精英保存策略。

DEAP實現

DEAP內置了實現NSGA-II中的基於擁擠度的選擇函數 tools.selNSGA2 用來實現精英保存策略：

tools.selNSGA2(indivials, k, nd='standard')

參數：

返回：

這里選用ZDT3函數作為測試函數，函數可表達為：

其Pareto最優解集為

這里為了方便可視化取 。

下圖給出了該函數在Decision Space和Objective Space中的對應：

其pareto最優解在Objective Space中如下圖紅點所示：

將結果可視化：

得到：

可以看到NSGA-II演算法得到的Pareto最優前沿質量很高：最優解均勻分布在不連續前沿的各個線段上；同時在最優前沿以外沒有個體存在。