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

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

並列關鍵字

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

參考文獻

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

Google Scholar

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.

Google Scholar

Bramel, J.,Simichi-Levi, D.(2002).Set-covering-based algorithms for the capacitated VRP.The Vehicle Routing Problem.(The Vehicle Routing Problem).:

Google Scholar

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.