Shortest tour with vertex priority

Question

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}}
 ]

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}}
 ]

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}]]

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).

Answer 1

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?