time-dependent VRP?

834 views
Skip to first unread message

mapolonio

unread,
Jun 16, 2015, 8:23:34 AM6/16/15
to jsprit-ma...@googlegroups.com
Hi, in the home page of the project it is mentioned time-dependent VRP as one of the features jsprit can solve, but I can't find any example or documentation about it. Am I missing something?

I'm currently working on a start up and we need to solve this problem.

Any help?

Stefan Schröder

unread,
Jun 22, 2015, 3:24:59 PM6/22/15
to jsprit-ma...@googlegroups.com, mapo...@ug.uchile.cl
You might get reasonable results when implementing your own VehicleRoutingTransportCosts like I did when solving Figliozzi's tdvrp benchmark. Here you can see how I implemented the according time-dependent vehicle routing transport costs. As you can see, one parameter of the methods is departure time, thus you can make the costs dependent on departure time.

mapolonio

unread,
Jun 22, 2015, 3:27:57 PM6/22/15
to jsprit-ma...@googlegroups.com, mapo...@ug.uchile.cl
Thanks, I'll take a look.

mapolonio

unread,
Jun 23, 2015, 3:20:23 PM6/23/15
to jsprit-ma...@googlegroups.com, mapo...@ug.uchile.cl
I see how this is useful to set the costs depending on time, but I'm missing how to use this to solve a problem. Do you have an example where you use this or other custom VehicleRoutingTransportCosts?

I'm lost in how to setup the problem. 


El lunes, 22 de junio de 2015, 16:24:59 (UTC-3), Stefan Schröder escribió:

Stefan Schroeder

unread,
Jun 23, 2015, 4:18:55 PM6/23/15
to jsprit-ma...@googlegroups.com
Implement the time-dependent vehicle routing costs and set it when building the vrp problem with the vrp builder. And then you can proceed as illustrated in the many examples.



Am 23/06/15 um 21:20 schrieb mapolonio:
--
You received this message because you are subscribed to the Google Groups "jsprit-mailing-list" group.
To unsubscribe from this group and stop receiving emails from it, send an email to jsprit-mailing-...@googlegroups.com.
To post to this group, send email to jsprit-ma...@googlegroups.com.
Visit this group at http://groups.google.com/group/jsprit-mailing-list.
For more options, visit https://groups.google.com/d/optout.

in...@opendoorlogistics.com

unread,
Jun 26, 2015, 5:34:14 AM6/26/15
to jsprit-ma...@googlegroups.com
Hi,

I've been looking at the time-dependent code and I want to check my understanding of something. If you have time-dependent travel costs and times, I believe the costs for them are only calculated correctly in the insertion if the ActivityInsertionCostsCalculator used in the ServiceInsertionCalculator is a RouteLevelActivityInsertionCostsEstimator, which is controlled by a switch somewhere and turned off by default? This calculates the effect of the insertion on not just the local (i.e. next activity), but all later activities in the route (hence its route level). Is this correct? Also, how do travel-time dependent times work with time windows?

thanks

Phil

Philip Welch
Open Door Logistics Limited
Specialists in open source solutions for transport logistics.

Skype: opendoorlogistics



---- On Tue, 23 Jun 2015 21:18:53 +0100 Stefan Schroeder<jsprit.vehi...@gmail.com> wrote ----
Implement the time-dependent vehicle routing costs and set it when building the vrp problem with the vrp builder. And then you can proceed as illustrated in the many examples.



Am 23/06/15 um 21:20 schrieb mapolonio:
I see how this is useful to set the costs depending on time, but I'm missing how to use this to solve a problem. Do you have an example where you use this or other custom VehicleRoutingTransportCosts?

I'm lost in how to setup the problem. 

El lunes, 22 de junio de 2015, 16:24:59 (UTC-3), Stefan Schröder escribió:
You might get reasonable results when implementing your own VehicleRoutingTransportCosts like I did when solving Figliozzi's tdvrp benchmark. Here you can see how I implemented the according time-dependent vehicle routing transport costs. As you can see, one parameter of the methods is departure time, thus you can make the costs dependent on departure time.

Am Dienstag, 16. Juni 2015 14:23:34 UTC+2 schrieb mapolonio:
Hi, in the home page of the project it is mentioned time-dependent VRP as one of the features jsprit can solve, but I can't find any example or documentation about it. Am I missing something?

I'm currently working on a start up and we need to solve this problem.

