基于Lingo的關鍵路徑法在冷鏈物流中的應用

曹 茜，宋筱影 （上海電力學院，上海 201399）

·現代物流·

基于Lingo的關鍵路徑法在冷鏈物流中的應用

曹 茜，宋筱影 （上海電力學院，上海 201399）

冷鏈物流是近期發展起來的新型物流形式，物流企業在進行冷鏈配送時往往會進行多方面的考慮。文章主要研究了關鍵路徑法在冷鏈物流中的應用，通過分析具體的實例，并運用Lingo軟件進行求解來解決關于冷鏈物流中配送的時效性問題。

關鍵路徑法；冷鏈物流；Lingo

0 引言

關鍵路徑法（Critical Path Method，CPM）[1]作為目前現代項目管理的重要管理工具，是通過分析某項活動過程中各子項進度安排的最少時差之和，以此來對該活動的時間和成本進行預測和優化的方法。

關鍵路徑法作為一種網絡技術中的重要方法，在物流行業有著許多的應用。而在整個物流過程中，物流的配送是其中非常重要的一個環節。它是公司根據不同企業不同的要求，對其需要的產品進行分揀、包裝以及配貨的過程。物流配送的時效性對于客戶滿意度和企業的日常經營具有較大的影響，而在冷鏈物流的配送中，這種影響則會更為重要。

1 關鍵路徑法

關鍵路徑法簡單來說就是對一個大型的項目進行分解，然后根據估算的各個任務的時間及其活動之間的相互聯系建立起關聯關系，形成一個網絡，通過對建立起的網絡模型求解，就可以找到網絡圖中的關鍵路徑，可通過它追蹤整個計劃實施的進度，對關鍵路徑上的活動進行有效的控制與調整，最后制定出一個最優的方案。

關鍵路徑法的操作步驟大致如下：

（1）列出組成項目的活動清單。每個項目都可分解為一個個小的活動和步驟，正是這些活動按照一定的順序連接起來才形成了整個項目。

（2）確定每項活動的緊前活動。緊前活動即是緊挨著該項活動前面的事件。也可理解為，只有當緊前活動結束時，該項活動才能開展。

（3）估計每項活動的完成時間。

（4）繪制網絡圖。根據活動清單和每項活動的緊前活動來繪制圖形。流程方向用箭頭來表明，箭頭上方標注每項活動的完成時間，節點以圓圈表明，代表事件。

（5）建模求解。關鍵路徑模型是一個相對成熟的模型，運用許多軟件都可以用它進行求解，例如WINQSB、Microsoft Office Project、Matlab、Lingo軟件等。本文主要討論用Lingo軟件進行建模求解的方法。

（6）找出整個項目的關鍵路徑。

2 冷鏈物流

冷鏈物流是國民經濟中的一項重要經濟活動[2]，指生鮮冷凍食品等需要在低溫環境下進行儲存、運輸和配送的一項工程。因為其對穩定的溫度要求較高，所以與其他常溫的物流配送相比，難度和成本也要更高。是否能進行準時的冷鏈物流配送，滿足物流時效的要求，直接關系到物流企業的經濟效益。

在配送問題中應用關鍵路徑法，主要應用到了關鍵路徑是整個項目中持續時間最長的路徑這一特點。可以將物流配送過程中的連接弧抽象為活動，即將一地到另一地的運輸過程看成是一個活動，連接弧上的數字，即兩個地點之間貨物的運送時間看做為該活動執行所需要的時間。所以，就可以根據這個配送模型建立一個計劃網絡圖，在這個計劃網絡圖中，路徑最長也就是配送時間最長的路徑就是關鍵路徑。若是關鍵路徑的長度滿足了配送時效的要求，那么該企業就可以進行及時的物流配送。

3 建立模型

近年來，由于人們對生鮮冷凍食品等的需求，冷鏈物流成為了現代物流發展的重點。V1企業是一家冷鏈物流配送企業，位于圖1中①所示位置， V10企業是一家快餐店，位于圖1中⑩所示位置。V1企業到V10企業的連通路徑如圖1所示，連接弧上的數字表示兩個節點之間貨物的運送時間。現在V1企業承擔了為V10企業運輸冷凍食品的任務，由于貨物的特殊性，V10企業提出V1企業必須在12個小時內將貨物送達，否則車廂里的冷凍食品就會變質。在最壞的情況下，V1企業能否為V10企業進行及時的物流派送是本文要解決的問題。

圖1 連通路徑及時間

