以混合基因演算法求解多桶格車輛途程問題

A Hybrid Genetic Algorithm for the Multi-Compartments Vehicle Routing Problem

本研究提出一個求解多桶格車輛途程問題的混合基因演算法。除常見的容量限制與時窗限制外，這問題還具有桶格限制、相容限制與指定限制，是個具多重限制的困難NP-hard問題，實務上通常採用啟發式解法求解。而對困難NP-hard問題而言，傳統啟發式解通常存在著相當的改進空間，因此有必要利用有效的搜尋機制加以改良。本文就在探討如何以基因搜尋機制改良林高正、曾文宏、陳建甫、蔡巧卿（2017）所提出的先分群再定路線啟發式解，並進行數值實驗以比較相關解法。 The multi-compartments vehicle routing problem is not only an NP-hard problem in strong sense, but also has multiple constraints. In addition to the classical capacity and time-window constraints, this problem also has compartment, compatibility, and assignment constraints. For such a problem, a solution found by traditional heuristics usually can be improved by using a searching scheme. In this paper, a hybrid genetic algorithm for the multi-compartments vehicle routing problem, that uses the cluster-first route-second heuristic proposed by Lin, Tseng, Chen, and Tsai (2017) to generate the initial population and to design the related genetic operators, is proposed.

The multi-compartments vehicle routing problem is not only an NP-hard problem in strong sense, but also has multiple constraints. In addition to the classical capacity and time-window constraints, this problem also has compartment, compatibility, and assignment constraints. For such a problem, a solution found by traditional heuristics usually can be improved by using a searching scheme. In this paper, a hybrid genetic algorithm for the multi-compartments vehicle routing problem, that uses the cluster-first route-second heuristic proposed by Lin, Tseng, Chen, and Tsai (2017) to generate the initial population and to design the related genetic operators, is proposed.