
下面的鏈接是精華版思路,亮點是對第六問的探討。
高度概括一下:第一問曼哈頓,第二問用免疫,三問增加任務單,四問增加揀貨員,五問改變復核臺,六問亮點來探討~ 有點皮
MathorCup C題 倉內揀貨優化問題?mp.weixin.qq.com
————————————————————————
編程實現時的思路,就在這里啦~
https://zhuanlan.zhihu.com/p/143159905?zhuanlan.zhihu.com
————————————————————————
以下是賽題思路分析?
背景:
接到訂單到商品出庫的流程,定位 組單 揀貨 復核 打包。
定位:倉庫有貨架,每貨架有多個貨格,商品擺放在貨格中,且每個貨格最多擺放一種商品,商品可以擺放在多個貨格。訂單下達倉庫后,定位操作,確定商品下架的貨格和每個貨格下架的商品數量。
組單:單個客戶訂單商品數量少,對于中小件商品倉庫,需要將多個客戶的訂單合并,構成任務單,這就是組單操作。
揀貨:揀貨員在某復核臺領取揀貨車及任務單,根據推薦順序下架任務單中商品。下架完畢后,揀貨員將揀貨車送往某復核臺,隨后揀貨員開始下一次揀貨。
備注:
(1) 揀貨員開始和結束復核臺可以不一致。
(2) 一個揀貨員負責對多個任務單時,每次只能揀一個任務單的商品。同一任務單,貨格訪問順序不同,行走距離也有差異。
(3) 揀貨員的行走速度為 1.5m/s,商品下架過程,對任意一個貨格,若下架商品數量小于 3 件,每件完成下架花費 5 秒,否則每件花費 4 秒。多人同時在一個貨格揀貨,不考慮等待的時間(感覺與問題六的暢銷品所在貨架可能擁擠,反而降低揀貨效率有點沖突)。
復核和打包:復核臺進行復核,然后將商品打包。
備注:
(1) 只有復核臺正常工作時,才可以進行復核打包操作,每個訂單復核和打包花費30 秒。
(2) 揀貨車先送到復核臺后,復核臺才能對該任務單中商品進行復核和打包。
(3) 若一個復核臺完成該復核臺所有任務單的復核和打包,沒有新任務前,該復核臺將處于空閑狀態。從0 時刻到 TOTAL_TIME 時刻,若一個復核臺總空閑時間為 IDLE_TIME,則該復核臺利用率=1-IDLE_TIME/TOTAL_TIME。多人同時到達一個復核臺時,需要考慮等待的時間。
注:當一個人有多個任務時,只能一個一個任務完成,不能在完成一個任務過程中揀另一個任務的貨。
問題 1:按照圖中距離標示,設計一種計算 3000 個貨格和 13 個復核臺總共 3013 個元素之間距離的方法。

圖 2 給出揀貨員在倉內路線示例(L1-L7)。
當揀貨員在倉庫中揀貨時,需要在貨格之間、貨格與復核臺之間、復核臺與復核臺之間行走。由于這些行走通常要繞過障礙物,不能直接采用坐標計算歐幾里得距離。
(附件中貨架坐標可理解為第一個貨格左下角坐標,如 S001 的(x,y)表示貨格 S00101 的坐標。其他相類似。復核臺坐標也理解為左下角坐標。 )
思路: 計算每個貨格和復核臺到其他貨格與復核臺的距離是這道題的基礎。之后的解題也需要這個結果,計算出來后存儲起來,方便之后調用。
問題 2:請給 P 規劃理想的揀貨路線,包括貨格訪問順序、返回的復核臺,計算完成出庫花費的時間。
假設所有復核臺正常工作,任務單 T0001 等待揀貨,揀貨員 P在復核臺 FH10 領取了任務單 T0001。完成出庫花費的時間(揀貨員揀貨開始到所有任務復核打包完成花費的時間)
思路: 已經確定1個任務單和1個復核臺,1個揀貨員,將任務單中的每一個商品作為圖中的一個點,用在問題一中計算的每個商品所在貨格到其他商品貨格之間的距離作為兩點之間的連線。就把問題二作為了一個圖論的遍歷最短路徑問題。
問題 3:給 P 指定任務領取順序,規劃理想的揀貨路線,使得這些任務盡快出庫。請計算完成出庫需要花費的時間和每個復核臺利用率。
假設 2 個復核臺 (FH03,FH11)正常工作,5 個任務單(T0002-T0006)等待揀貨,繼續由揀貨員 P 負責揀貨, P 初始位置為 FH03。
思路: 已經確定5個任務單和2個復核臺,1個揀貨員。先同問題二,把五個任務單的最短遍歷求出,計算時間。然后使用排隊理論,如果總等待時間最短,則越短的任務單應該越優先。然后計算出庫總花費時間和復核臺利用率。
問題 4:給每個揀貨員分配任務單、 起始揀貨復核臺,并分別規劃理想的揀貨路線,使得 49 個任務單盡快完成出庫,并計算完成出庫需要花費的時間和每個復核臺利用率。
假設 4 個復核臺(FH01,FH03,FH10,FH12)正常工作,49個任務單(T0001-T0049)等待揀貨,9 個揀貨員(P1-P9)負責揀貨。
思路: 在問題二的基礎上最大的改變是提高了揀貨員,那么會造成的影響是可能存在復核臺等待的問題。不過不影響揀貨員揀貨。 在此我們可以結合題意,假設領揀貨車與復核臺進行復合可以同時進行。因為“領揀貨車及任務單,領取時間不計”。 然后同問題三,越短的任務單越優先,計算出庫總花費時間和復核臺利用率。
問題 5:在問題 4 中,有 4 個復核臺(FH01,FH03,FH10,FH12)正常工作,請評估增加一個正常工作的復核臺對出庫時間的影響。
思路: 我們一共有13個復核臺,分別計算增加其他9個復核臺對最終出庫時間的影響。 使用一個for循環,計算一下五個復核臺的情況即可。
問題 6:對于倉內商品擺放問題,你有什么建議?
商品在貨架中的擺放位置,會影響揀貨效率。若將暢銷品放置在離復核臺較近的位置,揀貨員行走距離相應減少,但暢銷品所在貨架可能擁擠,反而降低揀貨效率。
思路: 問題六沒有要求建模,只要求給商品擺放的意見,那么根據信息論的變長最優編碼——“越常用的符號用越短的編碼表示”的思想,越暢銷也就是越需要經常取貨的商品,需要離復核臺越短。
我只提幾種意見,我們可以考慮的建議包括:
將暢銷排名最靠前的n種商品依照排序依次放在離復核臺最近的貨格上。
計算每個貨架到復核臺的平均距離,把商品依照暢銷排名與每個貨格的平均距離一一匹配。