Soft time windows

[He Huang]

Hi,

I understand I am not the first one to ask about soft time windows (for example, here and here) and I will not be the last one. I am happy to see it is labeled as feature here. I understand it will take a while so I guess I'd better implement it myself first. Of course, if it has already been implemented, it would be even better!

In the posts I listed earlier, Stephan suggested that, when implementing the softActivityConstraint, we should "keep in mind that the insertion of a new activity does not only have a local impact, i.e. on the two neighboring activities, but it can have an impact on the whole route since it shifts all subsequent activities". I understand that the insertion may 1) increase the time amount of being late for some subsequent activities, and 2) reduce the time amount of being early for some subsequent activities. I suppose this would be very similar to the min-waiting-time case, in which the insertion of a new activity will potentially reduce the waiting time for subsequent activities. 

I understand that min-waiting-time has already been implemented, so, before I start, any suggestions or any classes/functions in the min-waiting-time implementation that I should look at? 

Thank you very much.

Best regards,

He

[He Huang]

Hi,

In the min-waiting-time case, LocalActivityInsertionCostsCalculator, the impact of the insertion of the new activity on the whole route (subsequent activities) is calculated as waitingTime_savings. In this way, the calculation of the global impact does not require visiting each of the subsequent activities and thus it saves computational time.

Two reasons for it to work: 1) the penalty on the waiting time is linear, i.e., waitingTime_savings = waitingTime_savings_timeUnit * iFacts.getRoute().getVehicle().getType().getVehicleCostParams().perWaitingTimeUnit; 2) the nature of waiting time, as Stefan stated in this post: "the end time delay can be used to reduce waiting time somewhere in the route. However, this reduction cannot be bigger than the existing futureWaiting time, i.e. the sum of waiting times at subsequent customers", i.e., waitingTime_savings_timeUnit = Math.min(futureWaiting, endTimeDelay_nextAct).

When I try to follow the same logic for the soft time windows constraint, I would need three states similar to FUTURE_WAITING: 1) totalActivityEarly: sum of times of being early at subsequent activities (i.e., the same as FUTURE_WAITING); 2) totalActivityLate: sum of times of being late at subsequent activities; and 3) routeLate: time of being late for vehicle end time.

The time unit savings in totalActivityEarly and increases in routeLate as a result of the insertion of the new activity can be calculated in the same way as for waiting time: Math.min(totalActivityEarly, endTimeDelay_nextAct) for the former, and Math.max(0, endTimeDelay_nextAct - totalActivityEarly) for the latter.

However, for the time unit increases in totalActivityLate, it is more complicated: it requires visiting each of the subsequent activities. For example, suppose there are subsequent activities 1, 2, 3, ..., N, totalActivityEarly = 15 minutes, totalActivityLate = 0, routeLate = 0 and endTimeDelay_nextAct = 10 minutes. For the sake of simplification, assume operation time is 0 for all activities. Then consider two scenarios: 1) before insertion, the vehicle is early only for activity 1 and arrives exactly on time for all others. So after the insertion, the 10 minute endTimeDelay_nextAct is absorbed by the times of being early at activity 1 and it will not affect the arrival time at any of other subsequent activities, thus totalActivityEarly = 5 minutes, totalActivityLate = 0, routeLate = 0. 2) before insertion, the vehicle is early only for activity N and arrives exactly on time for all others. So after the insertion, the 10 minute endTimeDelay_nextAct will cause the vehicle being late for all subsequent activities except activity N, thus totalActivityEarly = 5 minutes, totalActivityLate = 10 * (N - 1) minutes, routeLate = 0.

In summary, the same method cannot be applied to the soft time windows case. The calculation of the time unit increases in totalActivityLate requires visiting each of the subsequent activities, which will increase the computational time significantly. Is there a way to get around this?

Moreover, I would like to use a non-linear penalty function for the time window violation, because in the case of multiple activities being late, I would like the one with an earlier end time to be visited first. In this case, even for totalActivityEarly and routeLate, it requires visiting each of the subsequent activities as the cost function is not additive.

Hopefully the above is understandable.

Please let me know what you think. Thanks.

Best regards,

He

[Stefan Schroeder]

Hi He,

This really helps implementing soft constraints. Thank you so much for your analysis. I really appreciate it. Once I need to implement it and/or integrate it into jsprit, I would like to discuss this further with you. However, currently I do not have the time to do it.

Best,
Stefan

Am 09/10/15 um 10:08 schrieb He Huang:

--
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.

[He Huang]

Hi Stefan,

Please kindly find attached my implementation of the soft time windows. It is implemented as a soft constraint. States similar to FUTURE_WAITING are not used. The calculation of job insertion cost goes through every individual subsequent job in the route, so the computational time increases significantly (compared with hard time windows). A non-linear penalty function is used: f(x) = 1000 x^2, where x is the violation for each individual time window.

Only end time constraints are relaxed in the implementation. Vehicles still depart at their corresponding start times, and services at the jobs can only start at or after their corresponding start times, i.e., variable vehicle departure time is not implemented or optimized, and early start of services is not allowed. If a vehicle arrives at a job earlier than the start time, it waits, as in the hard time window case. This type of soft time window constraint is categorized as Type I in Fu et al. (2008).

Tests have been conducted both on a small illustrative example and on Solomon benchmark instances.

The former is adapted from this post. The locations of the jobs are changed slightly. Two variable are added: vehicleStartTime t and serviceDuration s. The results are as expected: when those two variables satisfy this conidtion, the vehicle will visit "service1" first and then "service2"; otherwise the opposite.

The results on Solomon benchmark instances are not as good. Two algorithms are tested: the Jsprit algorithm (algoType = 1 in the code) and the extensive search algorithm (algoType = 2). For each of them, both hard time windows (timeWindowType = 0 or 1) and soft time windows (timeWindowType = 5) are tested. The problem is that, for the same instance and algorithm, the result returned by the soft time windows case is not always no worse than that returned by the hard time windows case. This is not as expected. One possible reason is that the algorithm is run only once for each instance. However, this is doubtful, because with v1.6.1, the “results are now reproducible since every time the algorithm runs, a unique random number generator (always starting with a predefined seed) is invoked”, as stated here.

Could you please kindly take a look at my implementation and advise? Thank you very much.

Best regards,

He

[Stefan Schröder]

Hello He,

Great! Thanks a lot. I am going to take a look at your implementation asap.

Best,
Stefan

[He Huang]

Oh great! I look forward to your comments! :-)

Best regards,

He