Date of Award

6-13-2013

Document Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Department of Electrical and Computer Engineering

First Advisor

Gilbert L. Peterson, PhD.

Abstract

This work introduces a new routing problem called the Dynamic Multi-Objective Multi-vehicle Covering Tour Problem (DMOMCTP). The DMOMCTPs is a combinatorial optimization problem that represents the problem of routing multiple vehicles to survey an area in which unpredictable target nodes may appear during execution. The formulation includes multiple objectives that include minimizing the cost of the combined tour cost, minimizing the longest tour cost, minimizing the distance to nodes to be covered and maximizing the distance to hazardous nodes. This study adapts several existing algorithms to the problem with several operator and solution encoding variations. The efficacy of this set of solvers is measured against six problem instances created from existing Traveling Salesman Problem instances which represent several real countries. The results indicate that repair operators, variable length solution encodings and variable-length operators obtain a better approximation of the true Pareto front.

AFIT Designator

AFIT-ENG-13-J-09

DTIC Accession Number

ADA587192

Download

Share

COinS