Any help?
--
You received this message because you are subscribed to the Google Groups "jsprit-mailing-list" group.
To unsubscribe from this group and stop receiving emails from it, send an email to jsprit-mailing-...@googlegroups.com.
To post to this group, send email to jsprit-ma...@googlegroups.com.
Visit this group at http://groups.google.com/group/jsprit-mailing-list.
For more options, visit https://groups.google.com/d/optout.

Stefan Schroeder

unread,
Jun 26, 2015, 6:07:20 AM6/26/15
to jsprit-ma...@googlegroups.com
Theoretically, you are right. You need to look at route level, since when dealing with time-dependent costs the insertion of one customer might have an impact on the whole route (since it might shift future legs into peak traffic hours). However, my experiments with the benchmarking instances from Figliozzi show that route level estimations do not improve solution quality much compared to local level insertions. But probably you need to make these experiments for your own again.

When it comes to time-windows, if your time-dependent travel time matrix has certain properties (e.g. FIFO property, i.e. overtaking is not allowed) then you can handle hard time windows here the way you handle them in problems with static travel times. You only need to provide an implemenation of BackwardTransportTime which is here usually not equal to TransportTime; and then you can propagate latest arrival times backwards (from the end to the start of the route). And if your travel time matrix features the FIFO property then if you depart earlier from an activity than 'latest departure time' you can always be certain that you arrive at the next activity at a time smaller than 'latest arrival time'. Thus, you do not break any time windows. However, designing the travel time matrix might not be that simple, however research has proposed ways, see for example Eglese et al: A Road Timetable to aid vehicle routing and scheduling or Figliozzi: The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics.

Am 26/06/15 um 11:34 schrieb in...@opendoorlogistics.com:

Stefan Schroeder

unread,
Jun 26, 2015, 6:14:54 AM6/26/15
to jsprit-ma...@googlegroups.com
Just an addition:
With regards to
"However, my experiments with the benchmarking instances from Figliozzi show that route level estimations do not improve solution quality much compared to local level insertions."
This is not a general statement, but is relating to jsprit's algorithms and heuristics. A prerequisite here is probably that you do not only use RegretInsertion but a more random insertion approach.

Am 26/06/15 um 12:07 schrieb Stefan Schroeder:

in...@opendoorlogistics.com

unread,
Jun 26, 2015, 6:19:16 AM6/26/15
to jsprit-ma...@googlegroups.com
thanks! It may take some time for me to understand this! : )


Philip Welch
Open Door Logistics Limited
Specialists in open source solutions for transport logistics.

Skype: opendoorlogistics



---- On Fri, 26 Jun 2015 11:07:18 +0100 Stefan Schroeder <jsprit.vehi...@gmail.com> wrote ----
Theoretically, you are right. You need to look at route level, since when dealing with time-dependent costs the insertion of one customer might have an impact on the whole route (since it might shift future legs into peak traffic hours). However, my experiments with the benchmarking instances from Figliozzi show that route level estimations do not improve solution quality much compared to local level insertions. But probably you need to make these experiments for your own again.

When it comes to time-windows, if your time-dependent travel time matrix has certain properties (e.g. FIFO property, i.e. overtaking is not allowed) then you can handle hard time windows here the way you handle them in problems with static travel times. You only need to provide an implemenation of BackwardTransportTime which is here usually not equal to TransportTime; and then you can propagate latest arrival times backwards (from the end to the start of the route). And if your travel time matrix features the FIFO property then if you depart earlier from an activity than 'latest departure time' you can always be certain that you arrive at the next activity at a time smaller than 'latest arrival time'. Thus, you do not break any time windows. However, designing the travel time matrix might not be that simple, however research has proposed ways, see for example Eglese et al: A Road Timetable to aid vehicle routing and scheduling or Figliozzi: The time dependent vehicle routing problem with time windows: Benchmark problems, an efficient solution algorithm, and solution characteristics.

Am 26/06/15 um 11:34 schrieb in...@opendoorlogistics.com:
Hi,

I've been looking at the time-dependent code and I want to check my understanding of something. If you have time-dependent travel costs and times, I believe the costs for them are only calculated correctly in the insertion if the ActivityInsertionCostsCalculator used in the ServiceInsertionCalculator is a RouteLevelActivityInsertionCostsEstimator, which is controlled by a switch somewhere and turned off by default? This calculates the effect of the insertion on not just the local (i.e. next activity), but all later activities in the route (hence its route level). Is this correct? Also, how do travel-time dependent times work with time windows?

thanks

Phil

Philip Welch
Open Door Logistics Limited
Specialists in open source solutions for transport logistics.

Skype: opendoorlogistics
Reply all
Reply to author
Forward
0 new messages