Shortest Routes Problem Solving - School Driver

Authors Avatar

Shortest Routes Problem Solving – School Driver

My aunt, a school driver, she has a problem of picking the student up to school. She lives in Belvedere Garden, and picks student to the school in Shek Lei Estate (the map is on the last page). In order to save the cost by shorten the distance to the school, she asked me to solve the problem for her.

By the virtue of keen competition, she couldn’t charge for the high fees from the students. Besides, the fuel is very costly and variable. Thus, her income becomes unstable. She tries to solve it by picks up more students from different places, but the routes will be more complex and the time does not allow her to do so. She has to pick 50 students up from 12 places, there are 10 seats left and therefore she can only save the cost by pick more students up from these 12 places but not the other places. I also found her driving routes have a great problem, she didn’t choose the fastest way. So I will choose the fastest routes for her.

She has to drive 4 times per school day

1. From BG to SLE (through all places in shortest routes)

2. From SLE to BG (fastest routes to back home)

3. From BG to SLE (fastest routes to back to school)

4. From SLE to BG (through all the places in shortest routes)

I have asked her where the 12 places were, how much profits she earns totally per month and how much the costs are. Here is the information:

The name of the twelve place:

Belevedere Garden Phase 3 (BG)

Tsuen King Garden (TKG)

Clague Garden Estate (CGE)

Discovery Park (DP)

Water Side Plaza (WSP)

Luk Leung Sun Chuen (LYSC)

Pa Tin Pa Tsuen (PTPT)

Kwai Yin Court (KYC)

Lei Muk Chuen Estate (LMSE)

Shek Yam Estate (SYE)

Shek Yam East Estate (SYEE)

Shek Lei Estate (SLE)

The distances between the places:

The cost of her original routes:

First drive:

BG→CGE→DP→TKG→PTPT→LYSC→WSP→KYC→LMSE→SYE→SYEE→SLE

12.6km

Second drive:

After sending the students to the school, my aunt will then go back home (From SLE to BG). Her original route is showed below:

BG→DP→KYC→SLE

5km

Third drive:

She has to pick up the students again after the school (From BG to SLE). Her original route is showed below:

SLE→KYC→DP→BG

5km

Fourth drive:

SLE→SYEE→SYE→LMSE→PTPT→LYSC→KYC→WSP→DP→TKG→CGE→BG

13.09km

The total distance of the whole drive is 12.6 + 5 + 5 + 13.09=35.69km

There are 22 school days average per month, which means the total distance of one month is

35.69 x 22 = 785km

In HK, the cost of the fees are 15p per km average, thus her original cost per month is

Join now!

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.

...

This is a preview of the whole essay