The Chromatic Traveling-Salesmen Problem and Its Application to Planning and Structuring Geographic Space

摘要

The classical traveling-salesman problem involves the establishment of a tour around a set of points in a plane such that each point is intersected only once and the circuit is of minimal total length. When the length of a salesman's tour cannot exceed a specified constant, the problem becomes that of finding the fewest number of salesmen such that every city is visited by a salesman and the length of each salesman's tour does not exceed a specified constant. This is the chromatic traveling-salesmen problem. An algorithm for this problem is developed and is used to create periodic markets in parts of Sierra Leone. Fifteen rural areas were examined from Sierra Leone, and weekly market places were identified in each area. Salesmen were to be assigned to an area so that each market place was visited and each tour (or periodic ring) did not exceed forty hours. The chromatic traveling-salesmen algorithm was used to minimize the number of periodic rings needed for each area and provide the specific tour for each ring.