标题: | 应用离散型粒子群演算法于大尺寸电视配送服务排程问题 Applying Discrete Particle Swarm Optimization to Scheduling Deliveries and Services of Large-Sized Televisions |
作者: | 张哲维 张永佳 工业工程与管理系所 |
关键字: | 车辆途程问题;时间窗;多车种;团队越野竞赛问题;离散型粒子群演算法;Vehicle Routing Problem (VRP);time window constraint;Heterogeneous fleet Vehicle Routing Problem (HFVRP);Team Orienteering Problem (TOP);Discrete Particle Swarm Optimization (DPSO) |
公开日期: | 2013 |
摘要: | 大尺寸电视在进行配送服务的排程规划时,受限于顾客的时间、可用于运送安装的车型、车辆容量与行走路径、技术人员与其工作时间等限制,是一种复杂型的车辆途程问题(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. |
URI: | http://140.113.39.130/cdrfb3/record/nctu/#GT070153320 http://hdl.handle.net/11536/75052 |
显示于类别: | Thesis |