## Travelling Salesman Problem in QBasic

## Travelling Salesman Problem in QBasic

(OP)

Has anyone written a code in QBasic to solve the Travelling Salesman Problem?

I can solve it in Excel Solver but would be interested in the code.

Pervez

I can solve it in Excel Solver but would be interested in the code.

Pervez

## RE: Travelling Salesman Problem in QBasic

Here is an example:

## CODE

Output:

## RE: Travelling Salesman Problem in QBasic

I think I did not make myself clear.

I am trying to find the shortest route from any city (example 4) back to 4, while going through ALL cities exactly once.

Travelling Salesman Problem – Qbasic

5 'Travelling Salesman Problem

10 'number of cities

20 N = 10

30 Dim cities(N, N)

40 Dim visit(N + 1)

50 Dim visit_distance(N)

60 'read data into matrix

70 Print "Matrix of distances between the cities:"

80 Print

90 For i = 1 To N

100 For j = 1 To N

110 Read cities(i, j)

120 Print cities(i, j);

130 Next j

140 Print

150 Next i

160 Print

170 'read data into vector

180 Print "Visiting cities in this order:"

190 Print

200 For i = 1 To N + 1

210 Read visit(i)

220 Print visit(i);

230 Next i

240 Print

250 Print

260 START = TIMER

270 'compute partial distances

280 Print "Distances between cities travelled:"

290 Print

300 For i = 1 To N

310 visit_distance(i) = cities(visit(i), visit(i + 1))

320 Print visit_distance(i);

330 Next i

340 Print

350 Print

360 'compute sum of distances

370 total_distance = 0

380 For i = 1 To N

390 total_distance = total_distance + visit_distance(i)

400 Next i

410 Print "Total distance travelled ="; total_distance

420 ELAPSED = TIMER – START

430 PRINT “elapsed time is” ; ELAPSED, “seconds”

440 '---------------------------------------------------------------------

450 'Matrix contains distances between the cities

460 Distance_Matrix:

470 Data 0,34,36,37,31,33,35,21,18,30

480 Data 34,0,29,23,22,25,24,31,20,27

490 Data 36,29,0,17,12,18,17,24,22,13

500 Data 37,23,17,0,32,30,29,16,33,29

510 Data 31,22,12,32,0,26,24,18,17,18

520 Data 33,25,18,30,26,0,19,20,18,22

530 Data 35,24,17,29,24,19,0,19,25,30

540 Data 21,31,24,16,18,20,19,0,21,24

550 Data 18,20,22,33,17,18,25,22,0,19

560 Data 30,27,13,29,18,22,30,24,19,0

700 'Vector contains the order in which to visit the cities

710 Visit_vector:

720 Data 4,3,5,1,6,7,2,4, 8,9,10

Your code, takes the visit vector, line 720, as input data.

I need to find the minimum route and then output the visit vector as the shortest route from city 4 back to 4, after visiting 1, 2, 3, 5, 6, 7,8,9,10,4 in any order which gives the shortest path.

Please see attached xls for 10 cities.

Seven cities will require enumerating 7! routes; 10 cities will require analysing 10! routes to find the shortest.

Thanx & Regards

Pervez

PS: I think I will take my star back :)

## RE: Travelling Salesman Problem in QBasic

In the excel sheet for 7 cities you posted the visit vector was hard coded. I didn't found any computation how you computed it. So I hard coded it too.

To compute it like you want, one first need to solve how to generate all 7! permutations. I don't know it yet. Maybe we will find an algorithm.

## RE: Travelling Salesman Problem in QBasic

I found an algorithm how to compute all permutations: see

QuickPerm algorithmhere https://www.quickperm.orgThen I could use it for programming TSP.

tsp_solver.bas## CODE

However you cannot see all 5040 permutation on the QB64 screen, so the program creates in the same directory the log file

tsp_solver.txtwhich you can open with notepad and you can see all computation stepstsp_solver.txt## CODE

