785 x 15p = £118 and her income is £810. So her actual income decreases to £810 - £118 = £692
Now I am going to find out the shortest routes of four drives. For the first drive and the last drive, I solve the problem by showing all possible ways as she has to go through all 12 places. The second and the third drive, I do only find the shortest routes and therefore I will use the Dijkstra’s algorithm. There are 52 way in the first drive and 66 ways in the fourth drive.
Possible ways for first drive:
BG→TKG→PTPT→DP→CGE→LYSC→WSP→KYC→LMSE→SYE→SYEE→SLE
14.57km
BG→TKG→PTPT→DP→CGE→WSP→LYSC→KYC→LMSE→SYE→SYEE→SLE
13.8km
BG→TKG→PTPT→DP→WSP→CGE→LYSC→KYC→LMSE→SYE→SYEE→SLE
15.3km
BG→TKG→PTPT→DP→LYSE→CGE→WSP→KYC→LMSE→SYE→SYEE→SLE
15.41km
BG→TKG→PTPT→DP→LYSE→WSP→CGE→KYC→LMSE→SYE→SYEE→SLE
15.66km
BG→TKG→PTPT→LYSC→DP→CGE→WSP→KYC→LMSE→SYE→SYEE→SLE
13.86km
BG→TKG→PTPT→LYSC→DP→WSP→CGE→KYC→LMSE→SYE→SYEE→SLE
15.59km
BG→TKG→PTPT→LYSC→WSP→DP→CGE→KYC→LMSE→SYE→SYEE→SLE
14.73km
BG→TKG→PTPT→LYSC→WSP→CGE→DP→KYC→LMSE→SYE→SYEE→SLE
14.2km
BG→TKG→DP→PTPT→LYSE→CGE→WSP→KYC→LMSE→SYE→SYEE→SLE
13.65km
BG→TKG→DP→PTPT→LYSE→WSP→CGE→KYC→LMSE→SYE→SYEE→SLE
13.9km
BG→TKG→DP→CGE→WSP→KYC→LYSC→PTPT→LMSE→SYE→SYEE→SLE
12.12km
BG→TKG→DP→CGE→WSP→LYSC→PTPT→LMSE→KYC→SYE→SYEE→SLE
14.32km
BG→TKG→DP→CGE→KYC→WSP→LYSC→PTPT→LMSE→SYE→SYEE→SLE
13.06km
BG→TKG→DP→WSP→CGE→KYC→LYSC→PTPT→LMSE→SYE→SYEE→SLE
13.85km
BG→TKG→DP→WSP→KYC→CGE→LYSC→PTPT→LMSE→SYE→SYEE→SLE
14.56km
BG→TKG→CGE→DP→PTPT→LYSC→WSP→KYC→LMSE→SYE→SYEE→SLE
13.01km
BG→TKG→CGE→DP→WSP→KYC→LYSC→PTPT→LMSE→SYE→SYEE→SLE
12.96km
BG→TKG→CGE→DP→KYC→WSP→LYSC→PTPT→LMSE→SYE→SYEE→SLE
13.37km
BG→TKG→CGE→LYSC→WSP→KYC→DP→PTPT→LMSE→SYE→SYEE→SLE
13.94km
BG→TKG→CGE→WSP→DP→PTPT→LYSC→KYC→LMSE→SYE→SYEE→SLE
13.74km
BG→TKG→CGE→WSP→DP→KYC→LYSC→PTPT→LMSE→SYE→SYEE→SLE
14.16km
BG→TKG→CGE→WSP→LYSC→KYC→DP→PTPT→LMSE→SYE→SYEE→SLE
14.17km
BG→TKG→CGE→WSP→KYC→LYSE→DP→PTPT→LMSE→SYE→SYEE→SLE
13.89km
BG→CGE→TKG→PTPT→DP→LYSC→WSP→KYC→LMSE→SYE→SYEE→SLE
14.37km
BG→CGE→TKG→PTPT→DP→WSP→LYSC→KYC→LMSE→SYE→SYEE→SLE
14.24km
BG→CGE→TKG→PTPT→LYSC→DP→WSP→KYC→LMSE→SYE→SYEE→SLE
14.3km
BG→CGE→TKG→PTPT→LYSC→WSP→DP→KYC→LMSE→SYE→SYEE→SLE
14.64km
BG→CGE→TKG→DP→WSP→KYC→LYSC→PTPT→LMSE→SYE→SYEE→SLE
12.56km
BG→CGE→TKG→DP→KYC→WSP→LYSC→PTPT→LMSE→SYE→SYEE→SLE
12.97km
BG→CGE→LYSC→KYC→WSP→DP→TKG→PTPT→LMSE→SYE→SYEE→SLE
14km
BG→CGE→LYSC→PTPT→TKG→DP→WSP→KYC→LMSE→SYE→SYEE→SLE
14.1km
BG→CGE→KYC→LYSC→WSP→DP→TKG→PTPT→LMSE→SYE→SYEE→SLE
14.35km
BG→CGE→KYC→WSP→LYSC→DP→TKG→PTPT→LMSE→SYE→SYEE→SLE
14.42km
BG→CGE→WSP→DP→TKG→PTPT→LYSC→KYC→LMSE→SYE→SYEE→SLE
13.33km
BG→CGE→WSP→LYSC→KYC→DP→TKG→PTPT→LMSE→SYE→SYEE→SLE
13.76km
BG→CGE→TKG→DP→PTPT→LYSC→WSP→KYC→LMSE→SYE→SYEE→SLE
12.61km
BG→CGE→DP→TKG→PTPT→LYSC→WSP→KYC→LMSE→SYE→SYEE→SLE
12.6km
BG→CGE→WSP→KYC→LSYC→DP→TKG→PTPT→LMSE→SYE→SYEE→SLE
13.48km
BG→DP→TKG→PTPT→LYSC→WSP→CGE→KYC→LMSE→SYE→SYEE→SLE
14.39km
BG→DP→TKG→PTPT→LYSC→CGE→WSP→KYC→LMSE→SYE→SYEE→SLE
14.14km
BG→DP→TKG→CGE→WSP→KYC→LYSC→PTPT→LMSE→SYE→SYEE→SLE
12.62km
BG→DP→TKG→CGE→KYC→WSP→LYSC→PTPT→LMSE→SYE→SYEE→SLE
13.56km
BG→DP→CGE→TKG→PTPT→LYSC→WSP→KYC→LMSE→SYE→SYEE→SLE
13.5km
BG→DP→WSP→CGE→TKG→PTPT→LYSC→KYC→LMSE→SYE→SYEE→SLE
14.23km
BG→DP→PTPT→TKG→CGE→WSP→LYSC→KYC→LMSE→SYE→SYEE→SLE
14.3km
BG→DP→PTPT→TKG→CGE→LYSC→WSP→KYC→LMSE→SYE→SYEE→SLE
15.07km
BG→DP→KYC→LYSC→WSP→CGE→TKG→PTPT→LMSE→SYE→SYEE→SLE
14.98km
BG→DP→KYC→WSP→LYSC→CGE→TKG→PTPT→LMSE→SYE→SYEE→SLE
15.67km
BG→DP→LYSC→PTPT→TKG→CGE→WSP→KYC→LMSE→SYE→SYEE→SLE
14.36km
BG→DP→LYSC→KYC→WSP→CGE→TKG→PTPT→LMSE→SYE→SYEE→SLE
14.32km
BG→DP→LYSC→WSP→KYC→CGE→TKG→PTPT→LMSE→SYE→SYEE→SLE
15.69km
The possible way of the fourth drive:
SLE→SYEE→SYE→LMSE→PTPT→TKG→DP→LYSC→KYC→WSP→CGE→BG
14.01km
SLE→SYEE→SYE→LMSE→PTPT→DP→LYSC→KYC→WSP→CGE→TKG→BG
14.42km
SLE→SYEE→SYE→LMSE→PTPT→LYSC→KYC→WSP→CGE→DP→TKG→BG
12.89km
SLE→SYEE→SYE→LMSE→KYC→WSP→CGE→LYSC→DP→PTPT→TKG→BG
15.67km
SLE→SYEE→SYE→LMSE→KYC→WSP→CGE→LYSC→PTPT→DP→TKG→BG
13.91km
SLE→SYEE→SYE→LMSE→KYC→WSP→CGE→DP→LYSC→PTPT→TKG→BG
14.1km
SLE→SYEE→SYE→LMSE→KYC→WSP→LYSC→PTPT→TKG→DP→CGE→BG
12.6km
SLE→SYEE→SYE→LMSE→KYC→WSP→LYSC→PTPT→DP→TKG→CGE→BG
12.61km
SLE→SYEE→SYE→LMSE→KYC→WSP→LYSC→PTPT→DP→CGE→TKG→BG
13.25km
SLE→SYEE→SYE→LMSE→KYC→WSP→LYSC→DP→PTPT→TKG→CGE→BG
14.37km
SLE→SYEE→SYE→LMSE→KYC→WSP→LYSC→CGE→DP→PTPT→TKG→BG
14.79km
SLE→SYEE→SYE→LMSE→KYC→LYSC→WSP→CGE→DP→PTPT→TKG→BG
14.1km
SLE→SYEE→SYE→KYC→LMSE→PTPT→TKG→CGE→LYSC→WSP→DP→BG
18.05km
SLE→SYEE→SYE→KYC→LMSE→PTPT→TKG→DP→LYSC→WSP→CGE→BG
16.27km
SLE→SYEE→SYE→KYC→LMSE→PTPT→TKG→DP→WSP→LYSC→CGE→BG
16.89km
SLE→SYEE→SYE→KYC→LMSE→PTPT→DP→LYSC→WSP→CGE→TKG→BG
16.92km
SLE→SYEE→SYE→KYC→LMSE→PTPT→LYSC→DP→WSP→CGE→TKG→BG
16.85km
SLE→SYEE→SYE→KYC→LMSE→PTPT→LYSC→WSP→DP→TKG→CGE→BG
15.35km
SLE→SYEE→SYE→KYC→LMSE→PTPT→LYSC→WSP→DP→CGE→TKG→BG
15.99km
SLE→SYEE→SYE→KYC→LMSE→PTPT→LYSC→WSP→CGE→TKG→DP→BG
15.65km
SLE→SYEE→SYE→KYC→LMSE→PTPT→LYSC→WSP→CGE→DP→TKG→BG
15.15km
SLE→SYEE→SYE→LMSE→KYC→WSP→DP→CGE→LYSC→PTPT→TKG→BG
14.74km
SLE→SYEE→SYE→LMSE→KYC→WSP→DP→LYSC→PTPT→TKG→CGE→BG
14.3km
SLE→SYEE→SYE→LMSE→KYC→WSP→DP→PTPT→LYSC→CGE→TKG→BG
14.7km
SLE→SYEE→SYE→LMSE→KYC→WSP→DP→TKG→PTPT→LYSC→CGE→BG
14.08km
SLE→SYEE→SYE→LMSE→KYC→LYSC→PTPT→TKG→CGE→WSP→DP→BG
14.53km
SLE→SYEE→SYE→LMSE→KYC→LYSC→PTPT→DP→WSP→CGE→TKG→BG
14.04km
SLE→SYEE→SYE→LMSE→KYC→LYSC→CGE→WSP→DP→PTPT→TKG→BG
15.58km
SLE→SYEE→SYE→LMSE→KYC→DP→CGE→WSP→LYSC→PTPT→TKG→BG
14.08km
SLE→SYEE→SYE→LMSE→KYC→DP→WSP→CGE→LYSC→PTPT→TKG→BG
15.94km
SLE→SYEE→SYE→LMSE→KYC→DP→PTPT→LYSC→WSP→CGE→TKG→BG
14.45km
SLE→SYEE→SYE→LMSE→KYC→DP→TKG→PTPT→LYSC→WSP→CGE→BG
13.8km
SLE→SYEE→SYE→LMSE→KYC→CGE→WSP→LYSC→DP→PTPT→TKG→BG
15.9km
SLE→SYEE→SYE→LMSE→KYC→CGE→WSP→LYSC→PTPT→DP→TKG→BG
15.62km
SLE→SYEE→SYE→LMSE→KYC→CGE→DP→WSP→LYSC→PTPT→TKG→BG
14.97km
SLE→SYEE→SYE→LMSE→PTPT→TKG→CGE→LYSC→WSP→KYC→DP→BG
16.26km
SLE→SYEE→SYE→LMSE→PTPT→TKG→CGE→LYSC→KYC→WSP→DP→BG
15.79km
SLE→SYEE→SYE→LMSE→PTPT→TKG→CGE→KYC→LYSC→WSP→DP→BG
16.08km
SLE→SYEE→SYE→LMSE→PTPT→TKG→CGE→KYC→WSP→LYSC→DP→BG
16.15km
SLE→SYEE→SYE→LMSE→PTPT→TKG→CGE→WSP→LYSC→KYC→DP→BG
15.49km
SLE→SYEE→SYE→LMSE→PTPT→TKG→CGE→WSP→KYC→LYSC→DP→BG
15.21km
SLE→SYEE→SYE→LMSE→PTPT→TKG→DP→LYSC→WSP→KYC→CGE→BG
15.01km
SLE→SYEE→SYE→LMSE→PTPT→TKG→DP→KYC→LYSC→WSP→CGE→BG
14.41km
SLE→SYEE→SYE→LMSE→PTPT→TKG→DP→KYC→WSP→LYSC→CGE→BG
15.1km
SLE→SYEE→SYE→LMSE→PTPT→TKG→DP→WSP→LYSC→KYC→CGE→BG
14.88km
SLE→SYEE→SYE→LMSE→PTPT→TKG→DP→WSP→KYC→LYSC→CGE→BG
14.69km
SLE→SYEE→SYE→LMSE→PTPT→DP→LYSC→WSP→KYC→CGE→TKG→BG
15.66km
SLE→SYEE→SYE→LMSE→PTPT→DP→KYC→LYSC→WSP→CGE→TKG→BG
15.06km
SLE→SYEE→SYE→LMSE→PTPT→DP→KYC→WSP→LYSC→CGE→TKG→BG
15.75km
SLE→SYEE→SYE→LMSE→PTPT→DP→WSP→LYSC→KYC→CGE→TKG→BG
15.53km
SLE→SYEE→SYE→LMSE→PTPT→DP→WSP→KYC→LYSC→CGE→TKG→BG
15.34km
SLE→SYEE→SYE→LMSE→PTPT→LYSC→DP→KYC→WSP→CGE→TKG→BG
15.06km
SLE→SYEE→SYE→LMSE→PTPT→LYSC→DP→WSP→KYC→CGE→TKG→BG
15.59km
SLE→SYEE→SYE→LMSE→PTPT→LYSC→KYC→DP→WSP→CGE→TKG→BG
14.93km
SLE→SYEE→SYE→LMSE→PTPT→LYSC→KYC→WSP→DP→TKG→CGE→BG
13.09km
SLE→SYEE→SYE→LMSE→PTPT→LYSC→KYC→WSP→DP→CGE→TKG→BG
13.73km
SLE→SYEE→SYE→LMSE→PTPT→LYSC→KYC→CGE→WSP→DP→TKG→BG
14.62km
SLE→SYEE→SYE→LMSE→PTPT→LYSC→KYC→WSP→CGE→TKG→DP→BG
13.39km
SLE→SYEE→SYE→LMSE→PTPT→LYSC→WSP→CGE→KYC→DP→TKG→BG
15.09km
SLE→SYEE→SYE→LMSE→PTPT→LYSC→WSP→DP→KYC→CGE→TKG→BG
15.93km
SLE→SYEE→SYE→LMSE→PTPT→LYSC→WSP→KYC→CGE→TKG→DP→BG
14.39km
SLE→SYEE→SYE→LMSE→PTPT→LYSC→WSP→KYC→CGE→DP→TKG→BG
13.89km
SLE→SYEE→SYE→LMSE→PTPT→LYSC→WSP→KYC→DP→TKG→CGE→BG
13.56km
SLE→SYEE→SYE→LMSE→PTPT→LYSC→WSP→KYC→DP→CGE→TKG→BG
14.2km
SLE→SYEE→SYE→LMSE→PTPT→LYSC→CGE→KYC→WSP→DP→TKG→BG
15.37km
SLE→SYEE→SYE→LMSE→PTPT→LYSC→CGE→WSP→KYC→DP→TKG→BG
14.84km
The shortest route of the first drive:
BG→TKG→DP→CGE→WSP→KYC→LYSC→PTPT→LMSE→SYE→SYEE→SLE
12.12km
The shortest route of the second drive:
BG→CGE→KYC→SLE
4.93km
The shortest route of the third drive:
SLE→KYC→CGE→BG
4.93km
The shortest route of the last drive:
SLE→SYEE→SYE→LMSE→KYC→WSP→LYSC→PTPT→TKG→DP→CGE→BG
12.6km
Therefore, the new total distance per month is
(12.12 + 4.93 + 4.93 + 12.6) x 22 = 761km
The new cost is
761 x 15p = £114
So her actual income increases to
£810 - £114 = £696
If my aunt is willing to use this my methods, she could save £4 a month (£696 - £692 = £4)
Evaluation
As a result, I saved £4 for my aunt. In England, people may think that £4 is just a little amount of money. However, £4 in Hong Kong and China you can help many poor. They may get warm and full by buying food, clean water and clothes. I suggested my aunt that she could save more by delete the second and the third drives. It saves almost £33 more (4.93 x 2 x 22 x 15p ). It would spend her leisure at home during the resting time but save her more money. She could also earn more by picking more students from those 12 places.
The cost cannot save so much because the routes in Hong Kong are not very long but complex, Hong Kong is just a point in the map only. In addition, she picks students up from 2 districts only and therefore the roads are shorter. The time is a problem as well, she is not allowed to pick more students. Otherwise, all of the students will be late for school and their parents will complain her.
In the first drive and fourth drive, I have found out the shortest routes by showing all possible. Actually, it’s very difficult to find out and it’s take me a long time. When I was doing it, I needed to check many times whether I had showed all the possible or not. Besides, it’s easy to make mistakes when I was calculating the distance of the possible routes.
In the second and the third drive, I used Djkstra’s algorithm to find out the shortest easily. It is very convenience and hard to make a mistake. This is the best method for me which I have learned. I impacted my aunt as well and she found it is useful.