GraphHopper.com | Forum | GitHub | Maps | Blog

Multiple Time Window Cost Matrix


#1

Hello!

I am working now quite some time with jsprit and it works very fine! Thx to @stefan and all others for implementing this great library.

During my work I got some interesting idea for planing tours:

In the practice it is usual that in the driving times between the rush hours are lower. So maybe it would be great if i would start in the morning with a service that is near the depot so the vehicle hasn´t to be long in the morning rush hour. After that the vehicle could drive to a service, that is far away but fast to arrive, because the streets are empty. Then the vehicle could work step by step to the depot again with shorter driving times.

In the algorithm I would think, that this would be good realized with the possibility to add two costmatixes in the problem. One for the faster tours between the rush hours (with given time window) and one for the rush hours.

This could look like so:

VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();

VehicleRoutingTransportCostsMatrix.Builder rushHour = VehicleRoutingTransportCostsMatrix.Builder.newInstance(true);
//Rush hour between 7 and 10 o´clock
rushHour.addTimeWindow(420, 600);
//Rush hour between 15 and 18 o´clock
rushHour.addTimeWindow(900, 1080);

vrpBuilder.addRoutingCost(rushHour.build());

VehicleRoutingTransportCostsMatrix.Builder fastHour = VehicleRoutingTransportCostsMatrix.Builder.newInstance(true);
//Rush hour between 7 and 10 o´clock
fastHour.addTimeWindow(600, 900);

vrpBuilder.addRoutingCost(fastHour.build());


Here is a exaple of the idea(sorry it was made with paint but i think you undestand what I mean :slight_smile: )

What do you think of this idea? Would this be possible and a good featue? If yes, I would make an issue for it in github.

Patrick


Time/Distance matrix calculation and How to take traffic into consideration?
#2

Hello Patrick,
Thanks for your idea. Day time dependent transport times is definitely an important issue. The great thing here is that to consider this you do not need to change jsprit’s core, but you can leverage existing interfaces. You can just implement this. Here you need to implement for example this method:

public double getTransportTime(Location from, Location to, double departureTime, Driver driver, Vehicle vehicle);

As you can see, you have access to the departureTime of your vehicle. Therefore, you can also make transport time dependent on time of day. So just put your two low-traffic and peak-traffic time matrices into your implementation of the above interface. However, you need special handling to cope with the discrete time leaps at the interface of these two transport time matrices. You need to avoid that vehicles can pass each other. In theory, this property is called FIFO property.


#3

Hi again!

Thanks, I will look forward to try this out if my work is at the point that the feature is needed. Again I have a new question, but i don´t want to make a new topic for each question :slight_smile:

I have a question about how the algorithm works with the case:
Not enough services to plan every vehicle for a full day.

In this case services and vehicles have timewindows and a servicetime.

Does the algorithm rather plan a vehicle full and let some unplaned? Or will the algorithm try to give every vehicle some “work”? Could this (/is this) somehow configurable?


#4

please create new topics for new topics :slight_smile:


#5

Hello @patrick_wisniewski19 ,

I opened a new thread with a similar question, did you implement this successfully ?
Or have you found another way to accommodate for traffic delays ?

thanks,
Karim.


#6

About this topic, I implemented something like this, but the problem is that sometimes departureTime is zero. The method that call my new matrix is “com.graphhopper.jsprit.core.algorithm.ruin.DBSCANClusterer#sample”, line 209 (1.7.2)

double dist = costs.getTransportCost(act1.getLocation(), act2.getLocation(), 0., null, r.getVehicle());

Can I change this line?

The code would look like this:

double dist = costs.getTransportCost(act1.getLocation(), act2.getLocation(), act1.getEndTime(), null, r.getVehicle());