李天驥

摘要：傳統(tǒng)運(yùn)輸問(wèn)題的目標(biāo)是使運(yùn)輸總費(fèi)用盡量少，而本文的主要目標(biāo)是先滿足醫(yī)療物資的需求，再考慮運(yùn)輸費(fèi)用的問(wèn)題。這個(gè)模型非常重要的應(yīng)用就是當(dāng)緊急事件發(fā)生時(shí)，如新冠疫情，如何有效地將醫(yī)療物資送往各個(gè)醫(yī)療單位，從而盡可能地保障人們的生命安全，同時(shí)在醫(yī)療物資最大限度送達(dá)的條件下盡可能地節(jié)約費(fèi)用。本文將建立一個(gè)緊急事件發(fā)生下的多層級(jí)、多周期運(yùn)輸模型，給出一個(gè)相應(yīng)有效的算法，并通過(guò)計(jì)算機(jī)模擬實(shí)例證明模型與算法的有效性。

關(guān)鍵詞：醫(yī)療物資供應(yīng);運(yùn)輸模型;多層級(jí)多周期運(yùn)輸

中圖分類號(hào)：T21.53 ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

1 引言

醫(yī)療物資是醫(yī)院所需要的治療物資，它有很多種類，并且都在挽救病人生命、保障醫(yī)生安全方面起到了非常重要的作用，因此，醫(yī)療物資的充足供應(yīng)是非常重要的。在今年新冠疫情暴發(fā)初期，多種醫(yī)療物資（如口罩和醫(yī)療防護(hù)服）一度出現(xiàn)了短缺的情況，那么，在不同的情況下能快速有效地將生產(chǎn)的醫(yī)療物資運(yùn)輸至前線，對(duì)于如疫情這樣的緊急事件是至關(guān)重要的，對(duì)此需要建立相應(yīng)的車輛運(yùn)輸模型來(lái)幫助解決問(wèn)題。

人們很早就對(duì)運(yùn)輸相關(guān)的問(wèn)題進(jìn)行了探索。Dantzig和Ramser在1959年便提出了問(wèn)題[1]，意在解決卡車運(yùn)輸石油的最小路徑問(wèn)題，之后Clarke和Wright于1964年將這類問(wèn)題總結(jié)變?yōu)榱嗽O(shè)計(jì)一個(gè)運(yùn)輸路徑，讓車輛將各個(gè)生產(chǎn)廠家的物資以最少的費(fèi)用運(yùn)輸?shù)叫枨笳呤种械木€性規(guī)劃問(wèn)題，也就是人們所熟知的運(yùn)輸中車輛路徑優(yōu)化問(wèn)題（VRP）[2]。

隨著社會(huì)的發(fā)展，最初的車輛路徑優(yōu)化模型已經(jīng)不能滿足人們刻畫復(fù)雜現(xiàn)實(shí)世界的需求，于是更多的包含更多限制條件也更符合實(shí)際情況的車輛運(yùn)輸模型被人們提出。車輛路徑優(yōu)化問(wèn)題的主要拓展方向有帶有車輛容量限制的運(yùn)輸問(wèn)題，帶有時(shí)間窗口的運(yùn)輸問(wèn)題，帶有隨機(jī)變量的運(yùn)輸問(wèn)題，多生產(chǎn)廠家的運(yùn)輸問(wèn)題，多時(shí)間周期的運(yùn)輸問(wèn)題等，這些問(wèn)題均在P Toth，D Vigo于2014年的文獻(xiàn)中有詳細(xì)的介紹[3]。而Braekers等人也對(duì)2015年之前的各類分支研究進(jìn)行了分類與匯總[4]。

近年來(lái)，隨著計(jì)算機(jī)科學(xué)的進(jìn)步，對(duì)于傳統(tǒng)車輛運(yùn)輸路徑優(yōu)化問(wèn)題的探究又有了進(jìn)展。各種算法的誕生使得人們可以更好地解決那些單純用線性規(guī)劃難以解決的實(shí)際情況，如Echeverri等人提出對(duì)于多周期運(yùn)輸問(wèn)題的啟發(fā)式算法[5]，Azadeh等人提出了對(duì)于多生產(chǎn)廠家運(yùn)輸問(wèn)題的遺傳算法[6]，Oliveira等人提出了多生產(chǎn)廠家運(yùn)輸?shù)膮f(xié)同演化算法[7]，Nazari等人運(yùn)用強(qiáng)化學(xué)習(xí)來(lái)解決車輛路徑優(yōu)化問(wèn)題[8]。同時(shí)，人們也將多種限制條件結(jié)合，使得模型與實(shí)際情況更加相似，如Mancini等人將多生產(chǎn)廠家與多時(shí)間周期的條件相結(jié)合[9]。此外，Coelho等人還對(duì)模型在現(xiàn)實(shí)中的應(yīng)用進(jìn)行了研究，驗(yàn)證了模型的可靠性[10]。Zhu等人研究了物資需求不確定情形下的路徑優(yōu)化問(wèn)題[11]。但這并不代表著人們對(duì)于車輛運(yùn)輸?shù)膯?wèn)題就已經(jīng)完善，對(duì)于多層級(jí)運(yùn)輸這一類在現(xiàn)實(shí)生活中十分常見(jiàn)的情況的研究便不十分充分。

