Accumulated passenger travel time as secondary objective

[Ravn]

Hi,

I am using the routing solver to solve an advanced VRP.
The domain is planning person transport and the overall goal is to minimize overall distance or time. This is well documented and does not present problems.

However a secondary objective is to minimize passenger travel time. Consider a transport job where the vehicle's depot, pickup addresses and destination are on a straight road as below:
-----VD-----D------A------B-----
VD = Vehicle Depot
D = Destination for passengers A and B
A = Pickup address for passenger A
B = Pickup address for passenger B

If I try to plan this, the planner will return the solution VD-A-B-D. This is however not satisfactory for passenger A - this passenger would rather be picked up after B so that she does have to travel unnecessarily. So a better plan would be VD-B-A-D.

So how do I get the solver to take passenger travel time (accumulated) into account?

I have read many posts in this forum and on others too - but I cannot seem to find a definite answer to the question. I apologize in advance if I have missed something.

I hope to hear from you and wish you all a pleasant weekend.

Best regards,
Ravn

[blind.lin...@gmail.com]

I'm sure I've posted on this topic before in this forum, but it has been a while.

I would recommend constraints as well as some objective goals.

In my case, there was a legal requirement that no passenger could be in a vehicle more than 45 minutes longer than a straight trip from origin to destination. We ended up changing that to the lesser of 50% more time or 45 minutes, as it seemed silly to allow 45 minutes additional time on a 5 minute trip.

Second, although I do not recall using it myself, I believe it will work to set soft constraints on all of the passenger's final values using SetCumulVarSoftUpperBound. If you set each to the direct trip distance (or travel time as your needds require), then the solver will see a penalty for time in excess of the straight line distance.

What I don't know is how much extra overhead that will add to your solver run. It all depends on how many trips you have, etc.

Hope that helps,

James

-- You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/f1925a3c-2fff-4fe9-a1e4-5515e7f41f21n%40googlegroups.com.

--

James E. Marca  
Activimetrics LLC  

[Ravn]

Hi James,

Thank you for your reply. I will try it out and get back to this forum with the results...

/Ravn

[Ravn]

Hi again,

I tried James' solution, but adding soft constraints on passengers' final values does not seem to work.

I already add a rule to the solver to constraint travel time:

for (int i = 0; i < data.PickupsDeliveries.GetLength(0); i++)
{
    long pickupIndex = manager.NodeToIndex(data.PickupsDeliveries[i][0]);
    long deliveryIndex = manager.NodeToIndex(data.PickupsDeliveries[i][1]);
        

   //state that transport time must not exceed max transport time for order.
   IntExpr dur_expr = timeDimension.CumulVar(deliveryIndex) - timeDimension.CumulVar(pickupIndex);
   solver.Add(dur_expr <=data.MaxTransportTimes[i]);

}

It seems that if I could just ask the solver to minimize dur_expr above, it would solve my problem. Is that possible?

[blind.line]

Can you just add that variable(s) using the soft constraint mechanism?

James

On Sep 5, 2024, at 05:02, Ravn <ravn...@gmail.com> wrote:

Hi again,

--

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/187a8f19-f64d-45f5-9c7c-95607cf49917n%40googlegroups.com.

[Ravn]

Hi again,

James, do you mean somethink like this (in the loop from previous post):

timeDimension.SetCumulVarSoftLowerBound(pickupIndex,3600*23, 1000); //penalty for pickups before 23:00
timeDimension.SetCumulVarSoftUpperBound(deliveryIndex, 0, 1000); //penalty for deliveries

I have tried that and it does not seem to work. I think the problem is that it is not the accumulated time that gets penalized...

[blind.line]

I’ll try to take a closer look at the detsiks of your old posts today…I have some time this afternoon 

James

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/5be3da88-051b-4d4e-af4f-1fc18cbc8ff6n%40googlegroups.com.

[blind.line]

Hi Ravn

I am working on a short blog post. I should be done with part 1 today. 

James

On Sep 10, 2024, at 09:53, blind.line <blind.lin...@gmail.com> wrote:

I’ll try to take a closer look at the detsiks of your old posts today…I have some time this afternoon 

[Joseph Mintz]

Is it possible to minimize capacity * transit time?
In this case, capacity ranges from 0 to 2.

Old solution:
0 VD -> A
1 A -> B
2 B -> D

Better solution:
0 VD -> B
1 B -> A
2 A -> D   ... this is less because 2*(timeAD) < 2*(timeBD)

[Ravn]

Hi James

I'm glad you are taking the time to help me. I am looking forward to read your post!

[Mizux Seiha]

unless using AddDimensionDependentDimension with capacity/passenger_load, I can't see a good way to do it...
if passenger is a small range [0;10] you "just" multiply your transit matrix NxN by a factor 10 so it may be doable but still...

[Ravn]

Hi again,

joeb... is pinning the problem precisely.

What I would like to do is have a transit callback returning:

UC(fromNode)*TimeMatrix(fromNode,toNode), 

where UC(fromNode) is the current load of vehicle at the fromNode = the Cumulvar of a Capacity dimension.
However, if I understand correctly, you cannot use CumulVar of other dimensions in a transit callback (the variable is not bound anyway, and besides transit callbacks can be cached).

I have read that it is perhaps possible to use the slack function (ref. https://groups.google.com/g/or-tools-discuss/c/0QCvAEP8n8w), but I really need a working example.

As minimizing accumulated passenger travel time is quite essential to passenger transport planning, I would suspect it to be possible one way or another.

/Ravn

[Ravn]

Hi Mizux, 

Thanks for the reply. I'm using C# as implementation language, and I do not think that AddDimensionDependentDimension is accessible here?
Besides, we could be talking several hundred passengers, which probably makes it infeasible...

/Ravn

[Laurent Perron]

Do not use this code. It does not work.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/9722ecbc-67d5-48e8-8e29-1be6f82832a2n%40googlegroups.com.

[Ravn]

Hi Laurent,

Thanks. I will wait and see what is suggested here, before doing anything...

/Ravn

[Mizux Seiha]

SetPathEnergyCostOfVehicle() could do the trick (just replace force by passenger) but I've never use it yet...
https://github.com/google/or-tools/blob/ed94162b910fa58896db99191378d3b71a5313af/ortools/constraint_solver/routing.h#L1202-L1210

[J. E. Marca]

I got side-tracked, but I've put together a draft post here https://activimetrics.com/blog/ortools/passenger_centric_vrp/

I tried to keep it as simple as possible and start from a basic VRP example in the OR-Tools code base, and then gradually expand to something that gets the right results.

I need to try out and possibly add in the SetPathEnergyCostOfVehicle() call, as I've never seen that before.

[Ravn]

Hi Mizux and James,

James: Thank you for your blog, which certainly takes one through the process of nearly achieving the goal. I do not doubt that it works, and it has given me pointers to why my previous attempts did not work.

Mizux: The SetPathEnergyCostOfVehicle() function does exactly what I want! I made a passenger dimension and supplied the function with that and the time dimension. Works brilliantly!

It strikes me as odd, however, that I have to raise the solutionlimit >1 in order to make it work - but that is probably because "solutionlimit" means "initial solution limit". 

Thanks to all for helping me out!

/Ravn