Solving Multi-Objective Multi-Constrained Optimization Problems Using Hybrid Ants System and Tabu Search

• Main Authors: LAU, Hoong Chuin, LIM, Min Kwang, WAN, Wee Chong, WANG, Hui, WU, Xiaotao
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2003
• Subjects: Artificial Intelligence and Robotics; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/2230; https://ink.library.smu.edu.sg/context/sis_research/article/3230/viewcontent/MIC03_HASTS.pdf
• Institution: Singapore Management University

Many real-world optimization problems today are multi-objective multi-constraint generalizations of NP-hard problems. A classic case we study in this paper is the Inventory Routing Problem with Time Windows (IRPTW). IRPTW considers inventory costs across multiple instances of Vehicle Routing Problem with Time Windows (VRPTW). The latter is in turn extended with time-windows constraints from the Vehicle Routing Problem (VRP), which is extended with optimal fleet size objective from the single-objective Traveling Salesman Problem (TSP). While single-objective problems like TSP are solved effectively using meta-heuristics, it is not obvious how to cope with the increasing complexity systematically as the problem is compounded with additional objectives and constraints. In this paper, we study the effectiveness of the classical divide-and-conquer paradigm where sub-problems are divided along objective functions and constraints, and conquered via a hybridized meta-heuristic. The “Divide” technique involves breaking the problems into several sub-problems such that each sub-problem now contains only a single objective subject to a partial set of constraints. In addition, each sub-problem is related to another through one or more common constraints. The “Conquer” technique on the other hand, refers to a single generic scheme that is able to self-adapt through various Derived Models to solve different sub-problems. Each derived model represents a different degree of collaboration between two (or more) core meta-heuristics. The advantage of the derived models lies in the ability to exploit the strength and cover the weakness of the meta-heuristics under the scheme.