Need help formulating a Traveling Salesman (Deliveryman) Variation

60 Views Asked by At

I am working with the following TSP variation:

A deliveryman has to deliver orders of items to several different locations around a city. The orders are:

Store 1: 25 items
Store 2: 60 items
Store 3: 20 items
Store 5: 10 items
Store 6: 20 items
Store 7: 50 items
Store 8: 70 items
Store 9: 15 items

And one constraint is that the truck can only carry 90 items at once, so he needs to optimize for both distance and load/capacity.

Can someone help me to describe this mathematically? Perhaps point me toward an algorithm or a formula?

1

There are 1 best solutions below

0
On BEST ANSWER

I think I have figured out what type of problem this is, and identified a source of solutions: I think this is a "Capacitated Vehicle Routing Problem," and this link from Uni Heidelberg appears to have some solutions.