在這個購物和吃飯都可足不出戶的時代，快遞員應該是大部分人接觸最多的第二職業(yè)，第一職業(yè)當然是自己的職業(yè)(從下圖快遞員的搜索趨勢增長就可見一斑)?？爝f員也成為我們最可愛的人，除了爸爸媽媽之外，最關(guān)心我們衣食住行。

對不少都市白領(lǐng)而言，幾乎每天坐電梯去辦公室都會遇到快遞員背著無數(shù)包裹逐層送快遞。發(fā)現(xiàn)大部分快遞員都是采用如下流程：坐電梯直接去到收件人群中的最高樓層，然后從高到底逐層往下送達;或者反之，從低到高逐層投遞，然后從最高的目標層下來。

然而這是最優(yōu)算法嗎，這是閑得蛋疼的作者在本文需要重點討論的問題。

顯然，快遞員對某寫字樓所有快遞送貨的時間(T)是需要優(yōu)化的目標。T=快遞員乘坐電梯的總運行時間(T1)+快遞員乘坐電梯的總?？繒r間(T2)+快遞員在各樓層等待電梯的總時間(T3)+快遞員在每層送貨的總時間(T4)。

• T1，快遞員乘坐的電梯在豎井內(nèi)運動所花費的時間，不含電梯在靜止狀態(tài)下的開門關(guān)門及上下乘客所花費的時間。其最小值是從底層起始樓層到目的地最高樓層然后回到底層的時間。所以最小化只要不走重復路線就可以搞定。(不考慮電梯停靠而需要減速和加速對速度的影響)

• T2，這主要是快遞員從A層到B層時，中間有人上下電梯引起的?？繒r間(包括：電梯開關(guān)門以及乘客上下的時間)。

• T3，在完成每層的送貨之后，需要在該層等待電梯上樓或者下樓去下一個目標樓層。影響該時間的輸入變量極多，不在本次討論范圍之內(nèi)。

• T4，快遞員在每層需要按收件人挨個送貨。其耗時總和與乘坐電梯的策略無關(guān)，也不在本次討論范圍之內(nèi)。

經(jīng)過模型簡化，快遞員要優(yōu)化時間T，核心是優(yōu)化T1和T2。如上所述，T1的最優(yōu)化比較簡單直接，只要不走重復路線或者回頭路，即可最優(yōu)化。T2是本次的優(yōu)化重點。T2主要是因為，在快遞員去往下一個樓層的時候，中途有人上電梯或下電梯導致。而其他人上電梯是完全隱性的，只有同行人(與快遞員同時乘坐電梯的人)下電梯的目標樓層才是顯性的，可以通過查看電梯內(nèi)的樓層面板得到信息。本次優(yōu)化的要點也是通過考慮同行人的目標樓層，動態(tài)調(diào)整快遞員自己的下一個目標樓層使得T2最小，而不是堅持固定的行程。

優(yōu)化算法也很簡單，如下：

• 將行程分為兩段：L1(從最初的起始層開始，?？?次或數(shù)次，到達目的地最高層)和L2(從目的地最高層，?？?次或數(shù)次，回到最初的起始層)

• 在L1的去程中，快遞員的下一個目標樓層，應使得從本層去下一個目標樓層之間有最少的同行人目標樓層(即停靠次數(shù)最小)。如存在多個目標樓層滿足上述條件，取其中的最大值。

• 在L2的回程中，快遞員從高到低，逐層停靠尚未送貨的樓層完成任務(wù)，直到回到最初的起始層。

• 無論在L1還是L2中，如果有他人上電梯且該層為快遞員需要送貨且沒有完成任務(wù)的樓層，立即下電梯完成送貨任務(wù)。

以上論述比較繞口，其實核心就兩條：

• 盡量減少中間有人下電梯增加停靠時間。特別是從下往上的過程中，中途上電梯的概率較低而中途下電梯的概率高，重點要使用策略保證不讓要下電梯的同行人在自己前面而增加?？看螖?shù)。
• 盡量保持機會(option)，當遇到有人上電梯時可以順勢下電梯完成送貨任務(wù)來減少停靠時間。特別是從上往下的過程中，中途下電梯的概率低而中途上電梯的概率高，重點要保留下電梯的機會與上電梯的人同層，可以順勢下電梯完成任務(wù)從而避免?？?。

舉例來說明：

• 快遞員從1層出發(fā)，需要去到3、4、7、9和10層送貨，在1樓上電梯的同行人按下了5層。
• 這時候快遞員的策略是按下4層，先去4層送貨。(避免了5層的停靠，此時3層和4層都滿足該優(yōu)化，但因為4>3，所以先去4層)
• 4層送貨完成后，接著坐電梯去更高樓層送貨。上電梯之后，發(fā)現(xiàn)里面的同行人要去8層，那就按下7層并去該樓層完成送貨。(避免了8層的?？?
• 7層送貨完成后，接著坐電梯去更高樓層送貨，此時電梯內(nèi)沒有同行人，這時按下10層按鈕網(wǎng)上。在9層時，電梯打開有人要上電梯往上，這時順勢在9層下電梯完成送貨。(避免了9層的?？?
• 9層送貨完成后，接著坐電梯去10層送貨。完成后，從10層坐電梯下到3層完成送貨，并最后回到1層。

當然本次討論忽略了許多細節(jié)，比如如何減少每次等待電梯的時間等等。而往往等待電梯是最費時間的，但是從現(xiàn)有的信息來看，等待時間是各種參數(shù)影響而比較隨機，因此無法在模型中考慮而優(yōu)化。

【本文為51CTO專欄作者“數(shù)據(jù)冰山”的原創(chuàng)稿件，轉(zhuǎn)載請通過作者微信公眾號(shujubingshan)獲取聯(lián)系】

戳這里，看該作者更多好文