物流配送路線的數學建模

鄧上煜，徐艷，謝康

（四川大學錦城學院 計算機與軟件學院，四川成都，611731）

1 課題背景

數學模型是一種抽象模擬現實世界的過程，它能通過模擬演算解釋現實世界的某些客觀現象、發展規律，進而對現實世界的某個事件或發展提供某種好的策略。數學建模是當代大學生在未來工作和生活中探索各種各樣問題并尋求解決方案的一個非常有幫助的工具。本文將選取現實生活中物流配送路線選擇作為場景實例進行數學建模并求解最佳方案。

2 問題描述

配送網絡圖（圖1）中P為配送中心，其余A-I為客戶的接貨點，各邊上的數字為公里數，括號內的數字為需輸送到各接貨點的貨物量，單位為噸。有裝載重量為2噸和5噸的兩種貨車，車輛一次運行路線距離不超過35公里，每個派送點只由一輛車服務一次，車輛由配送中心出發，完成任務后返回配送中心，快遞車輛配送過程中無裝貨，只考慮卸貨。每個點卸貨時間固定為5分鐘，車輛每小時行駛距離為10千米，每個派送人員工作時間為8小時。

圖1 配送網絡圖

本文擬采用數學模型確定最優配送方案評估標準，并將圖中所有點配送完畢。選擇最優運輸路徑，使成本最小化，配送訂單最大化，滿載率最大化的方式制定配送運輸方案。

3 問題分析

設車輛行駛速度為V(km/h)；卸貨時長為Tx(h)；貨車載重為W(t)；單個派送員單日工作時長為Ty(h)。

將單次多個點配送時長定義為單次時長t（h）；單次配送多個點行駛距離定義為單次行駛距離s（km）。假定要進行n次配送，ti、si分別為第i次配送的單次配送時長和單次配送行駛距離，則總時長T（h）的計算公式：

將單次配送任務的總貨物量定義為單次貨物量w（t），單次貨物量與車輛載重之比定義為單次滿載率k，所有單次滿載率加和除以配送次數得到平均滿載率K。假定要進行n次配送，wi、ki為第i次配送的單次貨物量和單次滿載率，則K的計算公式：

將單次配送任務的配送點數量定義為單次訂單量l（個）。從所有單次訂單量加和除以配送次數得到的平均訂單量L（個）。假定要進行n次配送，li為第i次配送的單次訂單量，則L的計算公式：

根據整理出的信息將此問題中的成本定義為兩個方面，第一是車輛成本、第二是資源成本。

（1）車輛成本與大型貨車和小型貨車各使用次數有關，擬制定一個車輛成本指標指標U用于表示車輛使用情況。下面假設大車使用了x次，小車使用了y次，基于運載量給出U的計算公式：

（2）通過信息整理分析，單次配送最大耗費時長為 S/v=3.5(h)加上卸貨時長Tx之和，假設單次配送中總卸貨時長不超過0.5h，則單次配送最大耗費時長為4h，若配送點過多導致卸貨時長超過0.5h，則認為配送點過于密集，可以將密集的配送點整合為一個快遞服務站來保證單次配送總卸貨時長再0.5h內，該問題非時效指標計算的關鍵點，所以整合操作在本文中不作重點考慮。

用單次配送實際耗費時長除以4h則可以理解為單次配送的時間利用率，定義為單次時效o，從所有單次時效相加求平均時效O，以反映員工的時間利用率。假定要進行n次配送，oi為第i次配送的單次時效，下面給出O的計算公式：

4 建立數學評估模型

4.1 設定總體評估指標

K、L、O、T、U中每個評估指標都不能單獨的確立某個方案為最優解，故設定一個總指標sum作為對所有評估指標的綜合考量用于的評估。由問題分析得出以下結論：在最優解與評估指標的關系中K、L、O為正相關， T、U為負相關。本文將K、L、O分別乘以某個權值a、b、c之和再減去T、U分別乘以某個權值d、 e之和作為總指標sum的綜合值，以公式表示為：

該sum值即可作為方案的總體評估指標，sum值越大則方案越優。

4.2 查找全部“相鄰點連線”

找出除源點P外所有點的排列組合方式，將每一個排列組合的字符序列看作是一條行駛路徑，在這條行駛路徑的配送點序列中，驗證從頭到尾任意前后兩點之間是否都存在直連通路。若存在任意前后兩點之間不為通路的情況則去除該行駛路徑，否則該通路保留，并在本文中將這樣的路徑稱為相鄰點連線。這樣的步驟作為初步篩選，保證了單次配送的各配送點都是相互緊挨著的，是對最優路徑的初步選擇。

4.3 相鄰點分區

經過初步篩選后，保留下來的行駛路徑均為相鄰點連線，然后可對所有保留下來的相鄰點連線進行分區。

以圖1舉例說明相鄰點分區的方法：從I點開始向前查找到下一個點A，I、A兩點的貨物的總量小于車輛載重5，并且從P點到I點再到A點再回到P點的最短總路程小于35，則繼續向前查找到下一個點B，并繼續向前做同樣的驗證，直到點D的時候貨物了大于5，則退回將I、A、B、C劃為一個分區。然后再從D點開始做以上同樣的操作，最終可以得出一個分區方案。

在找出相鄰點連線的基礎上，通過相鄰點分區的方式，我們可以得到所有初步最優的分區方案，并且在每一個方案的每一個分區中，通過相鄰連線保存的行駛路徑即可直接找到配送該分區的區內最佳行駛路徑，即對每一個分區只需要考慮源點到每個分區的起點和

終點的最短距離，避免了分區內部最優路徑的選擇問題。

通過這種方式，找出一種分區分案和一條相鄰連線，即可以比對某一種分區方案制定一個整體最優的配送方案。計算并保存所有分區方案的數據，將這些數據根據熵值法進行數學評估模型的設計。

5 計算過程

5.1 總體數據

利用 Dijkstra算法計算出所有配送方案的數據，如圖2所示。

圖2 利用 Dijkstra算法計算出所有配送方案的數據

5.2 熵值法

根據各項指標的變異程度，利用信息熵這個工具，計算出各個指標的權重，為多指標綜合評價提供依據，即可采用熵值法對各權值a、b、c、d、e進行計算求值。

將以上數據集中各方案的五個評估指標值轉換為一個22行5列的矩陣A，表達式如下：

將矩陣A轉換為如下決策矩陣B：

基于熵值法，第j個屬性下第i個方案，pi的貢獻度以dij表達式表示為：

基于熵值法，所有方案對屬性xj的貢獻總量ej的值也就是各評估標準的熵值，當某個屬性下各方案的貢獻度趨于一致時，ej將趨于最大值1。當ej值為1時，就可以不考慮該屬性在決策中的作用，即該屬性的權值為0。

再將dij矩陣帶入ej中即可得到五個評估指標的熵值大小，分別為 ：K：0.9985426；L：0.99665695；O：0.99936664；T：0.99864525；U：0.998687。

最終求得sum值大小作為評估指標的數學評估模型即為：

5.3 得到最優解

將各個指標的權值帶入模型中，再次利用Dijkstra算法并遍歷所有方案找出sum值最大的方案，即為最優解。輸出結果如圖3所示。

圖3 輸出結構圖