Document Type

Closed Project

Publication Date

Fall 2013

Instructor

Timothy Anderson

Course Title

Operations Research in Engineering and Technology Management

Course Number

ETM 540

Abstract

The Traveling Salesman Problem (TSP) is combinatorial optimization problem that has real-world synonyms for many organizations and problem types [1]. In this paper we discuss various implementations of the Vehicle Routing Problem (VRP), an extension of the traditional traveling salesman problem and explore a best-fit solution as well as a heuristically derived “good” solution. The best-fit solution utilizes a branch and bound technique but requires an exponential amount of computational resources to complete when applied to problems of marginal size. Some heuristic methodologies are elucidated to compare and contrast their benefits and drawbacks and an open source solution for capacitated vehicle routing that utilizes a tabu search heuristic is chosen for a pilot data. Next we compare the results of small batch runs between our best-fit and “good” solutions, exploring projections based on our real-world output. We conclude with our routing solution pilot data and recommendations for utilization by Nokia Siemens Networks as part of their ongoing equipment upgrade and deployment tool set.

Description

This project is only available to students, staff, and faculty of Portland State University

Persistent Identifier

http://archives.pdx.edu/ds/psu/21902

Share

COinS