Real world application for math example (Maybe pattern recognition)

[Keba]

Homework Statement

My dad is driving coal. His truck has a limited coal-capacity, and enough fuel. He drives this coal from the central which has enough coal, to farmers that need different amounts. As there are many farmers, he has to drive back and forth several times. He knows all distances, and how much coal each farmer needs. When all farmers have their needed coal, he notes the total distance his truck has driven.

How can he make a route, that minimizes the total distance his truck has driven?

Homework Equations

The Attempt at a Solution

This is not from any assignment, but from a real problem which directly affects when my dad gets home from work.
I figure, If I get all the distances, I can make a map of the problem using Multidimensional Scaling, and then apply a modified k-nearest neighbors algorithm, that has a stop criteria of the truck capacity, and thus takes the amounts of coal into account.

What strategy would you use?

 

[Ray Vickson]

Homework Statement

My dad is driving coal. His truck has a limited coal-capacity, and enough fuel. He drives this coal from the central which has enough coal, to farmers that need different amounts. As there are many farmers, he has to drive back and forth several times. He knows all distances, and how much coal each farmer needs. When all farmers have their needed coal, he notes the total distance his truck has driven.

How can he make a route, that minimizes the total distance his truck has driven?

Homework Equations

The Attempt at a Solution

This is not from any assignment, but from a real problem which directly affects when my dad gets home from work.
I figure, If I get all the distances, I can make a map of the problem using Multidimensional Scaling, and then apply a modified k-nearest neighbors algorithm, that has a stop criteria of the truck capacity, and thus takes the amounts of coal into account.

What strategy would you use?

Your problem is an example of the Operations Research problem known as the "Truck Dispatching Problem", and is closely related to the so-called "Vehicle Routing Problem". The truck dispatching problem was first posed by Dantzig and Ramser, Management Science, Vol. 6, No. 1, 1959, pp. 80-91. Those authors gave near-optimal solutions of the problem using linear programming formulations. A great deal of subsequent work has been done on this problem, and numerous usable systems for getting near-optimal solutions exist, using various tools such as integer programming, tabu search, etc., as well as through a host of constructive heuristics. One source that you can look at is the 400-page report freely downloadable as a pdf file (or readable on screen) from the EPA. Do a Google search under "truck dispatching problem" and then scroll down to an entry entitled "Mathematical Analysis of Solid Waste Collection" (the URL is too long to put here). It has chapters on the models and algorithms used, and carries out tests of these on numerous example problems.

RGV

 

[Keba]

Thank you for responding.
I was able to find some of the report, namely the part describing the Truck Dispatching Problem. "ftp://124.42.15.59/ck/2011-01/165/020/665/238/The%20Truck%20Dispatching%20Problem.pdf"[/URL]
It is the exact problem I am having.
I found the stated solution hard to follow, so I don't think I can recreate it for myself. You mentioned near-optimal solutions existed. Am I to understand, that there are finished algorithms available, that I can simply supply with a distance matrix, truck capacity and a delivery vector, and it will propose a solution?

 

[Ray Vickson]

I think the answer is YES: you can supply the data and the computer will spit out an answer of perhaps good quality (very likely better than anything you could come with on your own). The next question is: how do we get one of these codes? There, I am unsure; vehicle routing was not my speciality when still teaching and doing research. However, I can suggest you go to the INFORMS website and look therein for resources related to the situation. In particular, INFORMS maintains a listing of free software for a wide variety of problems, andaybe you will find what you need. Of course, there are numerous commercial packages available, but they might be very costly. You might also try posting your problem to the Operations Research newsgroup "sic.op-research", although that forum has been underutilized lately.

Good luck.

RGV

RGV

 

[Ray Vickson]

Sorry for the typos above. Doing this on an i-phone allows only limited editing, and I cannot seem to scroll down in edit mode. Anyway, the newsgroup is "sci.op-research". Let's hope the speller does not change "s c i" to "s i c".

RGV