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最优前沿质量很高：最优解均匀分布在不连续前沿的各个线段上；同时在最优前沿以外没有个体存在。