Transport

Question 1

Vehicle Routing

Answer 1

Generalised version of the travelling salesperson problem, which seeks to optimise the set of routes for a fleet of vehicles to travel to go through a set of customers

Question 2

Branch and Bound

Answer 2

Identify the minimum value in each row and then reduce each of the values by this
Do the same with the columns
Total cost of reduction is the sum of all row minimums and the column minimum
This represents the cost of starting at node D
To find the next node, make the D row and column all infinite as well as the column of the node you will be solving for (node 1 in this case)
Make sure this is a reduced matrix by seeing that each row and column has a 0. Add the distance travelled to the cost of reduction (using the value from the initial reduced matrix)
If it isn’t, reduce it and calculate the cost of reduction and add it to the total cost of reduction,
Follow the path with the lowest cost
Continue for all nodes

Question 3

Minimum Number of Vehicles

Answer 3

Replace infinities with 0s
This lets the solution have 2 consecutive instances of D

Question 4

Clark Wrighte

Answer 4

𝑆𝑖𝑗 = 𝑑01 + 𝑑02 − 𝑑12

The savings in this problem, arranged in decreasing order have been calculated
Demands q = [4 , 6, 3, 5, 3, 6] and Q = 15
Start from the first pair (1-2) which gives the maximum savings (quantity of 10, 4+6)
Go onto 2-?, and analyse the highest savings until you find one with a quantity inside the max capacity of the truck
D-2-1-3-D (13) and D-5-6-4-D (14) saves 40 units

Question 5

Limitations

Answer 5

The limitations of Clarke Wright algorithm can be addressed with a few other heuristics, for example with HOLMES-PARKER EXTENSION

We ignore 1-2, and instead start with 1-3 following the same procedure. However, resulting in a lesser distance travelled with D-4-3-1-D and D-6-2-5-D