Chuck Holland, Jack Levis, Ranganath Nuggehalli, Bob Santilli, Jeff Winters, UPS Optimizes Delivery Routes, Interfaces, Volume 47, Issue 1, January-February 2017, pp. 8–23. (2016 Franz Edelman Award)
對物流公司而言，如何有效地將貨品送到客戶手中，不僅僅影響公司獲利，也是其競爭力之所在。
在這篇得獎的論文中，詳細說明 UPS 導入作業研究方法時，所遇到組織和技術上的困難。
在運送的過程中，有許多的限制 (constraint)，例如顧客的偏好時間、開車所需的時間等等。決策變數 (decision variable) 是決定運送路徑，以最小化總成本的目標 (objective)，稱為車輛路線問題 (VRP) 或有時間窗的旅行推銷員問題 (TSPTW)，屬於 NP-complete 的問題。當需要運送的客戶數很大時，計算最佳解 (optimal solution) 所需要的時間不符合公司及時的需求 (註 1)，所以利用了多種萬用啟發式演算法 ( meta-heuristics) 以得到次佳解 (suboptimal solution)。在實際的應用過程中，所遇到的困難也包括地圖的精準度不夠、或有錯誤，促使 UPS 收購一家圖資公司；減少左轉，除了之前所說的省油外，也可以 降低發生車禍的機率。
如何讓第一線的司機和其管理者相信演算法所提供的路徑、並實際使用之？剛開始的 2008年， 透過小規模的實驗，一共有 21 位司機利用這套系統送貨，逐年增加到 2016 年的 55000人。開發小組也精心設計模擬遊戲，讓人類和資訊系統競賽並計算總運輸成本，以取得對系統的信賴度。
經過多年的時間，開發和實現系統共花費了 2.95 億美元。但是，估計 (estimate) 每一年節省 3 到 4 億美元，並且降低二氧化碳排放量 10 萬噸。
(註 1) 如果全美司機每天少一分鐘的生產力，UPS 每年的成本是 1500 萬美元。當運送數十站時，可以利用窮舉法 (total enumeration)，比較所有路徑的總成本，找出最佳路徑；只不過，需要點時間。
沒有留言:
張貼留言