精华内容
下载资源
问答
  • 遗传算法求解约束、类型车辆、目标优化车辆路径问题
    万次阅读 多人点赞
    2017-03-21 13:54:45

    目前关于车辆路径问题的模型种类很多,因此在建立综合优化模型时可选择的也很多,考虑到在实际情况中,配送中心大都是少批次、多品种的配送,需要将多个客户的货物集中到一起后再进行配送,而车辆装载货物的量有限,加之对于带载重限制的车辆路径问题的研究目前为止很多,研究背景较强,此外,结合调研中车辆有最大行驶里程限制,因此本文选择了带载重及车辆最大行驶里程限制的车辆路径模型作为综合优化的整合对象。

    本文涉及到的车辆路径问题描述如下:某配送中心,共有k辆车给n个客户点进行配送,每辆车的额定载重量为Gk客户点i的货物重量为gi,车辆装载的货物总重量要小于车辆的额定载重量,使得在满足客户需求的情况下车辆总行驶路径最短。可表示如下图所示。

    图1 车辆路径优化的模型模型

    建立模型

    变量太多,这里就不详细解释变量的含义,对上面4个函数解释如下:式(3-18)车辆总的行驶里程最短;式(3-19)表示车辆总载重利用率最大;式(3-20)表示车辆总容积利用率最大;式(3-21)车辆使用数量最少。

    同时针对模型具有以下的约束条件:


    该模型包含四个部分的目标:车辆运行里程最短,载重利用率最大,,车辆容积利用率最大,车辆使用数目最小,从优化的角度来看这是一个多目标优化的问题,所以采用通用的方法将其转化成单目标优化问题,以实现对四个目标函数的优化。

    单目标转换

    将上面的4个目标函数转化成以下的单目标函数:


    遗传求解

    设计改进的遗传算法进行求解,包括设计编码方案、初始化种群、制定解码方案、确定适应度函数、设计遗传算子、设定参数以及确定终止条件这几个步骤。

    部分程序:

    %    Author:    怡宝2

    %    Use:       基于遗传算法求解多约束条件,多类型运输车辆的车辆路径优化问题,并将4个多目标的优化问题,转化成一个单目标优化问题

    %                输入变量(可修改量):

    %                                      popsize:种群大小

    %                                      T:进化代数                      

    %                输出:        

    %                                      route:运输路径

    %    Remark  本人qq778961303,如有疑问请咨询

    tic;

    clc;close all;clear all;%S除变量

     

    format loose

     

    l=20;%配送车数

    vehicle=[1750 25;

            2000 31.5;

            2200 54;

            3040 65];%不同类型车辆的载重,体积的限制

    num_vehicle=[3 4 5 6];          %不同车辆的数量

    limit=[];                       %载重和体积的限制

    for i=1:length(num_vehicle)

       temp=rep(vehicle(i,:),[num_vehicle(i) 1]);

       limit=[limit;temp];

    end

    G=limit(:,1);   %车辆的载重限制

    V=limit(:,2);   %车辆的体积限制

    N=32;%需要配送节点数

    % G=1995;%^辆载重限制

    % V=30;%车辆体积限制

    L=250;%^辆路程限制

    alpha=1;

    Ws=130;%车辆满载时按载重计算的成本

    Vs=140;%车辆满载时按体积计算的成本()

    %车辆配送成本

    Csl=0.3;%单位公里消耗燃料费用(/km)

    Cs2=2; %车辆折旧(/km)

    Cs3=0.03;%轮胎消耗(/km)

    Cs4=1.38;%油费(/km)

    Cs5=1.24;%养路费(元/km

    Cs6=0.15;%车辆日常维护费(元/km

    %车辆其他配送相关成本

    Fsl=100;%装卸费用(/)

    Fs2=8.9;%保险费(/)

    Fs3=30; %文档费用(/)

    Fs4=50; %配送材料费用(/)

    while gen<=T

    %%遗传算法选择

    FitnV=ranking(Value);%分配适应度值

    Chrom=select('sus',Chrom,FitnV,1);%选择

    Chrom=mutationGA(Chrom,popsize,PM,N);%种群变异,单点变异

    Chrom=crossGA(Chrom,popsize,PC,N);%种群交叉,两点变交叉

    %%计算最优

    [vl,index1]=min(Value);

    gen=gen+1;

    trace1(gen,1)=Value(index1);

    trace1(gen,2)=mean(Value);

    %%记录最优

    if gen == 1

       bestChrom1=Chrom(index1,:);%记录函数1的最优染色体

       bestValuel=vl;%记录函数1的最优值

    end

    if bestValuel>vl

       bestValuel = vl;%记录函数1的最优值

       bestChrom1=Chrom(index1,:);

    end

    waitbar(gen/T,wait_hand);%每循环一次更新一次进步条

    end

    delete(wait_hand);%执行完后删除该进度条

    %显示结果

    disp(['最佳目标函数',num2str(bestValuel)]);

     

    disp(['最佳染色体',num2str(bestChrom1)]);

     

    disp(['总用车数量:',num2str(min(y4(:,1)))]);

    %% 结果

    %%转换为需要的格式和输出文件

    s=bestChrom1;

    needdataW=needdata(1,s);

    needdataV=needdata(2,s);

    route =divideroute(s,needdataW,needdataV,G,V,L,distdata);%路径划分

    %求每辆车的路程,载重利用率,体积利用率

    index = find(route==0);

    for i = 1:length(index)-1

       temp_route=route(index(i):index(i+1));                %每辆车的路径

       temp_y1=objectfun_distance(temp_route,distdata);      %每辆车的路程

       [temp_y2 temp_y3] = pervehicle(temp_route,needdata,G(i),V(i));      %每辆车的载重、体积利用率

       disp(['' num2str(i) '    辆车的路径:'num2str(temp_route)]);

       disp(['' num2str(i) '   辆车行驶路程:'num2str(temp_y1)]);

       disp(['' num2str(i) '辆车的载重利用率:'num2str(temp_y2)]);

       disp(['' num2str(i) '辆车的体积利用率:'num2str(temp_y3)]);

    end

    disp(['传算法优化得到的最佳路径:',num2str(route)]);

     

    disp(['遗传算法优化得到的目标函数值:',num2str(bestValuel)]);

     

    disp(['遗传算法优化得到的总行驶里程:',num2str(min(yl(:,1)))]);

     

    disp(['遗传算法优化得到的车辆载重未利用率',num2str(min(y2(1,:)))]);

     

    disp(['遗传算法优化得到的车辆容积未利用率',num2str(min(y3(1,:)))]);

     

    %% 画图

    %%总目标函数

    figure

    plot(trace1(:,1),'b-');

    hold on;

    plot(trace1(:,2),'r-');

    legend('目标函数最优值','目标函数均值');

    xlabel('迭代次数')

    ylabel('目标函数')

    title('遗传算法优化成本迭代曲线')

     

     

    如有疑问请咨询:qq778961303

    程序运行结果:

     

    更多相关内容
  • matlab求解模拟退火求解带有时间窗的多车辆路径优化问题
  • 提出解决车辆路径优化问题的方法, 针对蚁群算法的缺点, 分别对信息素更新策略、启发因子进行改进, 并引入搜索热区机制, 有效解决了蚁群算法的缺陷。最后, 以哈尔滨市局部地图为原型, 应用MATLAB软件对改进蚁群算法...
  • 资源名:目标路径优化问题_模拟退化算法_用车辆路径优化_VRP_matlab 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者更换...
  • 关于目标车辆路径优化问题的源代码,C语言,包含文档描述。
  • 对于动态目标车辆路径问题,通常将车辆的等待时间,服务车辆的数量,路线的总距离作为优化目标。 除上述目标外,本文还重点研究了导致环境污染和能源消耗的燃油消耗。 考虑车辆的负载和行驶距离,建立了相应的碳...
  • 提出解决车辆路径优化问题的方法,针对蚁群算法的缺点,分别对信息素更新策略、启发因子进行改进,并引入搜索热区机制,有效解决了蚁群算法的缺陷。最后,以哈尔滨市局部地图为原型,应用MATLAB软件对改进蚁群算法...
  • 【路径规划】一种基于改进蚁群算法的配送中心车辆路径优化方法matlab源码.zip
  • 更具实际的路径优化求解模型,适用范围更广的路径优化模型,
  • 十分钟学会车型车辆路径问题初始解构造方法

    目录

    ▎FSMVRP问题数学模型

    ▎FSMVRP问题初始解构造方法

    ▎参考文献


    今天为各位讲解一个基本车辆路径问题的衍生问题-多车型车辆路径问题(heterogeneous fleet vehicle routing problem,HFVRP)。其中HFVRP还分为两种类型,第一种是不限制每种类型车辆的数目(Fleet Size and Mix Vehicle Routing Problem,FSMVRP),第二种是限制每种类型车辆的数目(Heterogeneous Fixed Fleet Vehicle Routing Problem,HFFVRP)。

    今天主要讲解FSMVRP问题,该问题需要确定两方面内容:

    1)确定为每条路线服务的车型。

    2)确定每条路线访问顾客的顺序

    ▎FSMVRP问题数学模型

    \begin{aligned} \operatorname{Min} \sum_{k=1}^{T} f_{k} \sum_{j=1}^{n} x_{0 j}^{k}+\sum_{k=1}^{T} \sum_{i=0}^{n} \sum_{j=0}^{n} c_{i j} x_{i j}^{k}\quad(1) \\ s.t. \sum_{k=1}^{T} \sum_{i=0}^{n} x_{i j}^{k}=1 \quad j=1, \ldots, n\quad(2) \\ \sum_{i=0}^{n} x_{i j}^{k}-\sum_{l=0}^{n} x_{j l}^{k}=0 \quad j=0, \ldots, n ; k=1, \ldots, T \quad(3) \\ \sum_{i=0}^{n} y_{i j}-\sum_{l=0}^{n} y_{j l}=d_{j} \quad j=1, \ldots, n \quad(4) \\ y_{0 j} \leqslant \sum_{k=1}^{T} Q_{k} x_{0 j}^{k} \quad j=1, \ldots, n \quad(5) \\ y_{i j} \leqslant M \sum_{k=1}^{T} x_{i j}^{k} \quad i \neq j=0, \ldots, n \quad(6) \\ y_{i j} \geqslant 0 \quad i \neq j=0, \ldots, n \quad(7) \\ x_{i j}^{k} \in\{0,1\} \quad i \neq j=0, \ldots, n ; k=1, \ldots, T \quad(8) \end{aligned}

    其中,0表示配送中心,1,...,n表示顾客,T表示车型数目,Qk表示车型k的最大装载量(Q1<Q2<...<QT),fk表示车型k的固定使用成本(f1<f2<...<fT),dj表示顾客j的需求量,cij表示车辆从顶点i行驶到顶点j的成本(cij=cji)。

    此外,决策变量如下:

    公式(1)车辆使用成本和车辆行驶成本之和。公式(2)和(3)保证车辆到达一个顾客后会离开该顾客。公式(4)表示货物量的移动,确保每个顾客的需求都能被满足。公式(5)确保车辆离开配送中心时的装载量不能超过其最大装载量。公式(6)表示如果没有车辆从顶点i行驶到顶点j,那么从顶点i到顶点j没有货物流动。


    ▎FSMVRP问题初始解构造方法

    FSMVRP和容量受限的车辆路径问题(CVRP)的差别在于FSMVRP还需确定为每条路线服务的车型

    我们在节约(CW)算法构造容量受限的车辆路径问题(CVRP)初始解MATLAB代码这篇推文中提到过CVRP初始解的构造方法,CW法的本质是依据合并两条路径带来的节约值反复合并路线最终构造出初始解。CW构造CVRP的节约值很容易理解就是路径长度的节约值。

    虽然不能够直接将构造CVRP的CW法直接应用于FSMVRP问题,但是我们可以通过对节约值的改造,让改造后的CW法也能应用于FSMVRP问题。

    通过前文对FSMVRP问题要确认的内容可以看出,改造后的节约值也至少应该包含两部分:1)车辆使用成本的节约值,2)车辆行驶距离的节约值。其中车辆行驶距离的节约值就是路径长度的节约值。

    接下来在介绍车辆使用成本的节约值之前先引入3个概念:

    F(z)-能够服务总需求量为z的路线的最小车型的使用成本

    P(z)-能够服务总需求量为z的路线的最小车型的最大装载量

    F'(z)-不能够服务总需求量为z的路线的最大车型的使用成本

    为了能够更好的理解F(z)、P(z)和F'(z),我们用下面的例子进行阐述。

    假设有3个车型,每个车型的最大装载量为(Q1,Q2,Q3)=(30,50,100),每个车型的固定成本为(f1,f2,f3)=(20,40,90),则关于F(z)、P(z)和F'(z)的分段函数如下:

    F(z)=\left\{\begin{array}{rr} 20, & 0<z \leqslant 30 \\ 40, & 30 < z\leqslant50 \\ 90, & 50 < z\leqslant100 \\ \infty, & 100 \leqslant z . \end{array}\right.

    P(z)=\left\{\begin{array}{lc} 30, & 0<z \leqslant 30 \\ 50, & 30<z \leqslant 50 \\ 100, & 50<z \leqslant 100 \\ \infty, & 100<z \end{array}\right.

    F^{\prime}(z)=\left\{\begin{array}{rr} 0, & z<30 \\ 20, & 30 \leqslant z<50 \\ 40, & 50 \leqslant z<100 \\ 90, & 100 \leqslant z . \end{array}\right.

    在理解完上述三个概念后,我们进而介绍路径节约值固定成本节约值机会节约值。首先假设现在有两条路径R1和R2,路径R1最后一个访问的顾客为i,路径R2访问顾客j,总需求量分别为zizj,则上述3个节约值的定义分别如下:

    (1)路径节约值

    s_{i j}^{r}=c_{i 0}+c_{0 j}-c_{i j}

    (2)固定成本节约值

    s_{i j}^{f}=F\left(z_{i}\right)+F\left(z_{j}\right)-F\left(z_{i}+z_{j}\right)

    (3)机会节约值

    s_{i j}^{o}=\delta(w) \cdot F^{\prime}\left(P\left(z_{i}+z_{j}\right)-z_{i}-z_{j}\right) \\ \text { 其中 } w=P\left(z_{i}+z_{j}\right)-P\left(\max \left\{z_{i}, z_{j}\right\}\right) \\ \delta(w)= \begin{cases}0 & \text { if } w=0 \\ 1 & \text { if } w>0\end{cases} \\

    综上所述合并R1和R2的总节约值由3部分组成:

    s_{i j}=s_{i j}^{s}+s_{i j}^{f}+s_{i j}^{o}

    依据改造后的节约值,并保留CW法构造CVRP初始解的模式,反复合并路径,直至合并任意两条路径时的sij都为负值时,FSMVRP的初始解即构造完毕

    在这里再补充一点,机会节约值的作用。机会节约值目的是鼓励使用能够带来收益的更大的车型。当需要使用更大的车型来服务两条路径合并后的路径时,使用更大车型带来的剩余装载量为后续合并小需求路径提供可能,进而降低车辆使用成本。因此可以被“挤进”剩余装载量的最大车型的固定成本即为机会成本s_{i j}^{o}


    ▎参考文献

    [1]Gheysens F, Golden B, Assad A. A comparison of techniques for solving the fleet size and mix vehicle routing problem[J]. Operations-Research-Spektrum, 1984, 6(4): 207-216.

    [2]Golden B, Assad A, Levy L, et al. The fleet size and mix vehicle routing problem[J]. Computers & Operations Research, 1984, 11(1): 49-66.

    咱们下期再见

    ▎近期你可能错过了的好文章:

    新书上架 | 《MATLAB智能优化算法:从写代码到算法思想》

    优化算法 | 灰狼优化算法(文末有福利)

    优化算法 | 鲸鱼优化算法

    遗传算法(GA)求解带时间窗的车辆路径(VRPTW)问题MATLAB代码

    粒子群优化算法(PSO)求解带时间窗的车辆路径问题(VRPTW)MATLAB代码

    展开全文
  • 电动车辆路径优化问题(Electric vehicle routing problem,EVRP)是电动车运行管理和物流优化中的核心问题之一.对此,首先介绍电动车辆路径问题的研究现状;然后,从充电优化、路径优化和车队配置优化的不同侧重角度,着重...
  • 基于蚁群算法的物流车辆路径优化问题的研究.pptx
  • 设计了在动态环境下进行车辆路径优化的导向局域搜索算法。算法在产生初始解以后的动态求解过程中,不再做车辆之间的顾客调整,而只应用2-opt局域搜索算子更新车辆服务顾客的顺序,即针对每辆车辆的旅行路线求解一个...
  • 针对冷链物流配送车辆路径优化问题,分析云计算模式下处理配送车辆实时路径的优势,建立了冷链物流配送车辆路径优化应用服务架构;并在该架构下获取多源实时交通信息,分析车辆配送时间和综合成本,构建了冷链物流...
  • 研究顾客具有多种需求,分别需要由不同类型车辆提供服务,且...将经典的单一需求车辆路径问题推广到多种需求的情形,建立带约束的需求车辆路径问题的数学模型并设计求解模型的有效算法,为解决实际问题提供了决策依据.
  • 车辆路径 matlab代码 Intelligent_Algorithm 用matlab解决路径规划和竞争设施选址问题 一、五个基础算法以及示例: ga 遗传算法解决分配问题 问题描述: 现有10个工人去做10件工作,每个工人完成每项工作所需时间...
  • matlab鲸鱼优化算法求解开放式车辆路径问题.zip
  • 计算遗传算法的变成文件,基于车辆路径优化问题
  • matlab头脑风暴优化算法求解带时间窗和同时取送货的车辆路径问题.zip
  • 通过该模型求解带软时间窗的vrptw模型,得到车辆路径问题的最优解
  • 车辆路径优化.zip

    2020-05-10 17:10:18
    压缩包中有两个版本,一个是带时间窗的和一个是不带时间窗的,惩罚函数也有两个,分别是一次惩罚函数和二次惩罚函数。如果有问题可以我。
  • 提出一种模拟文化进化的Memetic算法求解带时间窗的车辆路径问题。设计了一种实数编码方案,将离散的问题转为连续优化问题。采用邻域搜索帮助具备一定学习能力的个体提高寻优速度;采用禁忌搜索帮助部分个体跳出局部...
  • 该资源有利用对物流配送车辆路径优化问题论文的参考和运用
  • 针对智能交通系统中的车辆路径优化问题,运用蚁群算法进行求解,并对状态转移概率公式的选择做出了调整,进一步对信息素挥发因子进行改进,从而改进了基本蚁群算法到一定阶段后容易陷入局部最优的缺点,提高了算法的运算...
  • 该资源对某篇论文中的模型进行了复现, 并编写了python代码, 调用gurobi进行求解, 最后画出路径图. 所得结果与论文中用遗传算法求解结果完全一致. 该资源是学习路径规划问题求解和gurobi代码编写的绝佳资料.
  • 本程序用于求解车型目标下的车辆路线问题,程序中考虑了两种车型,建立的目标函数是车辆总运营成本最小,考虑的约束有容量约束、最大行驶距离约束和时间窗约束,采用的优化算法是遗传算法,程序内部有详细的注释...
  • 针对配送中心的动态启用与车辆的合理分配,建立了以总...最后,应用狼群算法求解测试算例,并将其计算结果与几种常见智能优化算法的计算结果进行比较,验证了狼群算法求解配送中心车辆路径问题的可行性与有效性。
  • 用粒子群算法计算最短路径,一般用于车辆路径问题%------基本粒子群优化算法(Particle Swarm Optimization)----------- %------名称:基本粒子群优化算法(PSO) %------作用:求解优化问题 %------说明:全局性,...
  • 根据B2C(商家对客户)电子商务环境下物流配送的特点建立了带预约时间的车辆路径问题(VRP)数学模 型,设计了求解目标优化的蚁群算法,各个目标具有相同的重要性.在蚁群的状态转移概率中引入预约时间窗宽度及车辆等待...
  • 通过实验仿真, 将所提出的聚类算法 与蚁群算法和禁忌搜索算法进行比较, 所得结果表明了所提出的算法可以更有效地求得需求可拆分车辆路径问题优化解, 是解决需求可拆分车辆路径问题的有效方法.<...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,354
精华内容 3,741
关键字:

多车辆路径优化问题