An application of an M-tour traveling salesman algorithm (savings-based method) to Chic Centre Corporation

Date of Publication

1989

Document Type

Bachelor's Thesis

Degree Name

Bachelor of Science in Applied Mathematics

College

College of Science

Department/Unit

Mathematics and Statistics

Abstract/Summary

This thesis is an application of a heuristic algorithm for solving m-tour traveling salesman problems. Developed by G. Clarke and J.W. Wright, the algorithm is more popularly known as the Savings-Based Method. The paper applies the Savings-Based Method on the delivery schedules of Chic Centre Corporation, Cosmetics Division of the Consolidated Foods Corporation, Cosmetics Division of the Consolidated Foods Corporation (CFC). With the central depot in Pasig, this work attempts to determine the optimal number of salesmen to visit all supply points in the Chic Centre's existing delivery plan. The heuristic algorithm offers an alternative method of arriving at the optimal solution. (The classical solution is obtained via the Eastman's Algorithm). The Savings-Based Method works by computing for individual savings in linking two points in one route. Savings in linking two random points (in a descending manner) is considered until all possibilities of linking are exhausted. The link with the greatest savings is chosen from the list. In the end, when an optimal solution to the routing problem is reached, the refinement, process by Holmes and Parker (as discussed by T.B. Boffey in Graph Theory in Operations Research, 1982), is suggested.

Abstract Format

html

Language

English

Format

Print

Accession Number

TU07658

Shelf Location

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

Physical Description

55 leaves

Keywords

Algorithms; Programming (Mathematics); Heuristic programming; Simulation methods; Mathematical optimization

This document is currently not available here.

Share

COinS