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

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

10.6285/MIC.201808_7(S1).0013

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

多桶格車輛途程問題 ； 桶格限制 ； 相容限制 ； 基因演算法 ； 先分群再定路線法 ； Multi-compartments vehicle routing problem ； Compartment constraint ； Compatibility constraint ； Genetic algorithm ； Cluster-first route-second

管理資訊計算

7卷特刊1（2018 / 08 / 01）

126 - 136

繁體中文

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

1. 林高正、曾文宏、陳建甫、蔡巧卿(2017)。以先集群再定路線法求解多桶格車輛途程問題。管理資訊計算，6(S1)，149-160。
   連結：
2. Ahuja, R.K.,Magnanti, T.L.,Orlin, J.B.(1993).Network Flows: Theory, Algorithms, and Applications.Englewood Cliffs, New Jersey:Prentice-Hall.
3. 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.
4. 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.
5. Braysy, O.,Gendreau, M.(2005).Vehicle routing problem with time windows, Part II: Metaheuristics.Transportation Science,39(1),119-139.
6. Christofides, N.(1976).,Pittsburgh:Carnegie-Mellon University.
7. Dantzig, G.B.,Ramser, J.H.(1959).The truck dispatching problem.Management Science,6(1),80.
8. Dell'Amico, M.(ed.),Maffioli, F.(ed.),Martello, S.(ed.)(1997).Annotated Bibliographies in Combinatorial Optimization.Chichester, UK:Wiley.
9. Desrochers, M.,Lenstra, J.K.,Savelsberg, M.(1990).A classification scheme for vehicle routing and scheduling problems.Journal of the Operational Research Society,46(3),322-332.
10. Gen, M.,Cheng, R.(1997).Genetic Algorithms and Engineering Design.New York:John Wiley & Sons.
11. Goldberg, D.E.(1989).Genetic Algorithms in Search, Optimization, and Machine Learning.Reading, Massachusetts:Addison-Wesley.
12. Golden, B.(ed.),Raghavan, S.(ed.),Wasil, E.(ed.)(2008).The Vehicle Routing Problem: Latest Advances and New Challenges.New York:Springer.
13. Golden, B.L.(ed.),Assad, A.A.(ed.)(1988).Vehicle Routing: Methods and Studies.North-Holland:Elsevier Science Publisher B.V..
14. Holland, J.H.(1975).Adaptation in Natural and Artificial Systems.University of Michigan.
15. Horowitz, E.,Sahni, S.,Rajasrkaran, S.(1997).Computer Algorithms/C++.New York:Computer Science Press.
16. Laporte, G.(1992).The vehicle routing problem: an overview of exact and approximate algorithms.European Journal of Operational Research,59(3),345-358.
17. Laporte, G.,Nobert, Y.(1987).Exact algorithms for the vehicle routing problem.Surveys in Combinatorial Optimization,Amsterdam:
18. Laporte, G.,Osman, I.H.(1995).Routing problems: a bibliography.Annals of Operations Research,61,227-262.
19. Lawler, E.L.(ed.),Lenstra, J.K.(ed.),Rinnooy Kan, A.H.G.(ed.),Shmoys, D.(ed.)(1985).The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization.Chichester:John Wiley & Sons.
20. Myers, R.H.,Montgomery, D.C.(2002).Response Surface Methodology.New York:John Wiley & Sons.
21. Prim, R.C.(1957).Shortest connection networks and some generalizations.Bell System Technical Journal,36,1389-1401.
22. Reinelt, G.(1994).The Traveling Salesman: Computational Solutions for TSP Applications.Berlin:Springer-Verlag.
23. Toth, P.(ed.),Vigo, D.(ed.)(2002).The Vehicle Routing Problem.Philadelphia, PA.:Society for Industrial and Applied Mathematics.
24. Toth, P.(ed.),Vigo, D.(ed.)(2002).The Vehicle Routing Problem.Philadelphia, PA.:Society for Industrial and Applied Mathematics.
25. Toth, P.(ed.),Vigo, D.(ed.)(2014).Vehicle Routing: Problems, Methods, and Applications.Philadelphia, PA.:Society for Industrial and Applied Mathematics.
26. Toth, P.,Vigo, D.(2002).Models, relaxations and exact approaches for the capacitated vehicle routing problem.Discrete Applied Mathematics,123,487-512.
27. 陳建甫(2006)。碩士論文(碩士論文)。台南縣永康市，南臺科技大學工業管理研究所。

1. 蔡巧卿,陳建甫,邱錦雪,林高正(2019)。散裝飼料車電腦化派車系統之建置。管理資訊計算，8(特刊1)，75-89。