Algorithm for the Solution of a Traveling Salesman Problem to Minimize the Average Time to Demand Satisfaction.

摘要

This paper presents a solution approach for solving a modified traveling salesman problem. In this problem, each city which the salesman must visit contains a quantity of demand (in units) which the salesman must satisfy. The objective of the salesman is to minimize the average time until satisfaction for each unit of demand. The solution approach presented is a branch-and-bound approach in which the total set of feasible tours are broken down into subsets. Lower bounds are the calculated for each subset and compared against a known upper bound to determine if this subset can be fathomed or if a improved upper bound has been found. The solution approach presented ensures optimality. A computer code was created and is presented which implements the solution approach developed.