【路徑規劃-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電子書和數學模組化資料

❤️部分理論引用網絡文獻，若有侵權聯系部落客删除