GraphHopper.com | Forum | GitHub | Maps | Blog

How to use SoftConstraints in a distance matrix


#1

Hi everybody,

I find it really hard to implement SoftConstraints in the DistanceMatrix. I don’t even know where to start. Maybe someone can help me with starting of.

Kind regards,

Dragster1406


#2

Anyone that can help?


#3

Hi @dragster1406,

What exactly do you mean by “SoftConstraints in the DistanceMatrix”? What would you like to achieve by such SoftConstraints? Some explanation would be helpful, and examples would be better.

Best regards,
He


#4

Hi @jie31best,

Thanks for your reply.

I’m working on an project which routes get planned out of salesorders. These salesorders contain timewindows. Currently when I take the current date (e.g. 02/07/2018) some deliveries get removed from the solution because the date to lays in the past. I don’t want that these deliveries get excluded from the solution but get delivered first. So that all the deliveries get delivered but the most urgent one’s get priority.

I hope this explanation makes it a bit easier to understand.

Thanks for your help!

Kind regards,

dragster1406


#5

Ok I think I understand your problem (mostly). So you have a few deliveries whose time windows have already passed when the problem is run and so they are unassigned. What you would like to achieve is that they get assigned, and the most urgent one’s get priority - this part I’m not sure, do you mean that, when you have two deliveries whose time windows have already passed, the one whose time window passed earlier should be served earlier (if they are in the same route)?

Anyway I think there are two ways to handle the problem:

  1. Easy but not elegant:

For those deliveries who time windows have already passed, extend their time window end times to a proper value, e.g., one hour in the future. You will need to tweak this value based on your problem.

  1. Elegant but not easy:

Soft time window. Unfortunately, this is not supported in the current jsprit. There is such feature request, but it is not done. Actually there is a pull request, but it is not merged.

You can search “soft time window” on this site, and you will find a few related posts.

Btw, this is not related to distance matrix.

Best regards,
He


#6

@jie31best Thanks for your reply,

You got it right, this was the problem I was talking about. To bad it isn’t supported yet, thanks for your help.

Kind regards,

dragster1406


#7

For the people that might want to know. I have fixed this the following way:

/**
   * In this method the delivery gets created for the solver. So the solver can optimize each {@link Delivery}. The
   * servicetime is standard 1800 second -> 30 minutes. This is defined in SERVICE_TIME. When the currentdate is out of
   * the timewindow the timewindow gets set from current date till 3 days further this functions as the softconstraint
   * on the timewindow
   * 
   * @param size
   * @param order
   * @param timeWindowFromInMinutes
   * @param timeWindowToInMinutes
   * @param location
   * @param deliveryId
   * @return {@link Delivery}
   */
  private Delivery createDelivery(int size,
      ShortSalesOrder order,
      long timeWindowFromInMinutes,
      long timeWindowToInMinutes,
      String location,
      String deliveryId)
  {
    Delivery delivery;

    if (timeWindowFromInMinutes < 0)
    {
      timeWindowFromInMinutes = 0;
    }
    if (timeWindowToInMinutes < 0)
    {
      timeWindowToInMinutes = THREE_DAYS_IN_MS;
    }

    delivery = Delivery.Builder.newInstance(deliveryId).setLocation(Location.newInstance(location))
        .setTimeWindow(TimeWindow.newInstance(timeWindowFromInMinutes,
                                              timeWindowToInMinutes)).addSizeDimension(0,
                                                                                       size)
        .setServiceTime(SERVICE_TIME).build();

    return delivery;
  }

If my timeWindowFrom I pass is before current time it stays the same in my db but gets set in the solution as the current date. If the timeWindowTo is before current time it stays the same in my db but gets set in the solution 3 days further. This is done to give jsprit some room for changing the solution.