Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

8-2003

Abstract

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.

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Optimization

Publication

MIC2003: 5th Metaheuristics International Conference, Kyoto, 25-28 August 2003, Proceedings

First Page

1

Last Page

9

Publisher

MIC

City or Country

Kyoto, Japan

Embargo Period

5-22-2014

Copyright Owner and License

Authors

Download

Share

COinS