# Our Algorithm ## A brief introduction Group *Sleeptime Error* @ PD 110-1 Midterm Project --- # Outline 1. 協作歷程 2. 最終版演算法介紹 3. 反思與改進空間 --- # 協作歷程  ---- ## 初期 - 確立好工作模式，建立統一的Coding Style標準 - 共同構想演算法（此時每個人都有提出對這個問題的見解）  > 圖：本組劉姓同學大放厥詞 ---- ## 中期 - 確認好演算法方向 - 單中心補貨採劉冠甫同學的方案 - 由 劉冠甫、孫浩恩、林蓆葦共同實作 - 多中心捕貨採邱秉辰、梁晏誠同學的方案 - 並同時由該兩人實作 ---- ## 後期 - 12/10 完成兩組程式碼合併 - 合併後最高利潤 $$40,496,022$  ---- ## 最後一天的暴衝 - Deadline的力量 - 總圖MTP之夜 - 最終分數：$$56,194,075$  ---- ## 工作分配  --- # 最終版演算法介紹 :::warning **此演算法單中心與多中心的實作手法大同小異** 因此此處會**以多中心為例**介紹演算法主題，隨後再說明單中心與多中心的細微差異 ::: ---- # 多中心補貨 1. 我們把物流中心按照其==固定成本與容量的比值==**由小到大**排序 ```cpp sort(lgArr, lgArr + lgCnt, cmpByFixedCost); bool cmpByFixedCost(Lg a, Lg b) { return a.fixedCost < b.fixedCost; } ``` ---- 2. 排序好之後，我們就開始從固定成本最小的零售中心開始選擇零售店了！ ---- - 用 ==$(𝑟𝑡𝑅𝑒𝑣𝑒𝑛𝑢𝑒 − 𝑟𝑡𝐹𝑖𝑥𝑒𝑑𝐶𝑜𝑠𝑡 ∗ 𝜃_1) / 𝐷𝑒𝑚𝑎𝑛𝑑$== 對零售中心**由大到小**排序 - 經過試驗，$\theta_{1} = 0.95$時可以帶來最高的利潤 ---- - 試算 - 該物流中心可獲得的最高利潤 $testProfit$ - 第一個使得$rtRevenue - rtFixedCost < 0$的索引值 $index$ ---- - 變數R在此代表**我們要將前R名的零售店配給這個物流中心** - $R = min(\theta_2,index)$ - 經過試驗，$\theta = 36$時可以帶來最高的利潤 ---- - 判斷$testProfit$是否為正 - 若為正，將前$R$個零售店指派給這一個物流中心 - 若否，不需要執行任何動作 ---- 以上步驟執行到所有物流中心都跑完為止！ --- # 單中心補貨 ---- 1. 新建立一個bool陣列紀錄該零售店是否已經有物流中心供應 ```cpp= bool* selected = new bool[rtCnt]; for(int i = 0; i < rtCnt; i++) { selected[i] = 0; } ``` ---- 2. 在執行更新動作時，判斷該零售店是否已經有物流中心供應 - 若有，跳過此次更新操作 ```cpp= if(supplies > 0 && selected[rtArr[k].id - 1] == 0) { selected[rtArr[k].id - 1] = 1; update(lgArr[i], rtArr[k], supplies, table); } ``` ---- 3. 能為Single Source 帶來較高利潤的參數值（目前） $$\theta_1 = 1, \space \theta_2 = 37$$ --- ### 掃描QR Code，查看演算法的圖解  --- # 改進空間 ### 或許該算法有忽略一些狀況 - 該算法在每一次更新供貨數量時，供貨數量都設為 $min(dmd,cap)$ - 在多中心補貨的情況中，最佳的情況一定是要供應$min(dmd,cap)$嗎？ - 是不是會有更佳的分配方案? --- ## Thanks for your listening