排程力 Schedule Z 1：軟體使用說明

 壹、Schedule Z資訊

一、基本資訊

  1. 名稱：排程力 Schedule Z
  2. 作者：呂宗霖（演算法、資料結構）、李建廷（輸出介面、功能整合）、賴彥潔（UI設計、輸入介面、串Google map API）
  3. 程式語言：Java
  4. Android版本：8.0 (Oreo)，可兼容約82.7%的設備

二、想要解決的問題

Schedule Z想要解決的問題與價值
  1. 客群：業務（客戶拜訪）、旅行者（景點安排）、出差者（工作規劃）
  2. 問題：有時間窗的旅行推銷員問題 (Traveling Salesman Problem with Time Windows, TSPTW)
  3. 情境：有位旅行者想要安排五天四夜的自由行，手邊有10個想要去的景點，但尚未安排明確時間，同時過夜的飯店地點時間已經決定好了。這些景點，旅行者希望景點(1)~(5)要排在第1~3天、景點(6)~(7)要排在第4~5天、景點(8)~(9)要排在第2~4天、景點(10)要排在第5天。因此旅行者希望能規劃出最短路徑的旅行行程，要符合旅行者要求且不能與舊行程牴觸。

三、Schedule Z價值

  1. 在實用性上，可應用在客戶拜訪、景點安排、工作規劃，具有娛樂與商業價值。
  2. 在新穎性上，Google日曆與地圖並無提供這類的整合性的最佳規劃。
  3. 在技術性上，TSPTW問題是屬於NP-Hard，演算法需特別設計，才能有好的品質。

四、專題發想過程

宗宗之前在力利冷氣工作時，發現每天都會有很多的工作要分派給不同組的師傅們，老闆會希望能排出最順路（最短）的工作行程，一方面節省師傅們的交通時間，另一方面能排更多的工作。由於此APP處理的是排程問題，且這是在力利冷氣中發想的，所以名稱為排程力 Schedule Z。


貳、軟體規格書

一、介面與功能

（一）輸入介面（添加介面）

輸入介面（添加介面）

只要點擊主介面左邊第6個+符號按鈕，即會進入輸入介面：如果對行程長按，則會進入編輯模式。

1. 支援單項行程添加/編輯/刪除：

  1. （必）Title：行程標題
  2. （必）Position：行程地點，支援地點名稱與地址，不支援經緯座標
  3. （必）Type：行程型態，分別為起點 (start)、終點 (end)、新行程 (new)、舊行程 (old)
  4. （必）Start Date：行程開始日期，支援日期選擇介面
  5. （必）Start Time：行程開始時間，支援時間選擇介面
  6. （必）End Date：行程結束日期，支援日期選擇介面
  7. （必）End Time：行程結束日期，支援時間選擇介面
  8. （必）Service Time：行程服務時間，支援時間選擇介面，意指要在此行程停留多久。
  9. （選）Description：行程描述

2. 行程型態特徵：

  1. 起點：Start/End date and time必須一樣且須為所有行程中最早，Service Time不重要。
  2. 終點：Start/End date and time必須一樣且須為所有行程中最晚，Service Time不重要。
  3. 新行程：(Start date and time, End date and time)形成一個時間窗 (time window)，時間窗規範此行程地點的抵達時間，但不規範離開時間。例如：有個行程的時間窗為 (2022/01/18 09:00, 2022/01/18 11:00)，則代表我必早上9點~11點抵達此行程，不可以8點到（早到），也不能12到（晚到），但可以12點離開此行程。
  4. 舊行程：支援兩種格式，Schedule Z會根據起點與終點時間是否相同。
    1. 第一種為起點時間和終點時間相同，則Service Time很重要，例如時間窗為(2022/01/18 09:00, 2022/01/18 09:00)且Service Time為02:00，則此行程一定會被安排在(2022/01/18 09:00, 2022/01/18 11:00)。
    2. 第二種為起點時間和終點時間不同，則Service Time不重要，例如時間窗為(2022/01/18 09:00, 2022/01/18 11:00)，排程後的時間依然不會改變。
    3. 所以舊行程的時間窗不是用於規範抵達時間的範圍，而是真的行程的抵達與離開時間。

