CS Project
Schedule
I've divided this project into several chunks:
- Do whatever needs to be done so that parsed data can be translated to whatever the program needs each time.
- Get and parse the data.
- Process it with Djikstra's algorithm in order to get distances from everywhere to everywhere.
- Figure out how to deal with things like multiple airports, the one direction rule, other small variations in the TSP.
- Code the actual TSP. (talk to Jim re solving one TSP and reducing vs solving one each time)
- Write the web frontend (and bit of backend so it automatically gets data every so often, etc.)
- Clean up everything. Write documentation and any additional tests.
- Write a discussion of the project.
Given how long it took me to write Djikstra's - and the code that generated test data - I think that each part (except the small details and the TSP itself) should take a week or so. I'll see how long it takes to write the TSP after talking to Jim about what he thinks about the Lin-Kernighan paper. The small details will either come up as things go along, or should be added at the end. As far as a precise schedule, I'd like to get it doing stuff as quickly as I can and then add everything else. I'd like to have it doing TSPs on test data by the end of September and have the rest of it done by the end of October. We will see how that bears out.
Thursday 11/11
Current code. Roads are now a subclass of Connectors.
Monday 11/1
Current code, now with print statements in a fair number of places, and a four-city test instance. I've fixed a few things and am currently running into issues with road directionality. In a nutshell: In the code as it was, I'd cut a road, then I'd look at the destination of the cut road to find the next road to add. This caused that destination to have two roads leaving it and no roads entering it, thus breaking the tour. I tried to solve this by, when cutting a road, attempting to get the next addRoad from the source of the cutRoad. That seems to work better, but it'll get into strange loops and tries to add, say, a road from A to B when a road from B to A is already in the tour. I'm starting to bounce off it, so I'm going to put the code here and look at it more tomorrow.
Friday 10/29
One new test feature: you can now run a "complete" test on a given set of cities, which tries to solve a TSP on every possible ordering of that set. It'll return True if the solving produces the same length tour every time; otherwise it'll return False and the first two tours that did not equal each other. Takes (n!)2
time with the existing solver, so don't run it on anything big - or anything medium-sized.
Thursday 10/28
Current code. It now successfully loads all the test TSPs - that is, 'solves' them from the optimal tour. It will sometimes run through a solving attempt at five cities without crashing, but returns the initial tour even if that tour is not optimal. It repeatably crashes with twelve cities, but I'm working with the set of five for now.
Friday 10/22
Uploading again. WikiAcademia isn't letting me delete the old files - although it would let me upload over them before - so I'm just putting a zip file along with them. There's a very brief readme in the file. I'll put current code up each day I work on it over the weekend as well.
7:30 update: it now runs successfully on the minimal case. I should probably add some sort of a print function so that it can print out stuff about the tour, but it any case...on to a nontrivial instance.
11:20 update: There's now a bit of a print function for tours. A few other things were tidied up. Haven't played much with a nontrivial tour, though.
Monday 10/18
Uploading current code. The TSP is written, but is in the process of being debugged and does not work as is. The code is a bit better organized, with most of the classes now in a utils file.
Also looked a bit more into parsing PDF files; it seems that
Poppler provides a pdftotext utility that provides...something. It's nowhere near as nice as the PDF, but some industrial strength regex might make it usable.
Tuesday 10/12
Uploading current code. The TSP itself is getting there but needs a few functions to be fully functional.
Friday 10/1
Current code again. It's now 100x faster than it was - going from 'glacial' to 'kinda slow'.
10 cities processed. 2.598000 seconds taken to run Djikstra's.
393265 function calls (201019 primitive calls) in 2.618 CPU seconds
10 cities processed. 0.122000 seconds taken to run Djikstra's.
14781 function calls (10220 primitive calls) in 0.341 CPU seconds
10 cities processed. 0.041000 seconds taken to run Djikstra's.
5581 function calls (4864 primitive calls) in 0.118 CPU seconds
and eventually,
10 cities processed. 0.039000 seconds taken to run Djikstra's.
5092 function calls (4401 primitive calls) in 0.060 CPU seconds
Now it takes 15 seconds to generate cities and run Djikstra's for n=100. Still not quite where I'd like it to be, speed-wise, but further optimization would probably be complicated and is best left until after the rest of it works.
Wednesday 9/29
Uploading current code again. Djikstra's now works; on to the TSP itself.
Tue Sep 28
Uploading current code again. There are now objects! all over. Djikstra's still doesn't work, but now it's for a completely different reason, and I spent hardly any time working on it this week. I don't have a proper pseudocode for the Lin-Kernighan bit. Now that I understand what we've been looking it, it becomes clear that we've been looking at a brute-force thing. I could take Lin and Kernighan's original enhancements and drop those on top, but the paper we've been using goes out of its way to explain why that's a bad idea. We'd have to look at the part where he talks about his better idea to see if it makes sense. I do think that the newer code will make it much easier to implement whatever I end up using. Also putting up a pretty flow chart that I made.
Tue Sep 21
- in Jim's office, tried to outline simplified L-K; uploaded tsp.py ... which is all comments.
- need to create an API for what this needs, and put into real python code
Sunday 9/19
Started to debug the Djikstra's code. Ran through the Lin-Kernighan summary again and I think I understand the initial presentation of the algorithm - not sure about the later modifications, both those that Lin and Kernighan made, and those that the guy who wrote the thesis made. Looked for ways to convert the schedule PDF to text so that I can parse it; found
PyPdf, which didn't work very well, and
PDFMiner, which
seems better, but I haven't gotten to make a successful conversion yet either.
Monday 9/13
Uploading current code. The random generation bit is more or less as it was; I'm also in the process of implementing Djikstra's Algorithm. I've got it written in Python, but I'm not sure yet if it actually works as it should. It is also messy and untested. I think that for the rest of it, I might actually start writing tests and test cases before I write the code - might as well pretend to follow proper programming practice a little.
Saturday 9/11
I've started coding a little bit of stuff for this. So far, I have code that generates a random set of points and a few paths between them, suitable to then run Djikstra's Algorithm and then a TSP algorithm on.
I also looked at what I'd have to do to get flight data. Star Alliance offers downloadable timetables
here. I can either poke at whatever format their applications download in, or I can get the PDF, convert it, and parse it. Oneworld offers the same sort of thing
here. Skyteam, for whatever reason, does not seem to have a timetable available on their site; I'm just going to ignore them until I get the rest of it working for the other two alliances. If I were to make this a useful tool, rather than just a toy, I'd probably need to spend more effort working on timetable-related stuff than on the TSP; as that is less interesting, I will leave it until all the important features work.
![[paper clip]](/courses/source/wiki_images/paper_clip_tilt.png)
name last modified size