目錄 1. 摘要 1 2. 簡介 2 3. 系統環境需求 3 4. 系統架構 4 5. 系統流程 4 6. 資料庫設計規劃 7 7. 配送系統設計規劃配送系統流程圖 9 8. 實際測試網頁端 (

朝陽科技大學資訊工程系專題成果報告物流運輸配送系統指導教授 : 謝富雄教授專題組員 : 莊以愷 (9927010) 李鴻宇 (9927048) 林于迪 (9927078) 中華民國 102 年 12 月

目錄 1. 摘要 1 2. 簡介 2 3. 系統環境需求 3 4. 系統架構 4 5. 系統流程 4 6. 資料庫設計規劃 7 7. 配送系統設計規劃 9 7.1 配送系統流程圖 9 8. 實際測試 15 8.1 網頁端 ( 使用者 ) 15 8.2 Sever 端 ( 管理者 ) 16 8.3 Client 端 ( 司機 ) 21 9. 結論 23 10. 參考文獻 23 I

圖目錄 2.1 VRPSPD 圖 2 4.1 系統架構圖 4 5.1 使用者流程圖 5 5.2 司機流程圖 5 5.3 管理員流程圖 6 7.2.1 Google distance API 抓取距離 11 7.2.2 地圖分割程式 12 7.2.3 交配突變公式 13 7.2.4 Crossover 方法 13 7.2.5 Swap 方法 13 7.2.6 Shift 方法 14 7.2.7 2-opt 方法 14 7.2.8 Exchange 方法 14 7.2.9 Reverse 方法 14 8.1.1 使用者加入會員 15 8.1.2 會員介面 15 8.1.3 會員下單 16 8.2.1 加入車輛 17 8.2.2 加入商店 17 8.2.3 車輛表 17 8.2.4 商店表 18 8.2.5 配車路徑安排介面 18 8.2.6 路徑 1 19 8.2.7 路徑 2 19 8.2.8 路徑 3 20 8.3.1 透過 GPS 系統取得目前位置 21 8.3.2 更新車輛位置 21 8.3.3 更新後車輛資訊 22 8.3.4 司機排班路徑資訊 22 8.3.5 地圖資訊 22 II

表目錄表 6.1 資料庫 Table 7 表 6.2 Car table 7 表 6.3 Commodity table 7 表 6.4 driver table 8 表 6.5 driver_assignment table 8 表 6.6 member table 8 表 6.7 store table 8 表 6.8 route table 9 表 7.2.1 變數代號名稱 11 表 8.2.9 路徑載重, 距離總和 20 III

物流運輸配送系統謝富雄莊以愷李鴻宇林于迪朝陽科技大學資訊工程系 fshsieh@cyut.edu.tw 摘要物流配送無疑是現代物流管理中的重要環節而採用最佳路徑的配送便是物流配送活動中非常重要的工作因此本專題主要是以製作物流配送的雛型為主軸, 促使管理者方便管理會員資料訂單管理及物流配送本專題針對管理者常使用的管理功能做一整合, 而管理功能分別為車輛管理商店據點訂單資訊以及配送路徑最佳化, 而最佳路徑安排則為我們專題探討的核心為了達到最佳的配送路徑, 我們在決策上則需要知道各商店之間的距離, 透過 GOOGLE Distance API 提供實際的距離, 我們運用 particle swarm optimization (PSO) 與 variable neighborhood descent (VND) 方法, 可能找到好的成本低的較優路徑除此之外, 我們的系統提供一個網站讓司機經由手機得到配送路徑, 來導引配送作業關鍵字 : particle swarm optimization (PSO) variable neighborhood descent (VND) Abstract Distribution is undoubtedly an important part in modern logistics management. Finding the best path is very important in distribution logistics and distribution activities. The subject of this study is therefore to implement a prototype system for logistics and distribution to enable managers to easily manage member data, orders, logistics and distribution. The main functions provided in our system include vehicle management, store management, order management and optimization of delivery routes. The core technology is the determination of optimal delivery routes. To determine the best delivery routes, we need to know the distance between the stores. We find the distance between stores through GOOGLE Distance API. By applying the Particle Swarm Optimization with variable neighborhood descent optimization method, our prototype system finds good delivery routes with lower cost. In addition, our system provides a web site for drivers to access their delivery routes via mobile phone to guide their operations. Keyword: particle swarm optimization (PSO) variable neighborhood descent (VND) 2. 簡介由於網路商店的興起, 使用者於網路購買商品後則需要有個方式來配送到買家手中, 因此如何解決物流配送車輛優化調度的問題就逐步成為焦點物流配送車輛優化的問題, 即對固定的裝 ( 卸 ) 貨地點, 選擇較為適當的行車路線讓車輛井然有序的從各個路點通過, 並且在按照要求完成任務 - 1 -

而物流配送車輛優化調度問題, 則是減少配送車輛的運輸成本為了降低運輸成本勢必要縮短運送的距離因此如何安排車輛的行車路線使其總路程最短就是物流配送車輛優化調度需研究的問題現今的智慧型裝置都具有衛星定位功能, 本專題透過 Android 裝置來發送移動位置的資訊, 回傳到後端資料庫, 以即時掌握車輛位置, 並可以決策車輛的配送路徑直接透過智慧型的手機顯示讓司機可以有計畫的去執行配送過程減少車輛在配送過程的成本和時間本專題小組編輯 JAVA 程式碼和製作網頁的 PHP 時採用了 Eclipse[10], 它是一套開放原始碼 (Open Source) 的整合開發環境, 並被廣泛地使用在許多不同的領域 Eclipse 是 Java(Integrated Development Environment, IDE), 可用來編輯編譯執行和除錯特定語言的程式 Eclipse 最初的設計是適用在 Java 程式的開發, 但因其提供了強大的外掛機制可擴充, 亦可用於開發 C/C++ PHP 等程式目前 Eclipse 可在多種作業系統上執行, 使用 Eclipse 編輯編譯執行 Java 程式, 可以很快地上手在 Eclipse 中安裝 Android SDK[7],SDK 模擬器中 DDMS 套件能方便模擬一個不同位置進行測試車輛路徑問題交貨和取貨 (vehicle routing problem with simultaneous pickup and delivery, VRPSPD)[4][5], 假設 G=(N,A) 是一個完整的網路, 其中 N 是車輛的集合, 其中 N0 代表客戶和 Depot 代表倉庫 A 是路線上所需要的花費成本, 成本即為距離在倉庫有相同車輛其載重為 Q, 對車輛的數目沒有限制 VRPSPD 包括尋找每一組路徑的開始和結束的點 ( 倉庫 ), 每個客戶都恰好要被訪問一次每次只通過一輛車, 總車輛在任何負載路線不超過車輛的容量和總路線的最小成本 G 2.1 VRPSPD 圖問題的關鍵是收貨和送貨動作應同時由同一輛車進行因此, 解決一個方案的方法是針對問題制定一個檢查車輛上的負載, 以防止車輛超載該 VRPSPD 的應用中經常碰到連鎖店的配送體系每個商店可能同時具有送貨 ( 如新鮮食品或飲料 ) 和取貨 ( 例如, 過期的東西或空瓶子 ) 的要求該 VRPSPD 是一個 NP-hard 問題, 因為它可以被看作是車輛路徑問題 (vehicle routing problem, VRP), 只有當送貨物時或取貨物時會被考慮本專題的目的是提出一個有效的解決 VRPSPD 的方法該解決方案的方法是粒子群 - 2 -

優化 (particle swarm optimization, PSO) 和領域尋優法 (variable neighborhood descent, VND) PSO 演算法實現解決空間品質的解決方案,VND 是用來改善這些隨機從群體中選擇的每個解決方案, 造成迭代的粒子群演算法結合上述所有方法, 我們必須先取得配送商店的據點, 並取得商店與商店之間的距離車輛的基本可行駛最長距離和載重, 輸入到演算法中進行粒子群優化, 粒子群優化流程 : 先初始化一個粒子評估每個粒子適應度適應後粒子進行比較, 在目前粒子中取得較好適應結果 (pbest), 進行所有粒子的比較再取得適應度最優結果 (gbest), 在進行 (Local Search) 方法主要應用鄰域尋優法來找尋最佳路徑組合, 其目標為成本最小化以及載重最大化, 由於這兩個目標值, 利用鄰域搜尋法的區域搜尋法, 藉由此系統擴大其搜尋範圍, 可以避免落入局部最佳解, 進而找尋更佳的鄰域解管理者再經由演算法取得配送路徑決策, 進行車輛和路徑的安排分配到司機的配送路徑表, 方便司機由手機得到自己的配送路徑 3. 系統環境需求物流運輸配送的系統, 需要人機界面不管是客戶司機或是管理者可以透過 WEB 方便的提供因應的功能, 所以我們使用了 Appserv 架站整合包提供我們設計網也的環境使用 Eclipse 提供設計程式的工作平台透過演算法來演算出最優路徑, 演算法中使用到 Google API 提供路徑資訊, 透過 WEB-SERVICE 可以提供網頁上呼叫演算法來進行配送的決策,WEB-SERVICE 需要 Apache Tomcat 架設取得資源, 司機透過手機 APP 取得工作資訊回傳目前位置 1. APPSERV 2.4.9 架站整合包, 內容如下 Apache 2.0.59 PHP 4.4.7 MySQL 5.0.45 phpmyadmin-2.10.2 2. Eclipse indigo 3. Java EE 7 JDK 4. Apache Tomcat 7.0 5. Android SDK 6. phonegap-2.9.0 7. Google API 4. 系統架構系統架構分為使用者 ( 會員 ) 管理員司機三個部分, 會員需要透過網路連接到網頁,Server 提供會員可以有一組專屬帳號, 透過系統驗證帳號能進行加入訂單修改會員基本資料管理者可以管理車輛商店會員訂單決策排班表和配車功能, 決策系統透過 WEB-SERVICE 存放在 Server 裡讓管理者使用司機會員登入後可以透過 - 3 -

Android 裝置, 進行車輛的位置更新, 也可查看班表及配送資訊圖 4.1 系統架構圖使用者 ( 會員 ) 登入系統後可以加入訂單修改會員基本資料管理員登入系統可以選擇加入商店或加入車輛, 並可進行決策, 執行排班司機透過 Android 裝置, 進行車輛的位置更新, 也可查看班表及配送資訊 5. 系統流程系統流程分為使用者 ( 會員 ) 管理員司機三個部分, 首先會員登入系統,Server 會進行會員的驗證, 驗證失敗回到登入畫面, 驗證成功則跳入會員主畫面並顯示會員基本資訊訂單資訊, 能進行新增訂單修改會員資料, 流程圖如 5.1 司機流程, 司機登入後主頁面提供司機配車配送路徑資訊, 更新目前位置, 查看商店據點地圖, 如圖 5.2 管理者流程, 管理者登入後可以新增商店車輛基本資料, 管理所有會員商店訂單資料司機基本資料規劃司機配車和排班等功能圖 5.3-4 -

圖 5.1 使用者流程圖圖 5.2 司機流程圖 - 5 -

圖 5.3 管理員流程圖 - 6 -

6. 資料庫設計規劃 CAR Commodity Driver Driver_Assignment Member Root Route Store 表 6.1 資料庫 Table 欄位型態備註 Id Int 主鍵,auto increment Car_id Char 車輛編號 Type Cahr 型態 Car_name Char 車名 Car_load Float 載重 Location_X Float 緯度 Location_Y Float 經度 W Float 車輛能力表 6.2 Car table 欄位型態備註 Id Int 主鍵,auto increment Com_id Char 貨物編號 Com_load Float 貨物重量 Send_id Char 寄件者 Recerve_id Char 收件者 Sender_phone Char 寄件者電話 Recerve_phone Char 收件者電話 Earliest_pick_time Date 最早領貨時間 lastest_pick_time Date 最晚領貨時間 Earliest_arriver_time Date 最早到貨時間 lastest_arriver_time Date 最晚到貨時間 Com_source_store_id Char 寄件商店 Com_destination_store_id Char 收件商店表 6.3 Commodity table - 7 -

欄位型態備註 Id Int 主鍵,auto increment Driver_id Char 司機編號 Driver_name Char 司機姓名 Driver_age Char 司機年齡 Driver_phone Char 司機電話 Driver_password Char 司機密碼表 6.4 driver table 欄位型態備註 Id Int 主鍵,auto increment Driver_id Char 司機編號 Car_id Char 車輛編號 Route_id char 路徑編號表 6.5 driver_assignment table 欄位型態備註 Id Int 主鍵,auto increment Username Char 帳號 Pwd Char 密碼 Name Char 會員姓名 Phone Char 會員電話表 6.6 member table 欄位型態備註 Id Int 主鍵,auto increment store_id Char 商店編號 Type Cahr 型態 store_name Char 商店名稱 store_address Float 地址 store_x Float 商店緯度 store_y float 商店經度 L Float 需求量表 6.7 store table - 8 -

欄位型態備註 Id Int 主鍵,auto increment One Char Two Char Three Char Four Char Five Char Six Char Seven Char Eight Char Nine Char Ten Char 表 6.8 route table 7. 配送系統設計規劃配送路徑的決策可以提高效率, 降低工作成本, 使用演算法來優化, 依照車輛的性能, 例如載重車輛最高行車距離, 進行最優路徑的演算下列說明如何做決策, 將成本降低提高效益 7.1 配送系統流程圖 - 9 -

- 10 -

7.2 配送系統說明首先取得資料庫中 car 表格的車輛載重最高行車距離, 在 store 表格讀取各個商店所在的經緯度, 並呼叫 Google distance API 來取得各商店之間的距離, 圖 7.2.1 並透過解析 JSON 格式取得距離圖 7.2.1 Google distance API 抓取距離依照取得各商店之間的距離, 使用 NNH 製造出第一張圖,NNH 方法是以車庫為原點 (Origin) 收尋所有點取得最短距離的點 (N1), 再以 N1 尋找其他點取得最短距離 N2, 以此類推, 推論出第一張圖,(Origin) -> N1 -> N2, 接續使用隨機產生多張圖再經過地圖分割挑選出最優結果並存取下來, 地圖分割程式如下圖 7.2.2 變數名稱 n 商店數量 Load 載重 Cost 路徑距離花費 q 需求量 ( 載重 ) S i 商店 (i) C( 0,sj ) 表示原點到 S i 所需要距離花費 W 車輛載重的限制 L 車輛行駛距離限制 V j P j 紀錄最短的距離花費紀錄每個點所分割路徑編號表 7.2.1 變數代號名稱 - 11 -

程式說明地圖分割程式 Load 存取目前總載重, 下圖紅色字體部分記錄目前總共的路徑花費, 當 Load 和 W 滿足小於車輛所給的限制條件 V i 會記錄下現在的花費 P j 紀錄路徑編號,P j 紀錄方式假設目前是路徑 1 在 W 和 Load 都小於時, 經過的點都會記錄成路徑 1, 當超出就會開始規畫路徑 2, 程式都滿足 n > 商店數量 Load > W cost > L 就會結束地圖分割程式 V 0 = 0; For i = 0 to n do V i = + 無限大 Endfor; Load = 0; cost=0; j = I; Repeat Load = Load +q S i If ( I = j ) then Cost = C(0,s j ) + d S j + C(s j,0 ); else Cost = Cost - C(s j-1,0 )+ C(s j-1, s j ) +d S j + C(s j,0 ); Endif If(load<=W) and (cost<=l) then If V i=1 + cost < V j ; V j = V i=1 +cost ; P j = i-1; Endif J = j+1; Endif Until (j > n) or (Load>W) or (cost>l) endfor 圖 7.2.2 地圖分割程式 - 12 -

地圖分割程式會依據車輛的載重 (load) 和距離 (cost) 切割出多條路徑, 這些路徑會符合車輛需求接著進行基因演算法進行突變交配, 配對出新的後代, 我的依據圖 7.2.3 進行產生新的後代 W 機率內 F 1 進行突變,C 1 C 2 機率內發生交配圖 7.2.3 交配突變公式 Local Search 方法分割出的線段進行一些突變交配 2-OPT 等方法, 方法使用如下列附圖, 再次進行地圖分割再次比較出最優路徑, 輸出路徑 Crossover 方法, 隨機取路徑 N i 的連續路徑第 J 節點到 K 節點, 與隨機路徑 N j 的連續路徑第 J 節點到 K 節點進行交配, 條件須滿足車輛載重及距離圖 7.2.4 Crossover 方法 Swap 方法, 隨機取路徑 N i 的 K 點, 與隨機路徑 N j 的 J 點進行交換, 條件須滿足車輛載重及距離圖 7.2.5 Swap 方法 - 13 -

Shift 方法, 隨機取路徑 N i 的 K 點, 將 K 點加入到隨機路徑 N j, 移除 N i 的 K 點圖 7.2.6 Shift 方法 2-opt 方法, 隨機取路徑 N i 的連續路徑第 J 節點到 K 節點, 設 i=0,(j+i) 和 (K-i) 互換 I+=1 判斷到 (J+1)>(K-i) or (J+1)<(K-i) 圖 2.7.7 2-opt 方法 Exchange 方法, 隨機取路徑 N i 的路徑第 J 節點到 (J+1) 或 (J-1) 節點, 進行交換圖 2.7.8 Exchange 方法 Reverse 方法, 設 i=0 隨機取路徑 N i 的路徑起點 (I+i) 與終點 (J+i) 交換進行交換圖 2.7.9 Reverse 方法 - 14 -

8. 實際測試運輸的系統為了方便讓會員寄送貨物, 同時讓貨運公司方便管理因此設計了後端網路管理系統, 會員如要使用本系統, 需先註冊並成為會員註冊時必須輸入會員的帳號密碼姓名電話等基本資料, 如圖 8.1.1 註冊並登入後, 會員可以查看和修改個人的基本資料和訂單並寄送貨物, 如圖 8.1.2 寄送貨物時系統會自行產生訂單的編號, 寄件者和寄件者的電話會依據會員登入的帳號自行產生, 會員必須輸入貨物重量收件者收件者電話取貨時間和希望送達時間寄件和收件的商店編號, 輸入完成後即可完成訂單, 如圖 8.1.3 8.1 網頁端 ( 會員 ) 圖 8.1.1 使用者加入會員圖 8.1.2 會員介面 - 15 -

圖 8.1.3 會員下單 8.2 Sever 端 ( 管理者 ) 管理者登入到後端之後, 可以加入車輛的編號名稱載重 X 座標 Y 座標和行駛距離等的基本資料, 如圖 8.2.1 管理者也可以加入商店的編號名稱地址 X 座標 Y 座標和需求量等的基本資料, 如圖 8.2.2 當管理者建立好車輛和商店的基本資料後可以管理, 車輛部分可以資料的設定, 載重出發位置, 最遠的行駛距離, 如圖 8.2.3 商店管理部分可以資料的設定, 名稱地址據點位址, 貨物需求量等資訊, 如圖 8.2.4 以上的這 2 個條件都必須具備, 才能進行優化路徑的決策並規劃司機與車輛和路徑的分配, 一位司機只能搭配一輛車和一條配送路徑, 如圖 8.2.5 產生了 3 個路徑分別為 S04=>S03=>S02 S01=>S08=>S09=>S07 和 S06=>S05 這 3 條路徑, 因為車輛載重設為 80, 所以第一條路徑總和剛好 80(40(S04)+20(S03)+20(S02)), 如圖 8.2.6 第二條 80(10(S01)+30(S08)+30(S09)+10(S07)), 如圖 8.2.7 第三條 80(10(S06)+70(S05)), 如圖 8.2.8 最後 3 個的統計所有路徑的載重和行車距離限制, 如圖 8.2.9-16 -

圖 8.2.1 加入車輛圖 8.2.2 加入商店圖 8.2.3 車輛表 - 17 -

圖 8.2.4 商店表圖 8.2.5 配車路徑安排介面 - 18 -

圖 8.2.6 路徑 1 圖 8.2.7 路徑 2-19 -

圖 8.2.8 路徑 3 路徑 1 S04 S03 S02 距離 25.5KM 載重 40 20 20 合計 :80 路徑 2 S01 S08 S09 S07 距離 39.2KM 載重 10 30 30 10 合計 :80 路徑 3 S05 S06 距離 65.4KM 載重 70 10 合計 :80 車輛編號車輛名稱車輛載重車輛行駛距離 ( 公尺 ) C01 C01 80 100000 C02 C01 80 100000 C03 C01 80 100000 C04 C01 80 100000 C05 C01 80 100000 表 8.2.9 路徑載重, 距離總和 - 20 -

8.3 Client 端 ( 司機 ) 司機透過手機連接到網路, 登入後透過 GPS 定位, 本專題的測試是經由 Eclipse 的 Android 套件裡的 DDMS 模擬器來模擬經緯度座標, 如圖 8.3.1 並做即時更新, 如圖 8.3.2 管理者可以進行驗證, 如圖 8.3.3 司機登入後可以知道自己的路徑次序, 以進行貨物配送, 如圖 8.3.4 司機也可以查詢地圖, 如圖 8.3.5 圖 8.3.1 透過 GPS 系統取得目前位置圖 8.3.2 更新車輛位置 - 21 -

圖 8.3.3 更新後車輛資訊圖 8.3.4 司機排班路徑資訊圖 8.3.5 地圖資訊 - 22 -

9. 結論在本專題是製作物流運輸配送系統, 已成功架構出會員的各項功能如 : 註冊訂貨修改個人資料並跟資料庫連結, 使管理員能即時管理貨物狀態駕駛員的功能的可以在手機上觀看個人配送路徑和傳回目前車輛位置管理員則可以在網頁上經由演算法得到較優的路線決策, 以進行車輛的排班以及路線的安排的網頁平台本專題主要是以 PHP 語言和 JAVA 語言為主題下去完成在接觸這次的專題前對網頁的動態語言完全不了解, 雖然有相關書籍可供參考, 但仍經過不少時間才的測試才成功本題中目前完成的系統還不能算是最好, 受限於 Google API 傳送要求的限制, 時間限制內無法要求計算過多的距離, 所以我們專題中的測試範例, 配送的地點也無法太過複雜我們這次採用的車輛路徑最佳化問題的解題方法, 只不過是眾多路徑最佳化方法裡典型的一種, 我們以此方法為基本, 去試著模擬出現行的配送模式, 希望能夠去達成相近於現在商業所使用的決策結果本系統仍有許多不足的地方有待加強, 演算法的邏輯可以再做變更, 目前只是單單以車輛從車庫當出發點為基礎, 並未考慮到各個配送點的寄收貨問題, 雖然可以在路徑結果求得較精確的最佳解, 但如果配送路徑過長貨物多寡等, 超過車輛本身性能的話, 則系統將會無法辨別 10. 參考文獻 [1] 林上傑 / 林康司,JSP2.0 技術手冊, 碁峰資訊,2004. [2] 朱桂英,Android 開發應用 : 基礎篇, 上奇資訊,2011. [3] 陳惠貞 / 陳俊榮,PHP&MySQL 案例開發實戰手冊, 碁峰資訊,2012. [4] Fatma Pinar Goksal &Ismail Karaoglan&FulyaAltiparmak, hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery. Computer & Industrial Engineering 65 (2013)P. 39-53. [5] Christian Prins, simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research Volume 31, Issue 12, October 2004, Pages 1985 2002 [6] Phone gap : http://phonegap.com/ [7] Android SDK : https://developer.android.com/sdk/index.html [8] JAVA JDK: http://www.oracle.com/technetwork/java/javase/downloads/index.html [9] APPSERV : http://www.appservnetwork.com/ [10] Eclipse : http://www.eclipse.org/ - 23 -

目 錄 1. 摘 要 1 2. 簡 介 2 3. 系 統 環 境 需 求 3 4. 系 統 架 構 4 5. 系 統 流 程 4 6. 資 料 庫 設 計 規 劃 7 7. 配 送 系 統 設 計 規 劃 9 7.1 配 送 系 統 流 程 圖 9 8. 實 際 測 試 15 8.1 網 頁 端 (

目錄 1. 摘要 1 2. 簡介 2 3. 系統環境需求 3 4. 系統架構 4 5. 系統流程 4 6. 資料庫設計規劃 7 7. 配送系統設計規劃 9 7.1 配送系統流程圖 9 8. 實際測試 15 8.1 網頁端 (