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

• Main Authors: Guillermo, Dominador R., Sabino, Susan
• Format: text
• Language: English
• Published: Animo Repository 1989
• Subjects: Algorithms; Programming (Mathematics); Heuristic programming; Simulation methods; Mathematical optimization
• Online Access: https://animorepository.dlsu.edu.ph/etd_bachelors/16343
• Institution: De La Salle University

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.