排程力 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已經有不少學者提出相對應的演算法,因此我再花三天時間閱讀與理解論文。所以四天時間,就完成定義與解決問題的部分,這才是學習力大爆發XD。

二、使用Git多人協作

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

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

三、小結

整體來說,這次專案的經驗蠻好的,我對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.

留言