MA2760: Mathematical Investigations with Python
Coursework II
Rhyd Lewis
LewisR9@cf.ac.uk
1 Summary
In this assessment you are asked to write a program that attempts to find good solutions for a vehicle routing problem
using simple optimization techniques. Specifically, your program will read in a problem instance from a file and will
attempt to produce a solution using what are known as “local search” methods. Details of your methods, together with
their results (including tables of results and charts), should then be written-up in a formal report.
A LATEX file and some example code has been placed on Learning Central / Blackboard. Please use these as starting
points for your work.
2 Problem Specification
Every day a medical firm is given a list of patients that require a home visit. The medical firm employs a number of
doctors in the local area and needs to decide which doctors will visit which patients, and in what order. Once this has
been decided, each doctor leaves their home, visits each patient assigned to them, and then returns to their home. The
firm is interested in minimizing the total distance travelled by the doctors while ensuring that all patients are visited.
For various reasons, the number of patient visits per doctor per day is also limited to a fixed amount.
This problem is more precisely stated as follows. In total, we are given N separate (x, y) coordinates on a map. The
first n1 coordinates give the locations of each doctor’s home in turn. The remaining n2 = N − n1 coordinates then
give the locations of each patient in turn. The maximum number of visits per doctor m is also specified. Finally, an
N ×N matrixD is used, where Dij gives the driving distance from the ith coordinate to the jth coordinate.
Instances of this problem are specified in text files. The text file starts with the parameters n1, n2, and m respectively.
This is then followed by the n1 coordinates of the doctors’ homes, the n2 coordinates of the patients’ homes and,
finally, the N ×N distance matrix.
v0
v1
v2
v3 v4
v12 v9
v10 v7
v11
v8
v6
v5
Doctors’ homes
Patients’ homes
S = [ [3, 4, 9, 12],
[5, 10, 6],
[7, 11, 8] ]
Solution Representation
1
The figure above shows a small example of this problem using n1 = 3 doctors, n2 = 10 patients (giving N = 13),
and m = 4. It also shows how a candidate solution S to this problem can be conveniently stored as a two-dimensional
array (a list of lists in Python). This has n1 rows, and the patients of the ith doctor appear in row i of S in the order
that they are to be visited.
The cost of a candidate solution S is simply the sum of the distances travelled by all of the n1 doctors. Our task is to
find a solution that minimizes this cost. This cost is calculated as
∑(n1−1)
i=0 f(i), where f(i) calculates the cost of the
ith doctor’s route. This is defined as follows:
f(i) =
{
Di,S[i][0] +
(∑(li−2)
j=0 DS[i][j],S[i][j+1]
)
+DS[i][li−1],i if li > 0
0 otherwise.
Here, li gives the length of the ith list in S. Note that values of li greater than m are not allowed. For the example
solution in the figure above, the cost is calculated as f(0) + f(1) + f(2)
=D0,3 +D3,4 +D4,9 +D9,12 +D12,0
+D1,5 +D5,10 +D10,6 +D6,1
+D2,7 +D7,11 +D11,8 +D8,2.
3 Task 1 (approx 20%)
On Learning Central you will find two files, p1.txt and p2.txt. These specify problem instances using the layout
described earlier. Also available is the Python file doctor.py, which reads in these files.
The first task is to extend doctor.py to produce an initial solution S to this problem in a random fashion (no sophisti-
cated methods are needed at this point—a simple random assignment is fine). A cost function should then be written
that calculates the cost of a solution as described above. Note that it is critical for your cost function to be correct; thus
it is worth checking things manually using the small problem in p1.txt.
4 Task 2 (approx 20%)
The next task is to extend your program by implementing a local search technique. A simple example of this technique
operates by repeatedly applying the following step: Take the current solution S and make a small change to it. If this
change causes the cost of the solution to increase, then reset the change; otherwise keep the change.
Some suggested ways of making these changes include:
• Randomly selecting a single element S[i][j] in S and moving it into a different randomly selected route S[k]
(where i 6= k), providing that this does not result in more than m patients in the route;
• Randomly selecting two elements in S and swapping their contents.
As explained, your local search method should only accept changes that decrease or maintain the current cost. It should
also be run for a fixed number of iterations (typically a few thousand).
5 Task 3 (approx 10%))
Now modify your code so that useful graphical information is output to the user at the end of a run. Two things you
might want to include are: (a) an iterations vs cost line-graph that demonstrates how the cost has reduced during a run;
2
and (b) an attractive visual representation of the best solution found in the run (e.g., using NetworkX or by producing
a connected scatter plot) like the example shown in the figure earlier.
6 Task 4 (approx 50%)
Once you have successfully completed Tasks 1–3, there are a number of opportunities for further investigation which
can be implemented and documented in your report. Here are some ideas (note that there is no need to try all of these
ideas, and that you are also welcome/encouraged to come up with your own).
Produce problem instances and visualizations using on-line mapping services: You may want to write a separate
program for producing your own realistic problem instances using a set of valid GPS coordinates for doctor and
patent addresses, and then using mapping services to populate the matrix D. In your main program, mapping
services might also be used to produce a static image of each doctor’s route.
Consider other ways in which the solution can be changed: Two example operators have been suggested in Task-
2; however, others are available. For example, you might also try inverting a part of a route ([a,b,c,d,e,f,g]
becomes [a,b,f,e,d,c,g]) or moving a section of a route into another route. (Feel free to research this.)
Try making your local search code more efficient: For example, when making a small change, you may notice that
only some rows in S are altered. Thus, you may be able to speed up your program by only re-evaluating the
effected rows.
Try creating better quality initial solutions: For example, instead of just randomly assigning patients to doctors,
why not add some “intelligence” to the procedure to hopefully reduce the cost of the initial solution?
Try using more sophisticated search techniques: Rather than using the simple technique described in Task 2 (which
only allows changes that reduce or maintain the cost of S), why not occasionally allow worsening moves too,
enabling further solutions to be considered? You may wish to consider methods such as simulated annealing,
tabu search, or the great deluge algorithms here (you will need to research these), or you might want to try
creating your own method.
7 Extra Information
• Note that the globally optimal solutions (or costs) to these problems are not currently known, so algorithms
seen to quickly achieve low cost solutions will be viewed more favourably. Obviously one way of getting better
results is to allow your program to run for more iterations. However, let us agree that very long runs (more than
10 seconds on the lab machines) should be avoided.
• At the end of each run, your final solution (the best observed solution from the run) should be printed to the
screen along with its claimed cost. Note that your tutor will use their own checker program to confirm that the
cost of these solutions is the same as the claimed costs.
• You will have noticed that some of these tasks are open ended. You are therefore free to choose your own
directions for these parts, which can then be documented.
• Extra marks will be allocated to submissions that use neat, elegant, efficient code that is appropriately com-
mented.
• Marks are also allocated to reports that are written accurately and succinctly, with appropriate typesetting.
(Please use the supplied LATEX code). You may also wish to use various figures and tables in your report.
• It is also acceptable to include small pieces of your Python code within your report if it helps to explain some-
thing. However, bear in mind that you are also required to submit your code in a separate file.
3
8 Assessment and Submission
Marks will be allocated subject to the above tasks being carried out and documented appropriately. Note that it is
usually preferable to have a less-advanced program that runs correctly rather than a more advanced program that does
not run or that has bugs in it. The coursework should be submitted in paper form to the school office by midday,
Monday 15th of May.
• In their paper submissions, groups should provide (a) their report (b) neat printouts of their final code and (c) a
completed and signed peer assessment form.
• Before the deadline, one member of the group should also email the lecturer a single zip file containing their
Python file and their pdf. The title of the email and names of these files should be your group number: (i.e.
Group1, Group1.zip, Group1.py and Group1.pdf).
• The recommended length of the report is five pages using the supplied LATEX template. Reports should conform
to this template and should not exceed eight pages under any circumstances.
• During a lab session, each group will also be required to sit with the lecturer and give them a short overview of
the code, demonstrating how it is run. There is no need to prepare any materials for this part.
Please note that, according to university rules, unauthorised late submissions must be allocated a mark of zero by
default. Also according to university rules, instances of plagiarism are not be tolerated; indeed, one member of each
group will be required to sign a form indicating that your work has not been plagiarised on submission in the school
office. It is natural that students from different groups will sometimes exchange ideas and help each other out in
completing coursework of this nature; however, please be mindful that flagrant instances of copying will result in both
parties receiving zero (this has happened in some of my modules in the past, so you have been warned!).