COM3524 1
1. A delivery company with a single driver needs to optimise their route to deliver to
all cities which are shown on the following map. Distances are in km and the
company’s depot is located in city A. Dotted lines indicate the existence of roads.


Figure 1 Map showing location of depot and cities. Units are in km

Location Xi (km) Yi (km)
A (Depot) 50 15
B 80 10
C 90 50
D 40 50
E 30 30
Table 1 Co-ordinates of dept and cities (in km)
The delivery company commissions you to develop a bio-inspired algorithm to find the
best delivery route for them (meaning that every delivery site is visited only once and the
route length is minimised). In the first instance, you decide to use an Ant Colony
Optimisation Algorithm (ACO).

0 10 20 30 40 50 60 70 80 90 100
0
10
20
30
40
50
60
A
B
C D
E
a) Explain briefly in a maximum of 100 words what is meant by an ACO and the key
biological behaviour that it is inspired by. [10%]

{ANSWER)
b) The probability of ant k located at node r, choosing to transition to an allowed
node, s, is given by the following formula:


Where τ is the pheromone strength on edge rs, and η is the inverse of distance
between nodes r and s.
a, b are weighting parameters
At the start of the simulation, assume that pheromone is equally distributed on all
model edges (=1) and a, b are both set to one.
In the first update step, what is the probability that an ant located at the depot will
transition to i) node B, ii) node D and iii) node E? [20%]

c) You fully implement your ACO algorithm and find it works reasonably well.
However, you are keen to explore other bio-inspired approaches to solve the
problem and decide to supervise a student project to develop an Evolutionary
algorithm to apply to the same problem, so you can compare them.
The student reads a textbook on Evolutionary Algorithm approaches and presents
you with the following plan for the algorithm that they propose to implement
1. Generate random initial population of any route permutations of ABCDE
2. For every chromosome
3. Calculate fitness = 1/total route length
4. Select Parents for Mating Pool based on relative fitness
5. Implement probabilistic One Point Crossover to generate new offspring
6. Implement probabilistic Random Swap Mutation on offspring
Give two reasons why this proposed algorithm might give rise to some invalid
solutions to the specific delivery problem described on page 1.
[20%]
åÎ
=
ALLOWEDt rtrt
rsrsk
rsp ba
ba
ht
ht
COM3524 3

d) Your student takes note of your suggestions and implements a revised version of
the Evolutionary Algorithm, that appears to work.
The delivery company asks you to implement your preferred algorithm for them,
with their primary requirement that delivery routes for up to 10 possible delivery
cities are identified as quickly and efficiently as possible. They want the software
to be delivered to them, fully functional and optimised as much as possible, by
the end of the week.
i) From your knowledge of the characteristics of the two approaches, explain
which algorithm you would choose to package for the client, and why.
[20%]
ii) A month later, they phone to let you know that they have been taken over
by a larger company, and will now be delivering to up to 100 cities
nationwide. They ask you whether you think your previously delivered
algorithm will still work efficiently in this scenario. What is your response?
[10%]
e) The new parent delivery company imposes a new business model. Under this
new model, its staff receive commission for every parcel that they deliver. The
expanded fleet of vehicles at other depots means that not every driver needs to
visit every city on every trip, but they must still start and finish at their depot and
visit at least 3 other locations. The aim of your original client is to keep their inter-
city travel distance as low as possible, whilst maximising their commission.
The number of parcels to be delivered in city i, can be denoted as Ni
Your student is still working on their Evolutionary Algorithm (irrespective of
whether it is actually being used by the client!). How would the student need to
modify steps 1 and 2 of their algorithm (from part c) in order to take this into
account? [20%]



END OF QUESTION PAPER