Avoid early pickup hard constraint

[Zufar Muhamadeev]

Hello!

I want my vehicle avoid to visit pickups before timeWindow start. I have added HardActivityConstraint with simple method:   

    public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct,
            TourActivity nextAct, double prevActDepTime) {
        if (newAct instanceof PickupShipment) {
            double arrTimeAtNewAct = prevActDepTime
                    + routingCosts.getTransportTime(prevAct.getLocation(), newAct.getLocation(), prevActDepTime,
                            iFacts.getNewDriver(), iFacts.getNewVehicle());
            if (arrTimeAtNewAct < newAct.getTheoreticalEarliestOperationStartTime()) {
                return ConstraintsStatus.NOT_FULFILLED;
            }
        }
        return ConstraintsStatus.FULFILLED;
    }

What i whant to do here is to calculate arrive time at inserting activity and to escape inserting activity if vehicle arrive before TheoreticalEarliestOperationStartTime.

Unfortunatly this constraint doesn`t work(.

[Stefan Schroeder]

Hi,

You cannot enforce this, but what you can do is to minimize waiting times. Look at this branch. Here, waiting times can be easily incorporated into the optimization. Note that the branch is still under development. See also this.

Best
Stefan

Am 18/08/15 um 11:49 schrieb Zufar Muhamadeev:

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

[Josh Pilkington]

Hi Zufar,

Just to reinforce what Stefan has said, I think that the branch he has suggested will sort out your problems. The problem with the Master version is that it does not penalise waiting time (time costs are only considered as the driving time, and waiting time incurs no cost). This leads to lots of waiting time unless the driver is very busy.

I did hope to have "definitive" results for the tests of the alternative branch but this is very hard to test. Your mileage will go up in cases where waiting time would have been preferable under the Master version; the key question is whether this mileage goes up proportionally to the solution, or whether the penalty cost for waiting time is causing unnecessarily long trips. This is a very hard question to answer, requiring lots of planets to align. The best I can say at this point is that penalising waiting time with the same cost of driving time will lead to a logical answer, inflated waiting costs will demonstrably start to skew the answer, and waiting costs at less-than-driving-time-costs will still allow unnecessary waiting time to creep in to the route. 

Bottom line: Qualitatively – the new branch makes a lot more sense.

Regards,

Josh

[Stefan Schröder]

Hi,

The min-waiting-time feature is now in the master branch. Just look at this example to get to know how to use it. The great thing is that you only need to increase .setCostPerWaitingTime(1.) when defining your vehicle type. Then it automatically considers waiting time and tries to minimize completion time rather than transport time only. Theoretically, the trade-off between transport and waiting time is proportionally to transportCosts (i.e. costPerTransportTime and costPerDistance) and waitingCosts, so the marginal exchange rate should be costPerTransportTime / costPerWaiting (if costPerDistance = 0).

Best,
Stefan

[He Huang]

Hi,

It is great that min-waiting-time is implemented. GREAT job!

I guess one of the next steps would be optimizing the variable departure time. When I search for this topic and find that, in this post, Philip suggested: "With the departure from depot time, you could take the final solution generated from jsprit and just set the start time such that it leaves the depot at first_stop_open_time - depot_to_first_stop_travel_time" (I have not read through the codes in the playground, but does it do the same thing as Philip suggested?)

I don't think this is the correct way to do it. Consider the following example:

One depot location 0, two job locations 1 and 2, the distance between any two locations in any direction is the same and travel time is also the same 1 hour. Assume vehicle earliest departure time is 0, earliest start time is 2 and 4 for job 1 and 2, respectively. There is no end time constraint. Service time is 0.5 hour for both jobs.

There are two feasible solutions: 1) 0->1->2->0; and 2) 0->2->1->0 (assume it is closed route - actually this does not matter). Both solutions have the same travel costs so we only need to compare the waiting times. If vehicle departs depot 0 at time 0, then 0->1->2->0 will have a total waiting time of 1.5 hours (1 hour at job 1 and 0.5 hour at job 2), and 0->2->1->0 will have a total waiting time of 3 hours (at job 2 only). Thus, min-waiting-time will see 0->1->2->0 as optimal.

However, with variable departure time, for 0->1->2->0, in order to have 0 waiting time at job 1, departure time will be 1, and then the total waiting time will be 0.5 hour (at job 2 only); while for 0->2->1->0, in order to have 0 waiting time at job 2, departure time would be 3, and the total waiting time will be 0. Thus 0->2->1->0 is optimal in this case.

Hopefully I did not make any mistake here.

Please kindly let me know what you think. Thank you.

Best regards,

He

[Stefan Schröder]

Hi He,

Thanks a lot for you thoughts. I completely aggree with you. It is not just taking the final solution and setting the start time such that waiting time at the first customer is avoided. That might be a short cut, but it might yield rather bad solutions comparing to really integrate it in the insertion process.

Best
Stefan