排程力 Schedule Z 3：結果、結論與心得

伍、結果與結論

一、範例結果

排程前的範例第1~14項行程

排程後的範例第1~14項行程

排程前的範例第15~27項行程


排程後的範例第15~27項行程

以上為範例行程排程前後的比較，可以發現排程後的結果，新行程確實沒有牴觸時間窗，舊行程時間也沒有跑掉，行程與行程之間也沒有重疊，因此這樣的排程是合理的 (feasible)。

雖然VIG_VNS不保證可以獲得最佳解 (optimal solution)，但可以在合理時間內，得到高品質的解，不過每次的解可能會不一樣。

設總行程數為n，則VIG_VNS執行一次迭代的時間複雜度為O(n^3)，而Schedule Z的迭代次數為10*n，因此總時間複雜度為O(n^4)。像範例的27項行程，在Qualcomm Snapdragon 712處理器+8GB RAM，執行時間不到1秒鐘，即可得到此解。

二、Schedule Z可以改進的部分

（一）Google日曆

Schedule Z最遺憾的部分就是沒有將Google日曆串接起來，如果能串接起來，使用上會更方便。期待是舊行程可以從Google日曆導入到Schedule Z，而在Schedule Z添加新行程並跑最佳化排程，最後再將排程資料導回並插入至Google日曆中。這樣同時可以解決：

  1. 舊行程重複在Schedule Z中輸入
  2. 新行程同步插入到Google日曆中
  3. 在Google日曆顯示甘特圖
  4. 直接將資料存儲在在Google日曆中

（二）Google地圖

Google地圖多點導航有串接成功，不過地點的輸入仍稍嫌麻煩，因為還是要打景點名或地址，如果地點的輸入能使用視覺化的地圖來輸入位置，這樣的方式會對使用者更友善。

（三）演算法

1. 交通距離與時間

Schedule Z的距離和交通速度和實際還是有差距的，因為實際距離不可能是直線距離，一定是彎彎曲曲的路線，且交通速度會因為使用不同的交通工具而有所不同。因此交通時間的計算，不應該直接套用大圓距離和固定速度去得到交通時間，而應該要能串Google地圖API，直接得到兩地的交通距離與時間。

2. 多個時間窗

在Schedule Z中，可以發現有跨天的行程被排在一個很奇怪的時間，像是士林夜市的時間窗為 (3 18:00, 6 22:00)，但被排到(6 10:24, 6 12:24)。雖然排程結果沒有違反時間窗，但誰會在白天去逛夜市？因此使用者的意思應該是要在第3~6天的晚上去士林夜市，因此時間窗應該要設計成能支援多個時段，像士林夜市至少要有4個。

3. 多工作分派給多人

其實TSPTW的還是無法解決我在利力冷氣所遇到派工問題，因為在真實的派工現場，是會有多個工作分派給多組師傅群，而非只有一組師傅群。而TSPTW是用於多工作分派給一組師傅的情境，因此真正能解決利力的問題，其實是有時間框的車輛路徑問題 (vehicle routing problem with time windows, VRPTW)。


陸、心得

一、學習力大爆發

我真的覺得我學習力大爆發，Schedule Z是使用Java撰寫的，所以我要用Java寫TSPTW演算法，可是我在這之前沒有學過Java。因此我只花一天學習Java，兩天寫TSPTW演算法，兩天測試與除錯，共歷時五天完成演算法。

不過學過C++後，要快速上手Java其實不難，有很多常用概念是共通的，如：變數、選擇控制、迴圈、函數、基本容器、類別、繼承、多型。只不過有些用字與語法會不一樣，還有一些Java有但C++沒有的功能，但不會這些功能，對於建構演算法沒什麼大礙。

所以其實只要掌握程式語言共同的概念，學習其他的語言就會很快，不過真正難的不在於撰寫程式碼的過程，而是在於定義問題、解決問題、設計與理解演算法其實是更難的。所以學習新語言只是表面能力，定義與解決問題才是核心能力。

因此我覺得我最大的進步是在於核心能力，由於我自己修過演算法課程，且已經知道有TSP問題的存在，然而我所遇到的問題和TSP相似，但多了時間的概念。因此我只花一天的時間就定義好核心問題是TSPTW，而VRPTW是TSPTW更廣義的問題。定義好問題後，先尋找前人對此問題的解決方法是什麼？所幸TSPTW已經有不少學者提出相對應的演算法，因此我再花三天時間閱讀與理解論文。所以四天時間，就完成定義與解決問題的部分，這才是學習力大爆發ＸＤ。

二、使用Git多人協作

由於這份專案是我第一個多人協作的專案，所以我們是用GitHub做統整，git的使用其實沒有想像中的難，再加上GitHub有提供桌面版，所以對初始者蠻友善的。由於我們只有用master分支，沒有開新的分支，所以所有更新都在master分支，這會導致常常發生衝突，同時也因為對其他人程式碼不熟悉，合併過程就容易弄錯。

我們在測試前半小時，才發現Schedule Z行程顯示異常，後來緊急修復，才發現是因為我合併環節出錯，而導致顯示異常。健廷（我組員）還為此感到胃疼，我對此感到抱歉，很抱歉雷了各位ＸＤ，後來有朋友說應該要先開新分支再合併，這樣協作上會更安全。

三、小結

整體來說，這次專案的經驗蠻好的，我對Schedule Z的完成度打80分，剩下的20分就是Google日曆可以改進的部分。整個專案的發想、分工、進度都是我在負責的，由於我有很多領導的經驗，所以這部分處理的蠻順暢的。沒辦法，從大一到現在，每次團體分組，我都是組長的角色，所以我已經放棄當組員的念頭了。

分工部分也是蠻清楚的，主要就三大塊（輸入、輸出、演算法），而且跟組員溝通上算順利，至少兩位組員都知道我們要處理的問題以及我分派的工作是什麼？他們的成品跟我理想上的結果是一致的，所以能證明我和他們的溝通是有效的。

進度的部分雖然稍有落後，但最後成品的完成度還是有的。我還是會去盯其他組員的進度，然後針對他可用的時間與進度，適時修改工作目標。例如：Google日曆還沒串成功且可用時間只有3天，那我就會評估3天時間能串好Google日曆嗎？我覺得不太行，所以就把目標改成顯示清單列。等能夠成功顯示清單列，我們再來談Google日曆，所以在我的進度規劃中，有理想的成品樣子，也有最低的基本要求，以及每個功能重要程度的排序。

最後還是很感謝其他兩位組員的協作與努力，在期限的前一個晚上還熬夜到凌晨5, 6點，繼續除錯與新增功能。據我所知，有些組的組員是只做到最低要求就不做了，他們的成果是高於我的基本要求的。如果我的基本要求是50分，整題成品是80分，那他們就高出30分。有了他們的協作，我可以不用擔心介面與串接的問題，我只要專心處理演算法；而他們也不用擔心演算法，只要專心處理介面與串接問題。


相關文章

  1. 排程力 Schedule Z 1：軟體使用說明
  2. 排程力 Schedule Z 2：演算法介紹｜VIG_VNS for TSPTW
  3. 排程力 Schedule Z 3：結果、結論與心得
  4. Schedule Z載點
  5. Schedule Z程式原始碼
  6. 高等作業系統｜使用者的代理人｜王友群
  7. Page replacement 1：演算法介紹
  8. Page replacement 2：實驗結果與結論
  9. Page replacement source code


參考文獻

  1. Karabulut, K., & Tasgetiren, M.F. (2014). A variable iterated greedy algorithm for the traveling salesman problem with time windows. Inf. Sci., 279, 383-395.

留言

張貼留言