自從台灣加入WTO與制定石油管理法之後，油品市場競爭日益激烈且複雜，而在台灣土地價格寸土寸金以及難以擴增儲油槽的限制下，儲油槽的利用率儼然成為管理決策上的重要議題。儲油槽不僅可以供石油業者儲放各式油品，並可出租給其他無法建造儲油槽的油品供應商，賺取可觀的租賃費用且掌握競爭對手的通路命脈。因此，有效的儲油槽維護排程不僅增加系統操作可靠性，更可以降低操作成本，增加企業利潤與競爭力。維修排程為一典型NP-Hard問題，而啟發式演算法已經成功應用在解決各種NP-Hard問題上，包含旅行銷售員問題(Traveling Salesman Problem, TSP)、滿足限制問題(Constraint Satisfaction Problem)…等，其中螞蟻族群最佳化演算法(Ant Colony Optimization, ACO)則是近年來提出的新方法之一，其精神在於模擬螞蟻族群間藉由費洛蒙(Pheromone)訊息相互溝通共同合作以尋求最短路徑，藉以快速搬運食物的動物行為。本研究以螞蟻族群最佳化演算法解決石化工業儲油槽的維修排程問題，尋找排程之最佳解以降低維修成本進而提高維修效率，並與基因演算法作一效能與效率比較。此外，在一般解排程問題模式中，其最終結果往往只是把最佳排程解求出，並未進一步深入探索其所內含的知識。因此，本計畫擬結合螞蟻族群知識發現法將特定的排程解形成一個解集合，在此排程解集合中以資料探勘方法挖掘其所隱含的共通樣式(Pattern)，建立維修排程的分類法則，並透過領域決策專家的實務經驗來驗證與精鍊維修排程知識法則的效果。這些開採出來的知識法則亦可進一步提供石油業者構建立一套智慧型維修排程決策支援系統，輔助決策者在排程決策的制定與修正其決策知識。

　The oil market in Taiwan is becoming very competitive today than before, which is due to her recent entry into WTO and liberalized Petroleum Management Law, and the utilization ratio of oil tanks has already become the important topic in administrative decision. An optimized oil tank maintenance schedule not only increases system-operating reliability, but also reduces operation cost, and increases enterprise's profit and competitiveness. Maintenance problem is a classical NP-Hard problem, and heuristic algorithms has already succeeded in applying to solve various kinds of NP-Hard problem, which including the Traveling Salesman's Problem, limited resources allocation problem, and so on. Recently, Ant Colony Optimization (ACO) becomes another promising methodology in solving NP-Hard problem, which mimics the ethology behavior of collecting food quickly by the cooperative blind ants in different colonies seeking to the shortest path. Therefore, this research adopts the ACO approach to solve the maintenance scheduling problem of oil tanks, and compares the efficiency and effectiveness with Genetic Algorithm. In addition to finding out the best solution, we also investigate the knowledge behind the solutions further, and help businesses to archive the goal of Knowledge Management (KM). Therefore, we collect the solutions passing the threshold values into one set, and use ACO-based model of knowledge discovery in databases to uncover the interesting hidden patterns. Some classification rules are built up, and the domain expert will examine and refine these rules through his plentiful practical experience. The knowledge rules discovered can be further applied to the development of an intelligent decision support system for helping decision makers refine their decision knowledge in oil-tank maintenance scheduling.

