基于Lingo的關(guān)鍵路徑法在冷鏈物流中的應(yīng)用

曹 茜，宋筱影 （上海電力學(xué)院，上海 201399）

·現(xiàn)代物流·

基于Lingo的關(guān)鍵路徑法在冷鏈物流中的應(yīng)用

曹 茜，宋筱影 （上海電力學(xué)院，上海 201399）

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

關(guān)鍵路徑法；冷鏈物流；Lingo

0 引言

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

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

1 關(guān)鍵路徑法

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

關(guān)鍵路徑法的操作步驟大致如下：

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

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

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

（4）繪制網(wǎng)絡(luò)圖。根據(jù)活動清單和每項活動的緊前活動來繪制圖形。流程方向用箭頭來表明，箭頭上方標(biāo)注每項活動的完成時間，節(jié)點以圓圈表明，代表事件。

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

（6）找出整個項目的關(guān)鍵路徑。

2 冷鏈物流

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

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

3 建立模型

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

圖1 連通路徑及時間

4 利用關(guān)鍵路徑法求解

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

（1）建立計劃網(wǎng)絡(luò)圖

首先，根據(jù)圖1建立貨物物流配送作業(yè)的數(shù)據(jù)表（表1）及計劃網(wǎng)絡(luò)圖（圖2）。

表1 貨物物流配送作業(yè)數(shù)據(jù)

圖2 相應(yīng)的計劃網(wǎng)絡(luò)圖

（2）寫出相應(yīng)的規(guī)劃問題

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

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

根據(jù)問題，有下面的遞推公式：

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

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為作業(yè)的最遲開工時間，es為最早開工時間，ef為最早完工時間，lf為最遲完工時間;

endsets

data:

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

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

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

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

表2 作業(yè)數(shù)據(jù)

當(dāng)最早開工時間與最遲開工時間相同時，對應(yīng)的作業(yè)就在關(guān)鍵路線上，因此可以根據(jù)表2看出關(guān)鍵路線為A→C→G→I→K→M。

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

5 結(jié)束語

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

[1] 胡運權(quán)，郭耀煌.運籌學(xué)[M].北京：清華大學(xué)出版社，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

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

曹 茜（1982-），女，遼寧沈陽人，上海電力學(xué)院經(jīng)濟與管理學(xué)院， 副教授，博士，研究方向：物流與生產(chǎn)調(diào)度。