2
$\begingroup$

I'm trying to find the "looped" route with the lowest value of D/n, where D=Distance, and n=Number_of_points, for a cloud of 3D points. However there are a few conditions.

Conditions:

Each point must have one or more points in the route that are greater than $X$ distance away.

Not every point needs to be passed through.

I will try and explain what I mean: Imagine a system of delivery routes, whereby you get paid only if the delivery point is greater than $X$ meters away from the pickup point.

So, if you travel point $A \rightarrow B$ where the distance is $X$, you get paid, but you have been paid once in $X$. If you have say 10 equidistant points on a circle with circumference $X$. The distance in a line between them is $X/10$. So you are stopping once every $x/10$ to pick up a new package. Now, once you travel half way around the circle to point 5, you can deliver the package from the starting point and get paid. This means once the route has been completed halfway, you are getting paid every $X/10$ instead. Much more efficient.

Now here is the kicker, my data is not in a neat circle, but rather a cloud of 3D points.

Which algorithm or set of algorithms could be used to determine the most efficient route between the number of points?

Sorry if I horribly explained my problem, from what I understand the problem might be NP-complete but if an approximate solution can be calculated, that would work.

|cite|improve this question
$\endgroup$
  • $\begingroup$ If I understand your question, the 3D "cloud" of points consists of some where there are packages to pick up and some where there are deliveries to be made. Supposing for the moment you have full knowledge of these opportunities, and that the capacity of the delivery vehicle is such that the number of package pickups is not constrained, you want to compute the shortest route to deliver all of them. $\endgroup$ – hardmath Apr 7 '15 at 14:00
  • $\begingroup$ In particular the payoff depends only on whether the pickup and delivery points are at distance $X$ or more, and so one simply ignores the packages for which this is not true. $\endgroup$ – hardmath Apr 7 '15 at 14:02
  • $\begingroup$ Not exactly. Their is no upper or lower limit to the number of nodes, and each node is always both a pickup and a dropoff. A perfect route would be one where the pickup and dropoff points are separated by the minimum distance possible, and each have a point at least $X$ away. $\endgroup$ – Waabbit Apr 7 '15 at 17:43
  • $\begingroup$ It's unclear what you found to disagree with in what I wrote. I said "the number of package pickups is not constrained," and you write that there is "no upper or lower limit to the number of nodes". Your description of the perfect route being "one where the pickup and dropoff points are separated by the minimum distance possible" does not follow from the premises outlined in your post. So long as the entire route length is minimized for a given number of payoffs, it will not be suboptimal simply because some of the dropoffs take place over longer distances. $\endgroup$ – hardmath Apr 7 '15 at 17:56
  • $\begingroup$ Perhaps you are saying that any package can be dropped off anywhere, that the destination is not specified by the package being picked up? $\endgroup$ – hardmath Apr 7 '15 at 17:58

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.