在如新冠疫情這類緊急突發(fā)事件中，真實(shí)情況可能比這些現(xiàn)有的模型要復(fù)雜。首先，整個(gè)過(guò)程中一定包含多個(gè)供應(yīng)廠家和有需求的定點(diǎn)醫(yī)院;其次，在全國(guó)范圍內(nèi)的運(yùn)輸通常并不是直接由用供應(yīng)商發(fā)送到對(duì)應(yīng)的需求地，而是多層級(jí)運(yùn)輸，在物資運(yùn)送過(guò)程中需要經(jīng)由一些中轉(zhuǎn)站;此外，整個(gè)事件的跨度相對(duì)來(lái)說(shuō)是較長(zhǎng)的，正常的單周期運(yùn)輸模型難以準(zhǔn)確地為其提供參考。目前現(xiàn)有的研究中還并沒(méi)有將多生產(chǎn)廠家、多時(shí)間周期與多層級(jí)供應(yīng)同時(shí)聯(lián)系起來(lái)進(jìn)行探討。特別是整個(gè)運(yùn)輸模型的準(zhǔn)則也是先盡可能地滿足防護(hù)服的需求，其次再盡可能地節(jié)省運(yùn)輸?shù)馁M(fèi)用。在此背景下，針對(duì)性地建立了一個(gè)多階段、多時(shí)間周期的運(yùn)輸模型來(lái)解決問(wèn)題。

2 模型建立

根據(jù)實(shí)際情況，模型是由多個(gè)生產(chǎn)廠家經(jīng)由多個(gè)中轉(zhuǎn)站運(yùn)送到多個(gè)有需求的醫(yī)院。首先要盡量使醫(yī)院的需求量得到滿足，再讓運(yùn)輸?shù)目傎M(fèi)用盡可能小。

下面是一些決策變量和參數(shù)：

令A(yù)為所有廠家的集合|A|=M，B為所有中轉(zhuǎn)站的集合|B|=N，C為所有醫(yī)院的集合|C|=L。假設(shè)所有貨物必須經(jīng)過(guò)中轉(zhuǎn)站。任意 i∈A，j∈B，可構(gòu)成?。?i，j ）;同理任意 j∈B，k屬于C可構(gòu)成?。?j，k ）。從而形成整個(gè)運(yùn)輸網(wǎng)絡(luò)。因?yàn)檫@是一個(gè)多周期問(wèn)題，所以會(huì)有時(shí)間量t。

3 算法設(shè)計(jì)

首先按時(shí)間順序找出在這n天中供應(yīng)量大于需求量的天 。對(duì)其中最早的第 ? 天，首先判斷當(dāng)天供應(yīng)量與需求量之差，也就是理論最大剩余量與之后所有天的需求量之和做對(duì)比，若理論最大剩余量大于等于后面所有天的需求量之和，則按照之后所有天的需求量總和作為當(dāng)天剩余量進(jìn)行單周期的運(yùn)輸模型計(jì)算，后面所有天不再運(yùn)輸;若理論最大剩余值小于后面所有天的需求量之和，則以理論最大剩余量為當(dāng)天剩余量將 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?算出來(lái)。將原本的下一天的每家醫(yī)院的需求量分別與 n1天的剩余量相減得到新的需求量， ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ，判斷 n1+1天總供應(yīng)量之和與總需求量的大小，若總需求量更大，則求出這天的運(yùn)輸情況并停止;若供應(yīng)量更大，則重復(fù)對(duì)于第天進(jìn)行的操作，直至到一天需求量大于等于供應(yīng)量，或理論最大剩余量大于后面所有天的需求量之和，求出這天的運(yùn)輸情況并停止。之后再找到下一個(gè)供應(yīng)量大于需求量且還未確定運(yùn)輸方式第 ? 天，重復(fù)對(duì)于 ? 天的操作，直至所有供應(yīng)量大于需求量的天都以此被操作。最后再將所有還未被處理過(guò)的天按照模型進(jìn)行單周期求解。這時(shí)就得到了整個(gè)周期的運(yùn)輸情況。

