應用離散型粒子群演算法於大尺寸電視配送服務排程問題

Abstract

大尺寸電視在進行配送服務的排程規劃時，受限於顧客的時間、可用於運送安裝的車型、車輛容量與行走路徑、技術人員與其工作時間等限制，是一種複雜型的車輛途程問題(Vehicle Routing Problem, VRP)。當廠商可以選擇使用自營車隊或是外包的方式進行此配送服務時，則必須由利潤的角度而非傳統的成本角度考慮此項排程問題。因此，本研究將具有以上複雜限制的大尺寸電視配送服務排程規劃問題定義為具時窗限制之多車種固定車隊團隊越野競賽問題(Heterogene- ous fleet Team Orienteering Problem with Time Window, HFTOP-TW)，其中包含會考量到收益的團體越野競賽問題(Team Orienteering Problem, TOP)、有限制車隊之多車種車輛途程問題(Heterogeneous fleet Vehicle Routing Problem, HFVRP)與時間窗(time window)限制。本研究先建立一個數學模型表示HFTOP-TW問題，由於此問題為未定多項式難度(non-polynomial hard, NP-hard) 問題，故本研究使用離散型粒子群演算法(Discrete Particle Swarm Optimization, DPSO)來求解此問題。本研究先設計了一套能夠產生初始解的演算法，再使用貪婪式的途程改善策略來有系統地搜尋更好的解。最後，本研究透過模擬例題進行求解測試以確認本研究所提出之方法的可行性與有效性。由實驗結果可知本方法能求得最佳解的機率為94%，表示本研究之求解方法適用於求解此類服務配送排程問題。而此測試結果也驗證了DPSO演算法之價值並可作為相關產業實務上的參考依據，讓業者能在合理的時間內作出較佳的決策以達到最大化整體利潤的目的。

Scheduling of deliveries of large-sized televisions is constrained due to many aspects. For instance, delivery times, delivery vehicles, vehicle’s capacities, delivery routes, limitations with respect to the business hours and personnel abilities. Therefore, delivery of large-sized televisions is a complicated Vehicle Routing Problem (VRP). Whether it is utilizing the company vehicles or outsourcing delivery vehicles, it should be evaluated based on a profit-maximizing perspective rather than the traditional cost minimizing standpoint in order to plan out the scheduling. Therefore, with all the constraints being taken into consideration, scheduling of delivering large sized televisions is a Heterogeneous Fleet Team Orienteering Problem with Time Window (HFTOP-TW). HFTOP-TW is consisted of Team Orienteering Problem (TOP), Heterogeneous Fleet Vehicle Routing Problem (HFVRP), and time window constraint. This research starts by constructing a mathematical model to demonstrate the HFTOP-TW. Due to the fact that this problem is non-polynomial hard (NP-hard), this research applies the Discrete Particle Swarm Optimization (DPSO) for solving such a problem. This research first proposes an algorithm that can calculate initial solutions, then it utilizes greedy route improving strategy to systematically search for better solutions. This research is conducted, tested based on experiments proposed by other researchers in order to prove the effectiveness and efficiency of the proposed method. As per research result, the proposed method has 94% chance of acquiring the best solution. This shows that the proposed method is suitable for solving the scheduling deliveries and services of large-Sized televisions. On top of that, the result also proved the value of the application of the DPSO algorithm and it could be used to maximize profits within reasonable time windows.