篇名 | 以先集群再定路線法求解多桶格車輛途程問題 |
---|---|
卷期 | 6特刊1 |
並列篇名 | A Cluster-First Route-Second Heuristic for the Multi-Compartments Vehicle Routing Problem |
作者 | 林高正 、 曾文宏 、 陳建甫 、 蔡巧卿 |
頁次 | 149-160 |
關鍵字 | 多桶格車輛途程問題 、 桶格限制 、 相容限制 、 啟發式解法 、 先集群再定路 線法 、 Multi-compartments vehicle routing problem 、 Compartment constraint 、 Compatibility constraint 、 Heuristic algorithm 、 Cluster-first route-second |
出刊日期 | 201708 |
DOI | 10.6285/MIC.6(S1).13 |
本文在探討如何以先集群再定路線啟發式解法求解多桶格車輛途程問題。除常 見的容量限制與時窗限制外,多桶格車輛途程問題還具有桶格限制、相容限制與指 定限制,是個具多重限制困難的 NP-hard 問題。對具多重限制困難的 NP-hard 問題 而言,傳統啟發式解法不論是在實務應用、分枝與界限法之界限函數設計、或基因 演算法之起始族群建立和遺傳算子設計上均扮演著重要的角色。
In this paper, a cluster-first route-second heuristic is proposed to solve the multi-compartments vehicle routing problem. In addition to the classical capacity and time-window constraints, this problem also has compartment, compatibility, and assignment constraints. It is not only an NP-hard problem in strong sense, but also has multiple constraints. For such a problem, heuristic algorithms can be used in solving practical problems, deriving bounding functions for a branch and bound algorithm, and generating the initial population and designing genetic operators for a genetic algorithm.