4 計(jì)算機(jī)仿真

根據(jù)以上的模型和算法，我模擬一個(gè)醫(yī)療物資運(yùn)輸?shù)膶?shí)況，以2020年武漢新冠疫情為例。疫情爆發(fā)，市內(nèi)的十幾個(gè)指定接待新冠病人的醫(yī)院已經(jīng)滿員，醫(yī)療防護(hù)服的儲(chǔ)備已經(jīng)用完，需要有資格生產(chǎn)醫(yī)療防護(hù)服的企業(yè)迅速恢復(fù)生產(chǎn)和供應(yīng)。此外，我考慮此次運(yùn)輸方式為火車加貨車，認(rèn)為貨物會(huì)先集中到武昌站、武漢站、漢口站再統(tǒng)一運(yùn)到各個(gè)醫(yī)院。

接收新冠病人的方艙醫(yī)院標(biāo)號(hào)與名稱見(jiàn)表1，生產(chǎn)防護(hù)服的企業(yè)標(biāo)號(hào)與名稱見(jiàn)表2。

接下來(lái)對(duì)接收新冠病人的醫(yī)院的需求量進(jìn)行估計(jì)：

每位醫(yī)護(hù)人員需要每4小時(shí)更換一套防護(hù)服，對(duì)于此時(shí)的緊急情況我們假設(shè)方艙醫(yī)院都是按照三級(jí)甲等醫(yī)院的標(biāo)準(zhǔn)，每床至少配備1.03名衛(wèi)生技術(shù)人員和0.4名護(hù)士，此時(shí)緊急情況要24小時(shí)不間斷滿足此標(biāo)準(zhǔn)。記醫(yī)院k的床位數(shù)為cK， 那么此時(shí)每天所需的防護(hù)服量dK = cK×（1.03+0.4）×6，但因?yàn)槊刻焱话l(fā)情況可能會(huì)發(fā)生的，所以我假定每天醫(yī)院的需求量在基準(zhǔn)值dK 上下波動(dòng)，需求量函數(shù)為隨機(jī)函數(shù)，每天的需求量由電腦隨機(jī)生成。

各個(gè)方艙醫(yī)院公布的床位數(shù)量見(jiàn)表3。

由此可計(jì)算出醫(yī)院每天對(duì)防護(hù)服的需求量見(jiàn)表4。

接下來(lái)對(duì)這些企業(yè)的生產(chǎn)能力進(jìn)行估計(jì)：

因?yàn)獒t(yī)療防護(hù)服是通過(guò)生產(chǎn)線來(lái)生產(chǎn)的，而在規(guī)格相同的情況下每條生產(chǎn)線需要的工人數(shù)量是一定的，因此可以用人數(shù)來(lái)估計(jì)生產(chǎn)能力。根據(jù)相關(guān)公司的生產(chǎn)能力及員工數(shù)數(shù)據(jù)，算出一名員工正常工作一天約可生產(chǎn)100套醫(yī)用防護(hù)服，再根據(jù)公司公布的社保員工人數(shù)可知公司正常工作時(shí)的生產(chǎn)量。再根據(jù)公司恢復(fù)生產(chǎn)的時(shí)間，假定生產(chǎn)是線性恢復(fù)的，我得出了各個(gè)公司恰好完全恢復(fù)生產(chǎn)的產(chǎn)能以及公司生產(chǎn)量恢復(fù)函數(shù) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ，其中，a為完全復(fù)工時(shí)的產(chǎn)能，開始復(fù)工的第一天t =1。企業(yè)在恢復(fù)生產(chǎn)之后又繼續(xù)進(jìn)行了產(chǎn)能的增加直至產(chǎn)能與需求基本平衡。

根據(jù)產(chǎn)能恢復(fù)函數(shù)和恰好完全恢復(fù)生產(chǎn)時(shí)的產(chǎn)能，可以得出整個(gè)周期中這些公司的產(chǎn)能，見(jiàn)表5。

接下來(lái)需要得到運(yùn)輸時(shí)間，根據(jù)查得的各個(gè)廠家與醫(yī)院到中轉(zhuǎn)站的距離，假定因緊急事件需快速運(yùn)輸，火車時(shí)速為160 km/h，貨車時(shí)速為40 km/h，算出運(yùn)輸時(shí)間，表6為生產(chǎn)企業(yè)到中轉(zhuǎn)站的時(shí)間，表7為醫(yī)院到中轉(zhuǎn)站的時(shí)間。

