Minimum number of Trips

Question

I have latitude and longitude points of N societies, order count of these societies, I also have latitude and longitude points of a warehouse from where the trucks will deploy and will be sent to these various societies(like Amazon deliveries). A truck can deliver maximum 350 orders (order count < 350). So no need to consider items with order count above 350 (We generally would send two trucks there or a bigger truck). Now I need to determine a pattern in which the trucks should be deployed in such a way that a minimum number of trips occur.

Considering that we determine the distance between two societies or warehouses is 'X' from this script is accurate, How do we solve this? I first thought that we could solve it using sum of subset problem, maybe? Seems like dp on graphs to me, traveling salesman problem with infinite number of salemans.

There are no restrictions on the number of trucks.

@Henry I did what you said and fortunately managed to find the solution to this, Thanks a lot. — Naman Chikara, Jan 24 '19 at 22:01

score 2 · Accepted Answer · answered Jan 23 '19 at 13:47

2

This is a typical Travelling salesman problem (TSP) which is known as NP-complete. It means that if you are looking for the optimal solution you have to test most of combinatorics. And as you know, !350 is tremendeous.

Nevertheless, as Henry suggests, you can look for a good solution which is not necessarily the best. A lot of algorithm called "heuristic" let you find one good solution in a very efficient way. Just have a look here for some examples https://en.wikipedia.org/wiki/Travelling_salesman_problem.

The most simple heuristic algorithm may be a greedy solution like always take the closest unvisited point as next society.

answered Jan 23 '19 at 13:47

Vince

336
1
11

Thank you, this did help me to find the solution to this. https://pastebin.com/81SRjuKw this is my code, head over to line 39 for the algorithm part. – Naman Chikara Jan 24 '19 at 21:59
1

@NamanChikara Hum you should consider to use numpy. This would make your code a lot faster and simpler. – Vince Jan 25 '19 at 09:55
My prof told me to do the same, Thanks :) – Naman Chikara Jan 25 '19 at 22:43

Minimum number of Trips

1 Answers1