# Shortest tour with vertex priority

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[]]],
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, Sqrt, Sqrt, Sqrt},
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).

• Здравствуйте @AlexeyGolyshev, is it safe to assume that 'part of the cargo' is a known quantity? Dec 4, 2015 at 9:43
• @E.Doroskevic Yes. For example, pts[] (*{1.47545, 0.982238, 3}*) Part of cargo = 3. Dec 4, 2015 at 9:45
• 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? Dec 4, 2015 at 12:14
• @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. Dec 4, 2015 at 12:37
• @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$ ? Dec 4, 2015 at 18:55

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[] &)
]


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[] &)
];

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?