在得到了所有需要的量之后，便可以通過(guò)電腦算出每天由生產(chǎn)企業(yè)發(fā)往中轉(zhuǎn)站的防護(hù)服數(shù)量見(jiàn)表8，以及每天由中轉(zhuǎn)站發(fā)往各方艙醫(yī)院的防護(hù)服數(shù)量見(jiàn)表9。

可以看到，當(dāng)供應(yīng)量小于需求量的時(shí)候，運(yùn)輸量全部等于供應(yīng)量;而當(dāng)供應(yīng)量較多時(shí)，運(yùn)輸量便等于需求量，結(jié)果很好地滿足了模型先盡可能滿足需求再使得花費(fèi)盡可能小的目標(biāo)。

根據(jù)數(shù)據(jù)得到的結(jié)果，可以知道，當(dāng)理論供應(yīng)量大于需求量時(shí)，各個(gè)企業(yè)應(yīng)該運(yùn)輸多少套防護(hù)服以避免浪費(fèi);同時(shí)我們可以發(fā)現(xiàn)，在生產(chǎn)量不變的情況下，有時(shí)將企業(yè)生產(chǎn)的防護(hù)服送往兩個(gè)乃至多個(gè)中轉(zhuǎn)站是更加節(jié)約物資的方式，為現(xiàn)實(shí)中多種不同情況的物資運(yùn)輸提供了建設(shè)性的意見(jiàn);此外可以推斷出當(dāng)需求量較少時(shí)，將病人集中在特定的幾家醫(yī)院是從經(jīng)濟(jì)上更優(yōu)的方式，為面對(duì)疫情時(shí)如何安置病人也具有一定的參考價(jià)值。

通過(guò)計(jì)算機(jī)仿真可以看出建立的模型，以及相應(yīng)的算法是實(shí)際有效的，只要給定模型中的各個(gè)參數(shù)，模型就可以提供出一份多階段、多周期的運(yùn)輸方式，這個(gè)結(jié)果對(duì)于決策者有非常直觀的參考價(jià)值。

5 結(jié)語(yǔ)

本文考慮了緊急事件中醫(yī)療物資的多層級(jí)、多周期供應(yīng)問(wèn)題，建立了以滿足需求量為主要目標(biāo)，節(jié)約經(jīng)濟(jì)為次要目標(biāo)的優(yōu)化模型，并為模型設(shè)計(jì)出了一個(gè)快速有效的算法，最后通過(guò)計(jì)算機(jī)仿真所得到的計(jì)算結(jié)果驗(yàn)證了模型的有效性、合理性，說(shuō)明模型的算法對(duì)實(shí)際決策有很大幫助。

（責(zé)任編輯：武多多）

參考文獻(xiàn)：

[1] Dantzig G B， Ramser J H. The truck dispatching problem[J]. Management science， 1959， 6（1）： 80-91.

[2] Clarke G， Wright J W. Scheduling of vehicles from a central depot to a number of delivery points[J]. Operations research， 1964， 12（4）： 568-581.

[3] Vehicle routing： problems， methods， and applications[M]. Society for Industrial and Applied Mathematics， 2014.

[4] Braekers K， Ramaekers K， Van Nieuwenhuyse I. The vehicle routing problem： State of the art classification and review[J]. Computers & Industrial Engineering， 2016， 99： 300-313.

[5] Echeverri L C， Froger A， Mendoza J E， et al. A matheuristic for the Multi-period Electric Vehicle Routing Problem[C]. 2019.

[6] Azadeh A， Farrokhi-Asl H. The close–open mixed multi depot vehicle routing problem considering internal and external fleet of vehicles[J]. Transportation Letters， 2019， 11（2）： 78-92.

[7] de Oliveira F B， Enayatifar R， Sadaei H J， et al. A cooperative coevolutionary algorithm for the multi-depot vehicle routing problem[J]. Expert Systems with Applications， 2016， 43： 117-130.

[8] Nazari M， Oroojlooy A， Snyder L， et al. Reinforcement learning for solving the vehicle routing problem[C]//Advances in Neural Information Processing Systems. 2018： 9839-9849.

[9] Mancini S. A real-life multi depot multi period vehicle routing problem with a heterogeneous fleet： Formulation and adaptive large neighborhood search based matheuristic[J]. Transportation Research Part C： Emerging Technologies， 2016， 70： 100-112.

[10] Coelho L C， Renaud J， Laporte G. Road-based goods transportation： a survey of real-world logistics applications from 2000 to 2015[J]. INFOR： Information Systems and Operational Research， 2016， 54（2）： 79-96.

[11] Zhu， Jianming， Liu S， Ghosh S. Model and Algorithm of Routes Planning for Emergency Relief Distribution in Disaster Management with Disaster Information Update [J]. Journal of Combinatorial Optimization， 2019， 38（1）： 208-223.