基于改進C-W算法的廣西高校畢業生行李運輸研究

摘 要：以廣西高校畢業生行李運輸為研究對象，結合省級郵局與市級郵局之間的運輸車輛調度特點，針對運輸車輛運力、時間約束等條件，建立了改進C-W算法的廣西高校畢業生行李郵政快遞運輸車輛調度模型，并通過算例進行驗證，結果顯示算法對高校畢業生行李運輸具有顯著優化作用。

關鍵詞：行李運輸;C-W節約算法;車輛調度

中圖分類號：F25 文獻標識碼：A doi：10.19311/j.cnki.1672-3198.2019.18.011

1 前言

2017年全廣西畢業生總人數17萬人，高校畢業生行李運輸市場需求量大。然而并沒有規模地將高校畢業生行李運輸到目的地，而存在少量零星的運輸會加大運輸成本。現在運輸行李一般有兩種選擇——快遞與貨運。快遞的速度運輸時間短，運輸費用高，省內首重8元，續重每斤2元，寄行李的成本偏高。貨運雖然成本相對便宜，但運輸到的目的地距離自己所在地還有一定距離，非常不便。針對現在所存在的問題，制定相關的優化方案，解決成本過高而導致行李運輸費用高的問題，使大多數畢業生能夠解決行李運輸的問題。

2 建模

面對多個快遞公司與物流公司，畢業生不僅僅考慮價格，還考慮行李是否能夠送達住址。根據調查，85.61%的人住址附近有郵政快遞，因此，本文以郵政快遞的運輸路線作為研究對象。中國郵政在全國各地擁有完善的運輸網點。它在農村設有4.4萬處代辦點郵局，3萬多個網點覆蓋城鄉。因此，中國郵政在網點的覆蓋面上具有很大的優勢。通過對郵政運輸路線的優化，降低運輸成本。

2.1 問題描述

省級郵局記為D，市級郵局記為Xi（i=1，2，…，i）。D有i個市級郵局收集、派送快遞，在同一條線路上把所有的快遞送到特定的市級郵局后，返回途中，將路過一個或多個市級郵局，把市級郵局的快的運回省級郵局D。每個市級郵局對快遞的送到時間都有要求。運輸路線的基本形式有兩種：①運輸路線1表示運輸車輛由省級郵局D到市級郵局Xi進行派件，若收集完快遞后，運輸車輛有空間，且滿足集散地對時間的約束，則支持多運輸幾個市級郵局;②運輸路線2表示運輸車輛由省級郵局D到目的市級郵局派件，但收集快遞后車輛沒有空間或不滿足市級郵局的時間要求，直接返回省級郵局D。

2.2 模型的建立

2.2.1 假設條件

車輛運輸調度模型需要滿足一下約束條件：

①省級郵局的車輛數目與類別是固定的，并能滿足運輸需求;

②運輸車輛由省級郵局出發，在完成派件與收集快遞后需要回到省級郵局;

③在完成一個批次貨運時，每臺車輛最多安排一個班次;

④運輸車輛的運輸時間不包括裝卸時間;

⑤在支線運輸中，運輸車輛只在目的市級郵局卸載;

⑥轉運車輛都符合運輸時間的約束條件。

2.2.2 建立模型

根據以上的約束條件和假設條件，可建以下模型：

模型說明：（1）中的目標好書表示為市級郵局的車輛運輸的總成本為最小，其中前半部分的意思為同一個批次運輸車輛的運輸費，后半部分的意思為快遞的處理成本。（2）表示為省級郵局D分配給每個市級郵局的r類型運輸車輛的總數了小于等于省級郵局所擁有的數量。（3）的意義為從市級郵局回到升級有的r類型運輸車輛的總數量不會超過省級郵局所擁有的數量。（4）的意思是運輸車輛的分配能滿足各個市級郵局的派送需求。（5）的意思為運輸車輛的分配能滿足各個市級郵局的收件需求。

2.3 模型分析

由于市級郵局的快遞的數量不穩定，派送數量與收件數量有時候會出現數量相差大的情況，導致運輸車輛的剩余空間較多，無法達到滿載。因此，我們需要由不同市級郵局的派送數量與收件數量算出是否能采用C-W算法，如表1所示。

2.4 模型求解

實際情況中，物流配送規模變大，計算也會增加。因此，我們在解決這樣的問題時，如果使用的是啟發式的算法會提高最佳解的計算速度。C-W算法改進后的方法為：①把市級郵局與省級郵局相連接，形成一條只有一個市級郵局的運輸路線，統計總時間與費用。②把兩個市級郵局連接在同一條路線上節約的時間和費用，節約的時間與費用越多，說明將兩個市級郵局連在一起的總的運輸時間與費用節約越多，直到節約值為0。

D（i，j）=時間+費用表達節約值

D（i，j）=（liov+nroi·lio·CQr）+ljov+nroj·ljo-CQr-lijv+lij·CQR;r=1，2，…，r;

鏈接點i與點j形成的路線記為EFj，運輸車輛到達市級郵局j的時間比原路線的時間變多（或變少）的值，表示如下：

EFj=Xi+Ti+tij-Xj

