Extending Travelling Salesman Problem to accomodate returns: View it here(Better viewed on desktop)
Given that there is two deliveries to points B and C and one heavy pickup at point B. What is the optimised route?
- Can we send an empty truck to pickup returns at point B?(2 trucks Covering B, C nodes)
- Can we introduce a new lighter delivery to point D such that the truck can cover points B and D?(2 trucks covering B, C, and D)
Obviously option 2 is more optimised because it covers more nodes with the same number of trucks. This project handles this problem.
Looking at an example below
Given the points:
| Address | Weight to add to truck |
|---|---|
| 183 E Houston St, NY 10002 | -2 |
| Midtown Manhattan, NY 10010 | 5 |
| Allen Malls, Allen st, NY 10002 | -1 |
| 158e E 23rd St, NY 10010 | 6 |
| 223 1st Ave, NY 10003 | 9 |
The optimised routes given a truck can carry only 10 tonnes is given below:
Route 1