A proposed algorithm for finding the minimum cost of traveling in the Philippines

Date of Publication

2016

Document Type

Bachelor's Thesis

Degree Name

Bachelor of Science in Mathematics with specialization in Business Applications

Subject Categories

Mathematics

College

College of Science

Department/Unit

Mathematics and Statistics

Thesis Adviser

Isagani B. Jos

Abstract/Summary

We propose an algorithm combining the farthest insertion algorithm and Dijkstra's algorithm. This algorithm is an application of the Traveling Salesman Problem in a graph. The vertices of the graphs are the regions of the Philippines. In each vertex, there are sub-vertices representing the various cities/provinces of that particular region. We call such graph as the regional graph of the Philippines. The main objective of the study is to generate a tour visiting all or a selected number of regions in the Philippines exactly once, with the tour having the least cost or its approximation. A computer program applying the proposed algorithm to the regional graph of the Philippines was developed. This program written in Microsoft Visual Basic 2010 (VB.net) is called Phil Trip. All eighteen regions (vertices) and cities/province containing the airports (sub-vertices) are in the database of Phil Trip.

Abstract Format

html

Language

English

Format

Electronic

Accession Number

CDTU021086

Shelf Location

Archives, The Learning Commons, 12F, Henry Sy Sr. Hall

Physical Description

1 computer disc ; 4 3/4 in.

Keywords

Algorithms; Traveling salesman problem; Hamiltonian graph theory; Travel; Tourism--Philippines

Embargo Period

5-11-2021

This document is currently not available here.

Share

COinS