Optimal routing of vehicles with balancing workloads

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.