4 利用關鍵路徑法求解

本文將求出這個網絡的關鍵路徑，并計算其長度。若是關鍵路徑的長度小于規定配送的時間，則說明就算是在最壞的情況下，V1企業也能為V10企業進行及時的物流派送；否則，V1企業就不能為V10企業進行及時的物流派送。

（1）建立計劃網絡圖

首先，根據圖1建立貨物物流配送作業的數據表（表1）及計劃網絡圖（圖2）。

表1 貨物物流配送作業數據

圖2 相應的計劃網絡圖

（2）寫出相應的規劃問題

設xi是事件i的開始時間，1為最初事件，n為最終事件。希望總的配送時間最短，即目標函數就是求xn的最小值，設tij是作業 i,（ ）j的計劃時間，則對于事件i與事件j有不等式 xj≥xi+tij，由此得到相應的數學規劃問題：

分別用xi，zi表示第i（ i=1,…,10 ）個事件的最早開始時間和最遲開始時間，esij，lsij，efij，lfij分別表示作業 （i,j ）的最早開工時間、最遲開工時間、最早完工時間、最晚完工時間。找出最早開工時間與最遲開工時間相同的作業，就能得到項目的關鍵路徑。

根據問題，有下面的遞推公式：

（3）運用Lingo軟件對上述規劃問題求解

Lingo程序如下：

model:

sets:

events/1..10/:x,z;!x為事件的最早時間，z為事件的最遲時間;

operate（ events,events ）/1 2,1 3,2 4,3 7,4 7,4 5,4 6,6 5,7 8,5 9,8 9,9 10/:t,s,ls,es,ef,lf;!s為松弛變量，ls為作業的最遲開工時間，es為最早開工時間，ef為最早完工時間，lf為最遲完工時間;

endsets

data:

t=1 3 2 2 2 3 3 2 3 2 1 2;

@text（ txt 1.txt）=es,ls;!把計算結果輸出到外部純文本文件;

enddata

min=@sum（ events:x）;

@for（ operate（ i,j ）:x（j）>x（i）+t（ i,j ））;

n=@size（ ev ents）;

z（n）=x（n）;

@for（ events（i）|i#lt#n:z（i）=@min（ operate（ i,j）:z（j）-t（ i,j ）））;

@for（ operate（ i,j ）:es（ i,j ）=x（i ））;

@for（ operate（ i,j ）:lf（ i,j ）=z（j ））;

@for（ operate（ i,j ）:ls（ i,j ）=lf（ i,j ）-t（ i,j ））;

@for（ operate（ i,j ）:ef（ i,j ）=x（i）+t（ i,j ））;

end

運行程序，得出的結果如表2所示，方括號中第1個數字是最早開工時間，第2個數字是最遲開工時間。

表2 作業數據

當最早開工時間與最遲開工時間相同時，對應的作業就在關鍵路線上，因此可以根據表2看出關鍵路線為A→C→G→I→K→M。

關鍵路線是整個計劃網絡的最長路線，現在關鍵路線長度為1+2+3+2+2+2=12，也就是說，在最壞的情況下，V1企業為V10企業進行物流派送所花費的最長時間為12個小時，等于V10企業所要求的12個小時。因此V1企業可以為V10企業進行及時的物流派送。

5 結束語

本文研究了關鍵路徑法在冷鏈物流中的應用，對相關的問題建立了模型，并通過Lingo軟件對該模型進行求解，得到關鍵路徑的長度滿足配送時效的要求，幫助該企業檢測了物流配送的可行性。

[1] 胡運權，郭耀煌.運籌學[M].北京：清華大學出版社，2012.

[2] 翁心剛，安久意，胡會琴.冷鏈物流[M].北京：中國財富出版社，2016.

Application of Critical Path Method Based on Lingo in Cold Chain Logistics

CAO Qian,SONG Xiaoying (Shanghai University of Electric Power,Shanghai 201399,China)

Cold chain logistics is a new form of logistics which developed recently,and the logistics enterprises consider in many aspects for the cold chain distribution.This paper mainly studies the application of critical path method in cold chain logistics. By analyzing the example,we solve the timeliness for the cold chain logistics distribution with the Lingo software.

critical path method;cold chain logistics;Lingo

U116.1

A

1002-3100(2017)08-0043-03

2017-06-05

國家自然科學基金項目，項目編號：61303010。

曹 茜（1982-），女，遼寧沈陽人，上海電力學院經濟與管理學院， 副教授，博士，研究方向：物流與生產調度。