A branch and bound algorithm for the travelling salesman and the transportation routing problems |
| |
Authors: | R Radharamanan LI Choi |
| |
Affiliation: | Department of Mechanical and Industrial Engineering University of Utah, Salt Lake City, Utah, USA |
| |
Abstract: | In this paper, a branch and bound model with penalty tour building is developed for solving travelling salesman and transportation routing problems. The algorithm for determining the optimal solution of the problem is of the general form which can solve symmetric and asymmetric single and multiple travelling salesman problems (STS and MTS), and the transportation routing problems with capacity restrictions for the vehicles of same or of different capacities. The behavior of the developed algorithm is tested with randomly generated data. As an application, the routes for gas distribution is planned and carried out in several interior towns of a state, with the objective of making an efficient distribution in order to minimize the total cost of delivery with an optimal solution. |
| |
Keywords: | Transportation routing problem travelling salesman problem branch and bound algorithm decision tree optimization vehicle routing and scheduling capacity restriction |
本文献已被 ScienceDirect 等数据库收录! |
|