|
Description:
|
The purpose of this research is to develop an algorithm to find a near optimal solution of the M -traveling salesman (MTSP ) or the vehicle routing problem (VRP ) without capacity and demand constraints . The main objective of this modified MTSP problem is to find M tours subject to a balancing criteria and with minimum total distance . The selected balancing criteria is to minimize the longest tour (MIN -MAX ) . Two heuristic procedures have been developed , tested , and compared . In the first heuristic , a modification of Eastman's (1958 ) algorithm is used to continue searching for a better balancing solution . For the second heuristic , the idea of the well known 3 -OPT procedure is modified to satisfy the balancing criteria .
Both algorithms have been coded into BASIC programs . The programs were tested on a TI microcomputer at three levels : 15 nodes and 3 vehicles , 35 nodes and 4 vehicles , and 50 nodes and 5 vehicles , respectively . The main performance criteria used in this research were the longest distance tour , total distance , and total computational time . A minor performance criteria was the utilization of each vehicle .
The most important result of this research was the discovery of an algorithm which provides a good feasible solution for the VRP and the MTSP with sequential objectives . An area of application for this research is the design and control of material handling systems as proposed by Blair and Vasquez (1984 ) . Experimentation with both algorithms was conducted in the same way as described in Blair , Charnsethikul , and Vasquez (I985 ) using the same data set . |