Abstract: The complete computer program listed here illustrates an integer programming algorithm with an asymmetric 6-city traveling salesperson problem from the literature. A BASIC computer program and its output are included here.
The Problem, the Computer Program and Its Output
This paper is concerned with the traveling salesperson problem, asymmetric or symmetric. To illustrate the algorithm, the BASIC computer program listed below uses the 6-city problem in Little et al. [1]. Its distances are used in line 41 through line 99. The salesperson's home city is city 1, used in line 6221.
2 DEFINT I,J,K
3 DIM T(22,22)
7 DIM B(56),Y(56)
41 T(1,1)=99999!:T(1,2)=27:T(1,3)=43:T(1,4)=16:T(1,5)=30:T(1,6)=26
42 T(2,2)=99999!:T(2,3)=16:T(2,4)=1:T(2,5)=30:T(2,6)=25
43 T(3,3)=99999!:T(3,4)=35:T(3,5)=5:T(3,6)=0
44 T(4,4)=99999!:T(4,5)=18:T(4,6)=18
45 T(5,5)=99999!:T(5,6)=5
46 T(6,6)=99999!
91 T(6,1)=23:T(6,2)=5:T(6,3)=5:T(6,4)=9:T(6,5)=5
93 T(5,1)=12:T(5,2)=46:T(5,3)=27:T(5,4)=48
94 T(4,1)=21:T(4,2)=16:T(4,3)=25
95 T(3,1)=20:T(3,2)=13
99 T(2,1)=7
112 FOR JJJJ=-32000 TO 32000
114 RANDOMIZE JJJJ
116 M=-1D+17
121 B(1)=2:B(2)=3:B(3)=4:B(4)=5:B(5)=6
128 FOR I=1 TO 10
129 FOR K=1 TO 5
301 Y(K)=B(K)
302 NEXT K
383 AHOR=1+FIX(RND*5):BHOR=1+FIX(RND*5)
385 Y(AHOR)=B(BHOR)
387 Y(BHOR)=B(AHOR)
6221 P1NE1=T(1,Y(1))+T(Y(1),Y(2))+T(Y(2),Y(3))+T(Y(3),Y(4))+T(Y(4),Y(5))+T(Y(5),1)
6223 P1NEW=P1NE1
6450 P=-P1NEW
6451 IF P
6658 B(KEW)=Y(KEW)
6659 NEXT KEW
6661 M=P
6665 D1=Y(1):D2=Y(2):D3=Y(3):D4=Y(4):D5=Y(5)
6670 NEXT I
6890 IF M>-64 THEN 6895 ELSE 6999
6895 PRINT D1,D2,D3,D4,D5
6961 PRINT JJJJ,M
6999 NEXT JJJJ
This BASIC computer program was run with the IBM basica/D interpreter, and its output
(in a compressed form and to be interpreted in accordance with line 6895 and line 6961) for JJJJ=-32000 through JJJJ=-31939 is as follows:
4 3 5 6 2
-31999 -63
4 3 5 6 2
-31998 -63
4 3 5 6 2
-31967 -63
4 3 5 6 2
-31949 -63
4 3 5 6 2
-31939 -63
The output above shows that the shortest tour of 1-4-3-5-6-2-1 for 63 (miles) [1, p. 981] was produced 5 times. These computational results were obtained in 1 second with an Intel Pentium II 400 MHz. chip and the IBM basica/D interpreter.
One future research direction is to use the computer program listed above as a model for bigger problem instances and for problems of similar nature.
References
[1] John D. C. Little, Katta G. Murty, Dura W. Sweeney, and Caroline Karel, "An Algorithm for the Traveling Salesman Problem," Operations Research, Vol. 11, No. 6. (Nov.-Dec., 1963), pp. 972-989.
[2] Wayne L. Winston: "Operations: Applications and Algorithms," Fourth Edition, pp. 530-538, Brooks/Cole, a Division of Thomson Learning, Inc., Belmont, CA, 2004.
