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

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

林高正(Kao-Cheng Lin) ； 曾文宏(Wen-Hung Tseng) ； 陳建甫(Chien-Fu Chen) ； 蔡巧卿(Chiao-Ching Tsai)

《管理資訊計算》 7卷特刊1 (2018/08) Pp. 126-136

https://doi.org/10.6285/MIC.201808_7(S1).0013

摘要

本研究提出一個求解多桶格車輛途程問題的混合基因演算法。除常見的容量限制與時窗限制外，這問題還具有桶格限制、相容限制與指定限制，是個具多重限制的困難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.

並列關鍵字

Multi-compartments vehicle routing problem ； Compartment constraint ； Compatibility constraint ； Genetic algorithm ； Cluster-first route-second

參考文獻

林高正、曾文宏、陳建甫、蔡巧卿(2017)。以先集群再定路線法求解多桶格車輛途程問題。管理資訊計算。6(S1)，149-160。

陳建甫(2006)。以基因搜尋法求解多桶格車輛途程問題(碩士論文)。南臺科技大學工業管理研究所。

Ahuja, R.K.,Magnanti, T.L.,Orlin, J.B.(1993).Network Flows: Theory, Algorithms, and Applications.Englewood Cliffs, New Jersey:Prentice-Hall.

Ball, M.O.(ed.),Magnanti, T.L.(ed.),Monma, C.L.(ed.),Nemhauser, G.L.(ed.)(1995).Handbooks in Operations Research and Management Science.Amsterdam:Elsevier Science.

Braysy, O.,Gendreau, M.(2005).Vehicle routing problem with time windows, Part I: Route construction and local search algorithms.Transportation Science.39(1),104-118.