以先集群再定路線法求解多桶格車輛途程問題

A Cluster-First Route-Second Heuristic for the Multi-Compartments Vehicle Routing Problem

本文在探討如何以先集群再定路線啟發式解法求解多桶格車輛途程問題。除常見的容量限制與時窗限制外，多桶格車輛途程問題還具有桶格限制、相容限制與指定限制，是個具多重限制困難的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.