當EFj<0時，運輸車輛到達市級郵局j的時間變少;當EFj=0時，運輸車輛到達市級郵局i的時間不變，當EFj>0時，運輸車輛到達市級郵局j的時間變多。

令Δ-j=minr≥jXi-ETr，它的意思是運輸路線上市級郵局j后面的各市級郵局都不需要等待時，運輸車輛到達市級郵局j的時間的最大允許提前值。

Δ+j=minr≥jETr-Xi表示運輸路線上的運輸車輛到達市級郵局j后面的是基友不違反時間約束條件的同時，運輸車輛到達車輛市級郵局j的時間的最大允許推遲量。

根據以下原則可判斷出鏈接點i與點j后是否違反時間的約束條件：

①當EFj<0時，若EFjSymbolcB@Δ-j，運輸車輛在到達市級郵局j后的市級郵局時不用等待，否則則需等待。

②當EFj>0時，若EFjSymbolcB@Δ+j，運輸車輛在到達市級郵局j后的市級郵局時不會推遲時間，否則會推遲時間。

步驟如下：

Step1：根據省級郵局到市級郵局的云貨量與市級郵局到省級郵局的云貨量較大的安排運輸車輛數量;

Step2：觀察市級郵局：1，2，…，i中，市級郵局到省級郵局的運貨量中是否有滿載的，若沒有，則先派車，否則轉Step3;

Step3：將剩下的運輸車輛按從市級郵局到省級郵局的車輛的剩余空間由大到小進行排列;

Step4：計算個點之間的D（i，j）=時間+費用。令M=D（i，j）D（i，j）gt;0，并在對D（i，j）由大至小排序。當D（i，j）=市級郵局i到省級郵局D的時間與費用+市級郵局j到省級郵局D的時間與費用-市級郵局i到市級郵局j的時間與費用。

Step5：如果M=，則可以停止迭代，則可對第一項D（i，j）查看相對應的（i，j），如果滿足以下條件之一，就可以賺到下一步，否則轉Step8：

①點i和點j都不在已有的運輸路線上;

②點i貨點j在已有的運輸路線上，但是必須與省級郵局直接連接;

③點i和點j都在已有的運輸路線上，并于省級郵局直接連接，同時分別為起點和終點。

3 算例

廣西有一個省級郵局D服務于14個市級郵局，省級郵局有2中車型：I車型RQ1=4t，Ⅱ種車型RQ=2t。省級郵局擁有I車型和Ⅱ車型的運輸車輛各15輛，運輸車輛的平均速度v=65km/h。起點市級郵局到終點市級郵局的快遞量如表2所示;從市級郵局i經省級郵局運出的快遞量如表3;外來快遞經省級郵局D運往市級郵局i的快遞量如表4;市級郵局之間以及省級郵局與市級郵局的距離參考網上查詢結果;各市級郵局的裝卸時間Ti與市級郵局的時間需求ETi，LTi如表5;最后算出的運輸車輛的分配表如表6;市級郵局之間以及市級郵局與省級郵局是否連接，若不同市級郵局之間相連接，則為1，若市級郵局與省級郵局相連接則為2，其他情況都為0。

4 結論

本文針對廣西高校畢業生行李運輸問題，建立了改進型C-W算法的廣西高校畢業生行李郵政快遞運輸車輛調度模型，對有效解決廣西高校畢業生行李運輸難、運輸貴等問題提出了建議，同時結合廣西14個省市郵政局的情況，求解出了最終地級市車型分配方案。本文雖然對運輸車輛的調度、運輸路線進行了研究，并建立了模型，但在現實中情況不是一成不變的（如快遞每天的數量的多少、運輸車輛發生的意外情況等），理論與實際問題有待進一步研究與探索，可按以下兩個方面來展開研究：

①本文雖然對行李運輸問題構建了模型，實際問題中還需要考慮地理位置、人口數量、經濟發展程度、環境等因素，才能有效全面分析行李運輸過程，建立更趨于實際的理論模型;

②行李運輸對時間維度的要求十分緊迫，提出一個快速的有效求解方法對整理運輸路線的規劃與運輸車輛的調度起著關鍵作用，尋找一個迅速有效的計算方法是今后研究的要點。

參考文獻

[1]王宇奇，李靖澤.基于改進C-W節約算法的成品油二次配送優化研究[J].科技與管理，2014，16（1）：51-55.

[2]任雪甜，朱曉敏，何中祥，等.基于改進C-K節約算法的第三方冷鏈物流企業車輛調度（英文）[J].北京交通大學學報，2015，39（4）：125-132.

[3]陳火根，丁紅綱，程耀東.物流配送中心車輛調度模型與遺傳算法設計[J].浙江大學學報（工學版），2013，37（5）：512-516.

[4]肖燕等.物流配送車輛優化調度模型研究[J].鐵道運輸與經濟，2008，30（6）：69-75.

[5]倪玲霖，史峰.多分配快遞軸輻網絡的樞紐選址與分配優化方法[J].系統工程理論與實踐，2012，32（2）：441-448.

[6]林峰，賈濤，李然.基于改進C-W算法的易腐品一體化庫存路徑問題研究[J].系統工程，2016，（8）：100-107.