（二）輸出介面（主介面）

輸出介面（主介面）

1. 主介面按鈕介紹，由左至右依序介紹：

  1. 範例：左邊第1個E符號按鈕，功能為清除所有行程並導入預設的27項行程。
  2. 全刪：左邊第2個垃圾桶符號按鈕，功能為清除所有行程。
  3. 回顧：左邊第3個時鐘符號按鈕，功能為切換至回顧介面。
  4. 地圖：左邊第4個地圖符號按鈕，功能為將綠色勾勾所選行程，導入到Google地圖，並進行多點導航。
  5. 排程：左邊第5個旋轉符號按鈕，功能為執行多行程最短距離的排程。
  6. 添加：左邊第6個+符號按鈕，功能為添加單項行程。

2. 排程功能說明：

  1. 起點行程不用在第一項，但要是所有行程的最早時間，否則排程會失敗。
  2. 終點行程不用在最後一項，但要是所有行程的最晚時間，否則排程會失敗。
  3. 如果排程失敗，則不會更新時間窗；如果排程成功，則會更新時間窗。
  4. 排程功能含有排序與排程功能，所以排序有變動不代表排程成功，但如果時間窗有被更新，則代表排程成功。

（三）回顧介面

回顧介面

只要點擊主介面左邊第3個時鐘符號按鈕，即會進入回顧介面。在回顧介面中，點擊要回顧的歷史排程，即可看到排程結果。點擊單向行程，即可看到此行程的所有細節。可以看到時間窗被更新，則代表此組行程排程式成功的。位置的部分會有兩個，一個為輸入的資訊，另一個為經緯座標 (緯度, 經度)。

由於Schedule Z沒有建立資料庫來儲存資料，所以如果將Schedule Z從背景中結束執行，則所有資料皆會隨之不見，所以這回顧功能只是顯示暫時歷史資料。

（四）地圖介面

地圖介面：前六項行程的多點導航

先選取要導航的行程，再點擊主介面左邊第4個地圖符號按鈕，即會切換到Google地圖的多點導航模式。

Google地圖功能：

  1. 最大只支援25項行程的多點導航
  2. 排程前或後都可以進行多點導航，因為多點導航只涉及位置，而不涉及到時間。
  3. 此Schedule Z補足Google地圖多點導航沒有對排序做最短距離的優化。

二、Schedule Z 安裝

（一）點擊ScheduleZ載點

會導入到GitHub的網頁，然後點擊View raw開始下載ScheduleZ.apk，瀏覽器的下載區會看到ScheduleZ.apk，同時在檔案管理中的下載區做會看到ScheduleZ.apk。

點擊ScheduleZ載點->點擊View raw->開始下載ScheduleZ.apk

（二）點擊ScheduleZ.apk開始安裝

如果下載成功有自動開啟ScheduleZ.apk，就開始進入安裝模式，並選擇安裝；如果沒有自動開啟ScheduleZ.apk，可以到檔案管理中找到並開啟此檔案。有已安裝應用程式的畫面，即代表安裝成功。

成功安裝 排程力ScheduleZ

（三）開啟檔案管理權限


開啟檔案管理權限，允許來自此來源的應用


三、測試規劃

範例行程：第1~14項行程

範例行程：第15~27項行程

範例中有27項行程，有1項起點、1項終點、5項舊行程、20項新行程，新行程的時間窗可以跨天，為一個六天五夜自由行的規劃。每個景點間的距離會比實際交通距離還短，因為是直接使用大圓距離公式做運算，而交通速度是定速的（30km/hr）。


相關文章

  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.

留言

張貼留言