Question

Problem 1 - Local routing II

//////////////////////////////

You are routing your vehicles to deliver goods to seven customers. The customers are identified with an ID.

These are the distances between the customer locations and the distribution centers in miles.

Distance	1	2	3	4	5	6	7	DC
1		16.3	16.5	20	19.6	17.9	9.3	12.7
2			7.2	14.9	16.6	16.6	12.7	11.5
3				8.9	10.1	11	10.8	9.8
4					7.3	13.4	19.1	17.5
5						12.9	16.4	16.1
6							9.4	17.4
7								3.6

These are the number of boxes the customers need.

Customer ID	1	2	3	4	5	6	7
Demand (Boxes)	24	38	19	37	23	21	10

------------------------------

Vehicle routes

Consider that each of your trucks can carry, at most, 100 boxes per tour. Use the Savings algorithm to design the routes.

Tip: Remember that the Savings algorithm is a heuristic algorithm. This means that the solution provided by the Savings algorithm will not necessarily be the optimal solution to the problem.

Important: Write the sequence of customers with a dash between the ID numbers (do not use spaces and do not include “DC”). For example, if the route goes from DC to 5 to 2 to 6 to DC, write 5-2-6 or 6-2-5 (both are considered correct). In the above example, 2-5-6 or 2-6-5 would be considered wrong!

How many tours do you need?

-------------------------------

What are the savings (in distance traveled) compared to delivering directly from the DC to each customer?

Round your result to one decimal digit

-----------------------------

In the following questions, you will be asked to describe the route/tour that includes certain customers. Please, for designing the routes, use exclusively the Savings algorithm. (Do not further optimize the paths obtained from the Savings algorithm using other methods. Provide the answer in the format that is specified.)

Please describe the tour including Customer 1.

Write the sequence of customers with a dash between the ID numbers (do not use spaces and do not include “DC”). For example, if the route goes from customer 5 to 2 to 6, write 5-2-6 or 6-2-5. Please remember to follow the order in which the customers are visited. In the above example, 2-5-6 or 2-6-5 would be considered wrong.

-----------------------------------

Please describe the tour including Customer 2.

Write the sequence of customers with a dash between the ID numbers (do not use spaces and do not include “DC”). For example, if the route goes from customer 5 to 2 to 6, write 5-2-6 or 6-2-5. Please remember to follow the order in which the customers are visited. In the above example, 2-5-6 or 2-6-5 would be considered wrong.

----------------------------------

Please describe the tour including Customer 3.

Write the sequence of customers with a dash between the ID numbers (do not use spaces and do not include “DC”). For example, if the route goes from customer 5 to 2 to 6, write 5-2-6 or 6-2-5. Please remember to follow the order in which the customers are visited. In the above example, 2-5-6 or 2-6-5 would be considered wrong.

--------------------------------

Please describe the tour including Customer 4.

Write the sequence of customers with a dash between the ID numbers (do not use spaces and do not include “DC”). For example, if the route goes from customer 5 to 2 to 6, write 5-2-6 or 6-2-5. Please remember to follow the order in which the customers are visited. In the above example, 2-5-6 or 2-6-5 would be considered wrong.

------------------------------

Please describe the tour including Customer 5.

Write the sequence of customers with a dash between the ID numbers (do not use spaces and do not include “DC”). For example, if the route goes from customer 5 to 2 to 6, write 5-2-6 or 6-2-5. Please remember to follow the order in which the customers are visited. In the above example, 2-5-6 or 2-6-5 would be considered wrong.

---------------------------

Please describe the tour including Customer 6.

Write the sequence of customers with a dash between the ID numbers (do not use spaces and do not include “DC”). For example, if the route goes from customer 5 to 2 to 6, write 5-2-6 or 6-2-5. Please remember to follow the order in which the customers are visited. In the above example, 2-5-6 or 2-6-5 would be considered wrong.

---------------------------------

Please describe the tour including Customer 7.

Write the sequence of customers with a dash between the ID numbers (do not use spaces and do not include “DC”). For example, if the route goes from customer 5 to 2 to 6, write 5-2-6 or 6-2-5. Please remember to follow the order in which the customers are visited. In the above example, 2-5-6 or 2-6-5 would be considered wrong.

Answer 1

• First, we can calculate the distance savings matrix
• Secondly, we can figure out the rank of svings to figure out the pairing of customers. The pairing can only be done if the aggregate of the demand value does not exceed the given value ie 100

The distancesavings matrix can be calculated as follows

Distance	1	2	3	4	5	6	7
1		7.9	6	10.2	9.2	12.2	7
2			14.1	14.1	11	12.3	2.4
3				18.4	15.8	16.2	2.6
4					26.3	21.5	2
5						20.6	3.3
6							11.6

• Based on this matri, ranking table can be easily identified. I am attaching the rank table as well

Distance	Trips	Rank	Tour
26.3	4->5	1	4->5
21.5	4 6	2	5 4 6
20.6	5 6	3	na
18.4	3 4	4	na
16.2	3 6	5	3 6 4 5
15.8	3 5	6	na
14.1	2 3	7	na
14.1	2 4	8	na
12.3	2 6	9	na
12.2	1 6	10	na
11.6	6 7	11	na
11	2 5	12	na
10.2	1 4	13	na
9.2	1 5	14	na
7.9	1 2	15	1 2
7	1 7	16	2 1 7
6	1 3	17	na
3.3	5 7	18	na
2.6	3 7	19	na
2.4	2 7	20	na
2	4 7	21	na

From the above table we see the below conclusions

• Pairing at first need to be for customer 4 and 5. SO the sequecne is 5-4-6
• Conequently, our very first tour would be DC-3-6-4-5-DC or it can be DC-5-4-6-3-DC.
• Further, lets move down, we get 1 and 2, making tour DC-1-2-DC or DC-2-1-DC.
• Now, we can pair 1 and 7, so our tour can be DC-7-1-2-DC or DC-2-1-7-DC.

Answers

Tours needed : 2

Savings in distane traveled : 78.9

Tour including customer 1 : 2-1-7 or 7-1-2

Tour including customer 2 : 2-1-7 or 7-1-2

Tour including customer 3 : 3-6-4-5 or 5-4-6-3

Tour including customer 4 : 3-6-4-5 or 5-4-6-3

Tour including customer 5 : 3-6-4-5 or 5-4-6-3

Tour including customer 6 : 3-6-4-5 or 5-4-6-3

Tour including customer 7 : 2-1-7 or 7-1-2