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

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

10.6285/MIC.6(S1).13

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

多桶格車輛途程問題 ； 桶格限制 ； 相容限制 ； 啟發式解法 ； 先集群再定路線法 ； Multi-compartments vehicle routing problem ； Compartment constraint ； Compatibility constraint ； Heuristic algorithm ； Cluster-first route-second

管理資訊計算

6卷特刊1（2017 / 08 / 01）

149 - 160

繁體中文

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

1. Ahuja, R.K.,Magnanti, T.L.,Orlin, J.B.(1993).Network Flows: Theory, Algorithms, and Applications.Englewood Cliffs, New Jersey:Prentice-Hall.
2. Ball, M.O.(ed.),Magnanti, T.L.(ed.),Monma, C.L.(ed.),Nemhauser, G.L.(ed.)(1995).Handbooks in Operations Research and Management Science, Volume 8: Network Routing.Amsterdam:Elsevier Science.
3. Bramel, J.,Simichi-Levi, D.(2002).Set-covering-based algorithms for the capacitated VRP.The Vehicle Routing Problem,Philadelphia:
4. Braysy, O.,Gendreau, M.(2005).Vehicle routing problem with time windows, Part II: Metaheuristics.Transportation Science,39(1),119-139.
5. 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.
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.European Journal of Operational Research,46(3),322-332.
10. Garey, M.R.,Johnson, D.S.(1979).Computers and Intractability: A Guide to the Theory of NP-Completeness.San Francisco:W.H. Freeman.
11. Gen, M.,Cheng, R.(1997).Genetic Algorithms and Engineering Design.New York:John Wiley & Sons.
12. Gendreau, M.,Larporte, G.,Potvin, J.-Y.(2002).Metaheuristics for the capacitated VRP.The Vehicle Routing Problem,Philadelphia, PA:
13. Golden, B.(ed.),Assad, A.A.(ed.)(1988).Vehicle Routing: Methods and Studies.North-Holland:Elsevier Science Publisher B.V..
14. Golden, B.(ed.),Raghavan, S.(ed.),Wasil, E.(ed.)(2008).The Vehicle Routing Problem: Latest Advances and New Challenges.New York:Springer.
15. Han, J.,Kamber, M.(2001).Data Mining: Concepts and Techniques.San Francisco:Morgan Kaufmann Publishers.
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. Laporte, G.,Semet, F.(2002).Classical heuristics for the capacitated VRP.The Vehicle Routing Problem,Philadelphia, PA:
20. 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.
21. Martel, C.(2002).The expected complexity of Prim's minimum spanning tree algorithm.Information Processing Letters,81(4),197-201.
22. Naddef, D.,Rinaldi, G.(2002).Branch-and-cut algorithms for the capacitated VRP.The Vehicle Routing Problem,Philadelphia:
23. Prim, R.C.(1957).Shortest connection networks and some generalizations.Bell System Technical Journal,36,1389-1401.
24. Reinelt, G.(1994).The Traveling Salesman: Computational Solutions for TSP Applications.Berlin:Springer-Verlag.
25. Toth, P.(ed.),Vigo, D.(ed.)(2002).The Vehicle Routing Problem.Philadelphia, PA.:Society for Industrial and Applied Mathematics.
26. Toth, P.(ed.),Vigo, D.(ed.)(2014).Vehicle Routing: Problems, Methods, and Applications.Philadelphia, PA.:Society for Industrial and Applied Mathematics.
27. Toth, P.,Vigo, D.(2002).Models, relaxations and exact approaches for the capacitated vehicle routing problem.Discrete Applied Mathematics,123,487-512.

1. 蔡巧卿,陳建甫,邱錦雪,林高正(2019)。散裝飼料車電腦化派車系統之建置。管理資訊計算，8(特刊1)，75-89。
2. 蔡巧卿、曾文宏、陳建甫、林高正(2018)。以混合基因演算法求解多桶格車輛途程問題。管理資訊計算，7(S1)，126-136。