【路径规划-VRP问题】基于模拟退火 (SA)求解车辆配送 （VPR）附Matlab代码

✅作者简介：热爱科研的Matlab仿真开发者，修心和技术同步精进，matlab项目合作可私信。

🍎个人主页：Matlab科研工作室

🍊个人信条：格物致知。​

⛄ 内容介绍

    模拟退火算法的思想借鉴于固体的退火过程，当固体的温度很高时，内能比较大，固体内的粒子处于快速无序运动状态，当温度慢慢降低，固体的内能减小，粒子逐渐趋于有序，最终固体处于常温状态，内能达到最小，此时粒子最为稳定。

    白话理解：一开始为算法设定一个较高的值T（模拟温度），算法不稳定，选择当前较差解的概率很大；随着T的减小，算法趋于稳定，选择较差解的概率减小，最后，T降至终止迭代的条件，得到近似最优解。

带时间窗的车辆路径问题(VRPTW)

由于VRP问题的持续发展，考虑需求点对于车辆到达的时间有所要求之下，在车辆途程问题之中加入时窗的限制，便成为带时间窗车辆路径问题（VRP with Time Windows, VRPTW）。带时间窗车辆路径问题（VRPTW）是在VRP上加上了客户的被访问的时间窗约束。在VRPTW问题中，除了行驶成本之外, 成本函数还要包括由于早到某个客户而引起的等待时间和客户需要的服务时间。在VRPTW中，车辆除了要满足VRP问题的限制之外，还必须要满足需求点的时窗限制，而需求点的时窗限制可以分为两种，一种是硬时窗（Hard Time Window），硬时窗要求车辆必须要在时窗内到达，早到必须等待，而迟到则拒收；另一种是软时窗（Soft Time Window），不一定要在时窗内到达，但是在时窗之外到达必须要处罚，以处罚替代等待与拒收是软时窗与硬时窗最大的不同。

模型2(参考2017 A generalized formulation for vehicle routing problems)：

该模型为2维决策变量

⛄ 部分代码

function qnew=CreateNeighbor(q)

    m=randi([1 3]);

    switch m

        case 1

            % Do Swap

            qnew=Swap(q);

        case 2

            % Do Reversion

            qnew=Reversion(q);

        case 3

            % Do Insertion

            qnew=Insertion(q);

    end

end

function qnew=Swap(q)

    n=numel(q);

    i=randsample(n,2);

    i1=i(1);

    i2=i(2);

    qnew=q;

    qnew([i1 i2])=q([i2 i1]);

end

function qnew=Reversion(q)

    n=numel(q);

    i=randsample(n,2);

    i1=min(i(1),i(2));

    i2=max(i(1),i(2));

    qnew=q;

    qnew(i1:i2)=q(i2:-1:i1);

end

function qnew=Insertion(q)

    n=numel(q);

    i=randsample(n,2);

    i1=i(1);

    i2=i(2);

    if i1<i2

        qnew=[q(1:i1-1) q(i1+1:i2) q(i1) q(i2+1:end)];

    else

        qnew=[q(1:i2) q(i1) q(i2+1:i1-1) q(i1+1:end)];

    end

⛄ 运行结果

⛄ 参考文献

❤️ 关注我领取海量matlab电子书和数学建模资料

❤️部分理论引用网络文献，若有侵权联系博主删除