## RE: Travelling Salesman Problem in QBasic

Just thrilled to receive your response.

Will try it out later.

If it works I will give you another star.

If it does not I will take back the first star :)

Thanx

Pervez

## RE: Travelling Salesman Problem in QBasic

I tested it on several cases, the largest case was with ten cities and it always calculated a result

## RE: Travelling Salesman Problem in QBasic

When you have time can you please look at the ERROR I get when running your code.

Also, I do not understand Lines 2320 - 2360.

The Distance Matrix lines 2370 - 2384 I recognise as the distance between cities 1 to 7.

But what do lines 2320 - 2360 represent?

Regards

Pervez

PS: No urgency on this issue.

Please respond when convenient.

## RE: Travelling Salesman Problem in QBasic

Attached is the compilelog which I forgot to attach before.

Pervez

## RE: Travelling Salesman Problem in QBasic

In the compile log you attached are only these lines

## CODE

Maybe you changed something in the program improperly.

The code I posted, I tested before in QB64 on two PCs: my home PC with Linux and my work PC with Windows 10. It runs successfully on both.

First try to run the program as I posted it, without changing anything.

I also noticed from the screenshot you posted that you have a different version of QB64 than me. You have a 32 bit version (QB64 x32) and I have a 64 bit version (QB64 x64).

If I can't reproduce your error, then unfortunately I can't help you

I don't know what line numbers you mean.

The program I posted has only

236 lines- see the screenshot:## RE: Travelling Salesman Problem in QBasic

Mea Culpa!

I took your advice and your untouched (untouched by human hands?) version worked!

I must have screwed up during line numbering.

Thanx for all your help.

Pervez

## RE: Travelling Salesman Problem in QBasic

I ran your code for 10 cities and it worked fine.

But, I have a couple of questions and would be grateful if you could answer at your convenience.

1. I do not understand the first set of Distance Matrix - DATA 0,34,36 and the following 2 lines.

2. My 2nd question is where is the right place to put a TIMER?

I start the timer after the initial 7 DIM statements and end it just before Functions and Subroutines

My aim is to calculate the computing time only and not include any printing or output time.

Your help appreciated.

Pervez

'Data

'---------------------------------------------------------------------

'Matrix contains distances between the cities

'Distance_Matrix:

'Data 0,34,36

'Data 35,20,29

'Data 40,29,10

Distance_Matrix:

Data 0,34,36,37,31,33,35,21,18,30

Data 34,0,29,23,22,25,24,31,20,27

Data 36,29,0,17,12,18,17,24,22,13

Data 37,23,17,0,32,30,29,16,33,29

Data 31,22,12,32,0,26,24,18,17,18

Data 33,25,18,30,26,0,19,20,18,22

Data 35,24,17,29,24,19,0,19,25,30

Data 21,31,24,16,18,20,19,0,21,24

Data 18,20,22,33,17,18,25,22,0,19

Data 30,27,13,29,18,22,30,24,19,0

ELAPSED = TIMER – START

PRINT “elapsed time is”; ELAPSED, “secs”

'---------------------------------------------------------------------

'Functions and Subroutines

'---------------------------------------------------------------------

## RE: Travelling Salesman Problem in QBasic

To your questions:

As you could see these lines begin with

'and are set on comments. It was only a small example of three cities on which I tested the program during development. You can delete these lines.I would START the timer as you have done and END it after the main program is over i.e. after these lines

## CODE

Then make your own modification of the program, where you remove:

commands for opening and closing output file

all commands needed for printing the intermediate results on the screen and in the file, i.e. statements which begin with output_line$ and Print

## RE: Travelling Salesman Problem in QBasic

One last question:

How do I insert spaces between the brackets in the output?

( 2, .....7, 2 ) and ( 23, .... 19, 24 )

At my age I can get confused if the output is like

(2, ....7, 2) and (23, .....19,24)

I modified a few lines but got no change.

Regards

Pervez

## RE: Travelling Salesman Problem in QBasic