12
$\begingroup$

I changed the title of my question and tried to simplify formulation of the problem.

I solve a very big vehicle routing problem. I divided this one big problem on many small sub-problems. Each small sub-problem is only for the one vehicle. As in the traveling salesman problem vehicle needs to visit every point and it's needed to minimize total distance. In every point vehicle leaves a part of the cargo in it. And I have very special distance metric:

Sum( EuclideanDistance[point_i, point_j] * remaining_weight_at_point_j )

I have no any constraints (time constraint of delivery or something else). I need only to minimize the total distance. "Vertex priority" means that in some cases it's optimal to deliver cargo in point with higher weight and after that return back. I show it in example below.

It should be noted that in the real application I use GeoDistance and have tens of points in every sub-problem.

Data and visualization

pts = {
   (*X,Y,weight*)
   {1, 2, 1},
   {3, 2, 1},
   {2, 1, 5}
   };

epsilon = 0.001; (*certain very small number, base weight, we are returning with it from the end point to the start*)

totalWeight = Total@pts[[;; , 3]];

start = {2, 3, totalWeight + epsilon};

ListPlot[
 Append[
  Table[Labeled[pts[[i, {1, 2}]], pts[[i, 3]]], {i, Length@pts}], 
  Labeled[start[[{1, 2}]], "start point, " ~~ ToString@start[[3]]]],
 PlotRange -> {{0, 4}, {0, 4}}
 ]

enter image description here

FindShortestTour

tour = Last@FindShortestTour[Prepend[pts[[;; , {1, 2}]], start[[{1, 2}]]]];

ListLinePlot[
 Join[{start[[{1, 2}]]}, pts[[;; , {1, 2}]], {start[[{1, 2}]]}][[tour]],
 PlotRange -> {{0, 4}, {0, 4}}
 ]

enter image description here

sub1 = Join[{start}, pts, {start}][[tour]];
(* {{2, 3, 7.001}, {3, 2, 1}, {2, 1, 5}, {1, 2, 1}, {2, 3, 7.001}} *)

metric = Dot[
 EuclideanDistance @@ # & /@ Partition[sub1[[;; , {1, 2}]], 2, 1],
 7.001 - Accumulate@Prepend[sub1[[2 ;; -2, 3]], 0]
 ]

(* 19.8046 *)

Answering on Anton Antonov question in comments: "remaining weight at point j" is that the weight at arrival at j.

Dot[
 {Sqrt[2], Sqrt[2], Sqrt[2], Sqrt[2]},
 7.001 - {0, 1, 6, 7}  (* {7.001, 6.001, 1.001, 0.001} *)
 ]

Optimal order of vertex visit

sub2 = {
   start,
   {2, 1, 5},
   {1, 2, 1},
   {3, 2, 1},
   start
   };

ListLinePlot@sub2[[;; , {1, 2}]]

enter image description here

Dot[
 EuclideanDistance @@ # & /@ Partition[sub2[[;; , {1, 2}]], 2, 1],
 7.001 - Accumulate@Prepend[sub2[[2 ;; -2, 3]], 0]
 ]

(* 18.8353 *)

I hope that now my question is more clear.

Useful answer will be awarded with the additional bounty 200 points (1/3 of my current reputation).

$\endgroup$
  • $\begingroup$ Здравствуйте @AlexeyGolyshev, is it safe to assume that 'part of the cargo' is a known quantity? $\endgroup$ – e.doroskevic Dec 4 '15 at 9:43
  • 1
    $\begingroup$ @E.Doroskevic Yes. For example, pts[[1]] (*{1.47545, 0.982238, 3}*) Part of cargo = 3. $\endgroup$ – Alexey Golyshev Dec 4 '15 at 9:45
  • $\begingroup$ What are the constraints? I have a solution ready, but I am not entirely convinced it answers fully the question you left. I got to the point where I can identify the points in the shortest tour and the associated cargo dispatched at these particular points. Is that what you are looking for? $\endgroup$ – e.doroskevic Dec 4 '15 at 12:14
  • $\begingroup$ @E.Doroskevic I solve a very big vehicle routing problem. I divided this one big problem on many small problems. Each small problem is only for the one vehicle. My question is the toy example of such small problem. I would like to beat my naive benchmark. I will update my post in few minutes. $\endgroup$ – Alexey Golyshev Dec 4 '15 at 12:37
  • $\begingroup$ @AlexeyGolyshev Please define "remaining weight at point $j$" in the definition of the minimization function. Is that the weight at arrival at $j$ (i.e. after leaving $i$) or the weight after leaving $j$ ? $\endgroup$ – Anton Antonov Dec 4 '15 at 18:55
6
$\begingroup$

I have solved this problem as asymmetric travelling salesman problem.

Mathematica cannot to solve these kind of problems directly.

FindShortestTour[
 Prepend[pts[[;; , {1, 2, 3}]], start[[{1, 2, 3}]]],
 DistanceFunction -> (EuclideanDistance[#1[[{1, 2}]], #2[[{1, 2}]]]/#2[[3]] &)
 ]

FindShortestTour::asymdi: The distance function must be symmetric. >>

{3.31327, {1, 3, 4, 2, 1}}

So I converted to the symmetric TSP.

mat = DistanceMatrix[
   Join[#, #] &@Prepend[pts, start],
   DistanceFunction -> (EuclideanDistance[#1[[{1, 2}]], #2[[{1, 2}]]]/#2[[3]] &)
   ];

mat = ReplacePart[
   mat,
   {
    {i_?(1 <= # <= 4 &), j_?(1 <= # <= 4 &)} -> 0.,
    {i_?(5 <= # <= 8 &), j_?(5 <= # <= 8 &)} -> 0.
    }
   ];

g = WeightedAdjacencyGraph[mat /. (0. -> ∞)]

Last[FindShortestTour[g]] /. _?(# > 4 &) -> Nothing

(* {1, 4, 2, 3, 1} *)

UPDATE

It seems that simple TSP is better than asymmetric TSP in the case of a large number of points (file). Can it be improved further?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.