[1] Beckers, R., Deneubourg, J. L., & Goss, S. (1992). Trails and u-turns in the selection of the shortest path by the ant lasius niger. Journal of Theoretical Biology, 159, 397-415.
[2] Bullnheimer, B., Hartl, R.F., & Strauss, C. (1997). Applying the ant system to the vehicle routing problem. Presented at the 2nd Metaheuristic International Conference, Sophia-Antipolis, France.
[3] Burke, E. K., & Smith, A. J. (2000). Hybrid evolutionary techniques for the maintenance scheduling problem. IEEE Transactions on Power Systems, 15, 122-128.
[4] Clark, P., & Niblett, T. (1989). The CN2 induction algorithm. Machine Learning, 3, 261-283.
[5] Colorni, A., Dorigo, M., & Maniezzo, V. (1991). An autocatalytic process. Technical Report, 91-016.
[6] Colorni, A., Dorigo, M., & Maniezzo, V. (1992). Distributed optimization by ant colonies. In Proceedings of the First Conference on Artificial Life, 134-142, MIP Press, Cambridge, MA.
[7] Colorni, A., Dorigo, M., & Maniezzo, V. (1996). Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems. Man and Cybernetics, Part B, 26(1), 29-41.
[8] Colorni, A., Dorigo, M., Maniezzo, V., & Trubian, M. (1994). Ant system for job-shop scheduling. Belgian Journal of Operations Research, Statistics and Computer Science (JORBEL), 34(1), 39-53.
[9] Di Caro, G. & Dorigo, M. (1997). AntNet: a mobile agents approach to adaptive routing. Technical Report 97-12, IRIDIA, Universit´e Libre de Bruxelles.
[10] Dopazo, J. F., & Merrill, H. M. (1975). Optimal generator maintenance scheduling using integer programming. IEEE Transactions on Power Apparatus and Systems, 94(5), 1537-1545.
[11] Dorigo, M. (1992). Optimization, learning and natural algorithms, Ph.D. Thesis, Dip. Elettronicae Informazione, Politecnico do Milano, Italy.
[12] Dorigo, M., Bonabeau, E., & Theraulaz, G. (2000). Ant algorithms and stigmergy. Future Generation Computer Systems, 16, 851-871.
[13] Dorigo, M., & Di Caro, G. (1999). The ant colony optimization meta-heuristic. In Corne, D., Dorigo, M., & Glover, F. (Eds.). New Ideas in Optimization, McGraw-Hill, 11-32.
[14] Dorigo M., & Gambardella, L. M. (1996). A study of some properties of Ant-Q. Proceedings of PPSN IV-Fourth International Conference on Parallel Problem Solving From Nature, 22-27, Berlin, Germany.
[15] Dorigo, M., & Gambardella, L. M. (1997). Ant colonies for the traveling salesman problem. BioSystems, 43, 73-81.
[16] Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53-66.
[17] Dorigo, M., Gambardella, L. M., & Di Caro, G. (1999). Ant algorithms for discrete optimization. Artificial Life, 5(2), 137-172.
[18] Fayyad, U. M., Shapiro, G. P., & Smyth, P. (1996). From data mining to knowledge discovery: an overview. Advances in Knowledge Discovery and Data Mining, MA AAAI/ MIT Press, 1-36.
[19] Gambardella, L. M., Taillard, E., & Agazzi, G. (1999). Macs-vrptw: A multiple ant colonysystem for vehicle routing problems with time windows. In Corne, D., Dorigo, M., & Glover, F. (Eds.). New Methods in Optimisation. McGraw-Hill.
[20] Gambardella, L. M., Taillard, È.D., & Dorigo, M. (1997). Ant colonies for the QAP. Technical Report IDSIA-4-97, IDSIA, Lugano, Switzerland.
[21] Gruhl, J. (1973). Electric generation production scheduling using a quasioptimal sequential technique. MIT Energy Lab, Research Note MITEL 73-003.
[22] Han, J., Kamber, M. (2000). Data mining：Concepts and techniques. S. Francisco：Morgan Kaufmann Publishers.
[23] Hentenryck, P. V. (2002). Constraint and integer programming in OPL. INFORMS Journal on Computing. 14(4), 345-373.
[24] Huang, S. J. (2001). Enhancement of hydroelectric generation scheduling using ant colony system based optimization approaches. IEEE Transactions on Energy Conversion, 16(3), 296-301.
[25] Ibrahim, E. A., Salih, D., & Mohammed, A. (2000). A tabu search algorithm for maintenance scheduling of generating units. Electric Power Systems Research, 54, 91–99.
[26] Kim, H., & Nara, K. (1995). A method for maintenance scheduling using GA combined with SA. Transactions IEE Japan, 115-B(11).
[27] Kim, H., Hayashi, Y., & Nara, K. (1997). An algorithm for thermal unit maintenance scheduling through combined use of GA, SA and TS. IEEE Transactions on Power Systems, 12(1), 329-335.
[28] Kohonen, T. (1997). Self-organizing maps. (2nd ed.). Berlin Heidelberg, New York：Springer-Verlag.
[29] Kooncea, D. A., & Tsai, S. C. (2000). Using data mining to find patterns in genetic algorithm solutions to a job shop schedule. Computers & Industrial Engineering, 38, 361-374.
[30] Li, S. T., Shue, L. Y., & Lin, P. C. (2002). A genetic-based heuristic approach toward maintenance scheduling of oil tanks. Sun Yat-Sen Management Review, 10, 133-157.
[31] Liu, B., Abbas, H. A., & McKay, B. (2003). Classification rule discovery with ant colony optimization. Intelligent Agent Technology, 2003. IAT 2003. IEEE/WIC International Conference on, 13(16), 83-88.
[32] Maniezzo, V., & Colorni, A. (1999). The ant system applied to the quadratic assignment problem. IEEE Transactions on Knowledge and Data Engineering, 11(5), 769-778.
[33] Merkle, D., Middendorf, M., & Schmeck, H. (2002). Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation, 6(4), 333-346.
[34] Parpinelli, R. S., Lopes, H. S., & Freitas, A. A. (2002). Data mining with an ant colony optimization algorithm. IEEE Transactions on Evolutionary Computation, 6(4), 321-332.
[35] Rejowski, R., & Pinto, J. M. (2003). Scheduling of a multiproduct pipeline system. Computers and Chemical Engineering, 27(8-9), 1229-1246.
[36] Rousseeuw, P. J. (1987). Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics, 20, 53-65.
[37] Satoh, T., & Nara, K. (1991). Maintenance scheduling by using the simulated annealing method. IEEE Transactions on Power Systems, 6(5), 850-857.
[38] Schoofs, L., & Naudts, B. (2000). Ant colonies are good at solving constraint satisfaction problems. Proceedings of the 2000 Congress on Evolutionary Computation, 2, 1190-1195.
[39] Shelokar, P. S., Jayaraman, V. K., & Kulkarni, B.D. (2004). An ant colony classifier system: application to some process engineering problems. Computers and Chemical Engineering, 28(9), 1577-1584.
[40] Sim, K. M., & Sun, W. H. (2003). Ant colony optimization for routing and load-balancing: survey and new directions. IEEE Transactions on Man and Cybernetics Systems, Part A, 33(5), 560-572.
[41] Solnon, C. (2002). Ants can solve constraint satisfaction problems. IEEE Transactions on Evolutionary Computation, 6(4), 347-357.
[42] Stützle, T., & Dorigo, M. (1999). ACO algorithms for the quadratic assignment problem. In Corne, D., Dorigo, M., & Glover, F. (Eds.). New Ideas in Optimization, McGraw-Hill.
[43] Stützle, T., & Hoos, H. (1997). The MAX-MIN ant system and local search for the traveling salesman problem. In IEEE Conference on Evolution Compution (ICEC'97), 309-314.
[44] Taillard, E.D., & Gambardella, L. M. (1997). Adaptive memories for the quadratic assignment problem. Technical Report IDSIA-87-97, IDSIA, Lugano, Switzerland.
[45] Yamayee, Z.A. (1982). Maintenance scheduling: description, literature survey and interface with overall operations scheduling. IEEE Transactions on Power Apparatus and Systems, 101(8), 2770–2779.
[46] Yamayee, Z. A., Sidenblad, K., & Yoshimura, M. (1983). A computationally efficient optimal maintenance scheduling method. IEEE Transactions on Power Apparatus and Systems, 102(2), 330-338.
[47] Ying, K. C., & Liao, C. (2004). An ant colony system for permutation flow-shop sequencing. Computers and Operations Research, 31(5), 791-801.
[48] Zurn, H. H., & Quintana, V. H. (1975). Generator maintenance scheduling via successive approximations dynamic programming. IEEE Transactions on Power Apparatus and Systems, 94(2), 665-671.