Nearest stop first!!!

[nassery318]

Thanks in advance,

Is there a posibility of designating/forcing the nearest location as the first stop rather than the farthest as the first (this happens in some cases)?

This surely defeats the purpose of optimal route and could possibiliy increase time and distance traveled. One potential solution would be reversing the sequence of the route. I was wondering if there is a constraint that can do this without the need for post processing?

[jcoupey]

Not out of the box but you could achieve this with additional timing constraints. If the job you want to happen first has a very tight time window, then the only valid option would be to put it first.

Of course you'll end up with a more constrained problem with a potentially worse solution.

[saurabh119]

Hi,

I am facing a similar issue. Sometimes stops are visited on the way back (after making U-turn) on the street. The duration of the route is exact same if stops are visited on the way forward when compared to when they are visited on the way back.

Currently there are 3 optimization parameters: Priority, Duration and Least Vehicle used. Can a 4th parameter be introduced so that nearest stops are visited first?

Thanks in advance.

[jcoupey]

Currently there are 3 optimization parameters: Priority, Duration and Least Vehicle used

This is something that is evaluated at solution level, while the notion of "nearest stop" as you describe it is only related to some previous job in a given route. I don't really see how you'd translate that into a solution-level metric that would favor another option?

[saurabh119]

Maybe after the best solution is calculated, then another step of local search can be introduced for each route separately which will check for nearest stop. Minimizing the running total cost/duration in the route.steps array is the objective. Thoughts?

[jcoupey]

We already try to minimize the total travel time, so the question is how to discriminate solutions if as you point out "the duration of the route is exact same if stops are visited on the way forward when compared to when they are visited on the way back".

I feel that if we want to dig further into this, we should start on real examples, which we lack in this ticket: can you share reproducible examples where the solution ordering is not the one that you'd expect, and explain why?

[K-Leon]

From my point of view a great optimization goal could be the summed delivery time.
This means:
Arrival Time Stop a + Arrival Time Stop b + Arrival Time Stop c.

If the sum of the arrival times is minimal, the deliveries will happen asap and the driver won‘t drive past them just to deliver them on the way back.

[jcoupey]

Not sure the sum of arrival times would discriminate the situation described above: if doing ...->A->B->C->... after a U-turn at B has the exact same travel time than ...->A->C->B->... because you stop at C first and not on the way back, then the gain on arrival at C will be compensated by the delay at B so the sum would also be identical.

We can probably discuss this endlessly in theory, this is why I suggested we focus on a couple examples from actual instances.

[saurabh119]

The attached example is similar to the one @K-Leon mentioned. The expected order is Start -> Stop 1 -> Stop 2 -> Stop 3 -> End. The deliveries of all the 3 stops will complete in 20 seconds if delivered in this order. Now it is taking 37 seconds to complete. The total travel time for the vehicle is 40 seconds in both cases though.

request.txt
response.txt
matrix from OSRM.txt

[jcoupey]

@saurabh119 thanks for sharing an actual example. In this case, we probably have both solutions/orderings at hand internally so it would actually be possible to discriminate the "right" solution by adding e.g. the solution completion time (or sum of arrivals as suggested above) here:

vroom/src/structures/vroom/solution_state.h

Lines 23 to 50 in 18c4290

	struct SolutionIndicators {
	Priority priority_sum;
	unsigned unassigned;
	Cost cost;
	unsigned used_vehicles;
	friend bool operator<(const SolutionIndicators& lhs,
	const SolutionIndicators& rhs) {
	if (lhs.priority_sum > rhs.priority_sum) {
	return true;
	}
	if (lhs.priority_sum == rhs.priority_sum) {
	if (lhs.unassigned < rhs.unassigned) {
	return true;
	}
	if (lhs.unassigned == rhs.unassigned) {
	if (lhs.cost < rhs.cost) {
	return true;
	}
	if (lhs.cost == rhs.cost and lhs.used_vehicles < rhs.used_vehicles) {
	return true;
	}
	}
	}
	return false;
	}
	};

This change would only adjust which solution is picked in the end across different searches, but would not impact the actual optimization objective (including something related to actual arrival times in the objective is not an option for complexity reasons).
The problem I see with this is that it may work on a simple situation such as the above example but would probably not be enough for situations with more complex setups where a small reordering could happen within a longer route.

Do you have any such example at hand?

[saurabh119]

Currently I do not have any such large example. I think an example can be generated using a symmetric matrix or a symmetric subset in a matrix (for small reordering).

[K-Leon]

I think the most important part is having solutions a user can reason about easily. „Fixing“ the simple case will help already a lot. Anyways I’ll try to look for more complex examples.

[jcoupey]

Agree that "fixing" weird situations is always interesting, even if only in simple settings.

it would actually be possible to discriminate the "right" solution by adding e.g. the solution completion time (or sum of arrivals as suggested above)

On second thoughts, this may not be as straightforward than I first made it sound. In the above example, the completion time is the same (40) for both orderings. And as I mentioned later in my previous comment, we don't have direct access to arrival times for intermediate steps, only margins (earliest and latest dates). Probably possible to use the earliest date for last task in the route to get the same effect though.

[saurabh119]

Here is another example with 16 jobs. The expected order is A -> B -> C -> D -> E -> F -> G -> H.... The calculated order is A -> G -> F -> E -> D -> C -> B -> H.... The arrival time at H is 118 in both cases.

request.txt
response.txt

[AymanElarian]

any update for this ? it's really important to prioritize nearest first

[zahert]

Any updates here, on prioritizing nearest job first ?

[jcoupey]

Nope, no update.

it's really important to prioritize nearest first

I'd say that is highly dependent on your standpoint and use-case. The roadmap is built with our clients and partners so we obviously prioritize what is important from our/their own point of view.

Of course you can always become a client (e.g. by using our commercial API) in order to have more impact on the roadmap. ;-)