Penalize late shipments

rdbrid · April 20, 2016, 10:43pm

I am implementing a simple constraint but for some reason its not working. The constraint is to simply penalize shipments that have their deliveries exceeds a specific buffer time. Once the delivery time exceeds the allowed time for delivery, a penalty is added to the cost.

To do this, i have implemented a SoftActivityConstarint. My logic is simple, in the override getCost() function, i have done the following:

if(newAct instanceof DeliverShipment){
 double deliveryTime = prevActDepTime + prevActDepTimeroutingCosts.getTransportTime(prevAct.getLocation(),newAct.getLocation(),prevActDepTime, iFacts.getNewDriver(), iFacts.getNewVehicle());
 double orderTime= iFacts.getJob().getOrderTime();
 timeToDeliver= deliveryTime - orderTime
  if(timeToDeliver> bufferTime)
    return +10; //Penalty 
      else
    return 0;
}
`return 0;`

Also, i have used a custom objective function that applies the same criteria by iterating through all routes and all the activities in each route.

What happens is that the overall cost is updated accordingly to the new constraint while the cost for each delivery is never updated. Also, the subtracting the delivery time from the order time as mentioned above, the result sometime turns to be negative because its in time units and actual time.

If anyone could answer the following question, it would be really helpful:

Is the constraint i implemented for Penalizing Late Shipments correct or not ?
Is it the case that in the best solution, the summation of the resulted cost for each job should equal the final objective cost for that solution ?
If the above question answer is true, then why is there difference between final and the summation of individual resulted cost for each job ?
How can i deal with time in term of minutes and hours (convert current time to minutes or hours) ?

jie31best · April 21, 2016, 9:52am

Hi @rdbrid,

I’ll try to answer your first two questions:

The insertion of newAct at a particular position in a route may shift the arrival times of (some) downstream activities in the route. Thus I think you need to take that into the calculation. Btw, in one of your edits, you mistakenly removed a “+” in the calculation of variable “deliveryTime”.
I assume by “the resulted cost for each job” you mean the penalties you impose via the constraint? Besides that, there can be other activity costs (e.g. waiting cost) as well as transportation cost and fixed cost, unless in the vehicle type implementation you set all cost parameters as 0.

Best regards,
He

rdbrid · April 21, 2016, 10:39am

@jie31best,Thank you very much for taking the time to answer my questions.

Regarding the answer for the first question, how can i take the insertion of a newAct into consideration. What i understand so far, is that by implementing a SoftConstraint, i am changing the cost of the newAct which consequently impact how the activities are inserted. What am i missing ? it would be really helpful if you could elaborate more.

As for the second answer, i meant that even though that the cost changes when using the constraint, the resulted costs are the same. Note that i am not using a costMatrix and i am using a distance cost of 1.

This example explains my problem in the firs three questions. You can see from the example that the costs with or without the constraint are the same. Only the overall cost is working.

For example:
Costs without constraint:
Activity Costs
start 0
pickupShipment 1
pickupShipment 5
deliverShipment 8
pickupShipment 12
deliverShipment 13
deliverShipment 15
end 17

overall cost | 24.46060338596672

Costs with constraint:
Activity Costs
start 0
pickupShipment 1
pickupShipment 5
deliverShipment 8
pickupShipment 12
deliverShipment 13
deliverShipment 15
end 17

overall costs |60.46060338596672

Thanks.

jie31best · April 22, 2016, 4:00am

Hi @rdbrid,

Okay, I guess I will have to be careful with the terms here. Let me first try to answer your second question.

To be precise, the cost you impose via the soft constraint is not part of the activity cost (unless you defines it that way). By default, the activity cost consists of waiting cost + service cost - and by default they will be 0 as the default cost parameters associated with them are 0.

Based on the first version of your example, I assume what you show here is what SolutionPrinter prints out. If so, the costs are accumulative (transportation cost + activity cost), i.e., the cost imposed via the soft constraint is not part of it - again, unless you have defined a custom activity cost and included the cost imposed via the soft constraint as part of it, which I suppose you did not do.

I hope this clears your doubt.

Best regards,
He

jie31best · April 22, 2016, 4:35am

Now back to your first question.

By implementing a Soft Constraint, indeed you are manipulating how the activities are inserted. Let’s take SoftActivityConstraint for example, what it does is: 1) it will try to insert the newAct at each possible position in each route; 2) a cost is calculated for each trial; and 3) it will insert the newAct based on the costs and the insertion heuristic (bestInsertion, regretInsertion, etc.).

What I meant by “the insertion of newAct at a particular position in a route” is a trial. What I was saying is that the cost you calculate for each trial is not complete. Let me explain:

When you try to insert the newAct between the prevAct and the nextAct, you only calculate the delay penalty for the newAct.

However, note that, by inserting the newAct before the nextAct, the arrival time (or deliveryTime as you call it) of nextAct may be changed, as well as the arrival times of (some) downstream activities in the route - that’s what I meant by they may be “shifted”. As a result, their deliveries may also exceed the buffer time and thus need to be penalized, and the penalty needs to be part of the cost of this trial, along with what you have already calculated.

Hopefully the above answers your question.

Best regards,
He

rdbrid · April 23, 2016, 8:01pm

@jie31best, Your the “Best”.

Regarding the activity cost, what i did is i have created a custom activity costs. I have created a class that implements the interface “VehicleRoutingActivityCosts”, in the class i have used the default calculation for both service and waiting time and added my logic and returned the total cost. This is correct right ? The costs are aligned now so i am assuming that it is.

Regarding your second answer in which you suggested that i should update next activities after newAct, i just want to make sure that i understand one thing clear. Do you mean by “trial”, a route with a set of activities or just an activity ?

In either cases, i understood your explanation but i am having a problem on where and how to implement it. Could you please guide me where i can penalize shipments after penalizing the newAct. I thought about implementing a SoftRoutConstraint but would be this be right ? Wouldn’t i be penalizing activities twice ?

Your help is really appreciated as i am currently stuck.

Again, thank you very much for your time.

jie31best · April 25, 2016, 8:13am

Hi @rdbrid,

If you have defined the cost imposed by the soft constraint as part of the activity cost, then I suppose it should be counted as part of it and reflected in the costs printed by SolutionPrinter. You said “the costs are aligned” so I assume it is and the problem is solved?

By one trial, I mean the algo tries to insert one job at one particular position in one route. Such trials will be conducted many times for one job in one iteration.

For example, when it is trying to insert job D and there are two routes, one with two jobs A and B, and the other with one job C, then the algo will try to insert job D at each of the following positions (if not considering putting it in a new route): 1) between Start and job A in the first route; 2) between jobs A and B; 3) between job B and End of the first route; 4) between Start and job C in the second route; and 5) between job C and End of the second route. Each of the five is what I mean by one trial.

What SoftActivityConstraint does is that it defines a cost associated with each trial, and what SoftRoutConstraint does is that it defines the cost on a route level, that is, a cost if a particular job is inserted into a particular route, regardless the position. You can refer to Walkthrough—Constraints (the doc does not explicitly talks about SoftActivityConstraint and SoftRouteConstraint, but you can get the idea).

Now, when you are trying to figure out whether to use SoftActivityConstraint or SoftRouteConstraint, you need to ask yourself: does the position matter?

In your case, the shift of the arrival times of downstream jobs certainly depends on the position of the newAct being inserted in the route, that is, if, in the above example, the algo tries to insert job D into the first route, the three possible positions 1), 2) and 3) will have different impact on the arrival times of jobs A and B. Therefore, you should calculate such penalties at the activity level, i.e., in SoftActivityConstraint.

What you need to do is that, after calculating the arrival time of the newAct and its associated penalty (what you have already done), you need to loop over all the downstream jobs starting from the nextAct, and calculate the new arrival time for each of them and its associated penalty. You can exit the loop early if the arrival time of a job does not change - it means the arrival time of any further downstream job won’t change either.

Best regards,
He

rdbrid · April 25, 2016, 8:29am

@jie31best, thanks for your time.

Based on your explanation, i will do the following (I will write the whole solution):

I will implement a SoftConstraint interface.
I will calculate the penalty for the newAct.
I will loop the rest of the activities and update their arrivalTime & endTime and if an activity is a delivery, then i will calculate the penalty for it and add it to the newAct penalty.
After that, i will return the total penalties cost.

Now that is what i am going to do. But i have some questions:

Is returning a total cost correct or not and if not, how am i going to set penalties costs of the other activiteis ?
I used the iFacts.getRoute().getActivities() and iFacts.getRoute().getTourActivities().getActivities() and they were both empty. I also tried using iFacts.getAssocitedActivites() returns only pickup and delivery activities of the current activity. How can i get a list of all activities ?

jie31best · April 25, 2016, 9:53am

Hi @rdbrid,

The penalties on the downstream jobs is part of the cost you impose on the newAct, because those penalties are resulted from the insertion of the newAct at that particular position. Thus, it is correct to return the “total cost”.

Try iFacts.getRoute().getActivities() to get the list of all the activities in the route.

You can refer to this post on stackoverflow and this discussion on the old mailing list for earlier discussions on the same topic.

Best regards,
He

rdbrid · April 26, 2016, 10:39am

@jie31best, i am really sorry to bother you again, but i am really stuck. I am really trying. Thanks for you time.

It seems that there is something wrong with my implementation. I have been trying and trying but something is not right.

My distanceCost and timeCost both have a value of 1. When i run my work without any penalties, i get the following results:

After that i set a penalty on job 4 with a value of 10, the results changes to this:

First, you can see that the total cost is not aligned with the total costs for each route (19 + 15 != 44).
Second, the end time in the first route is penalized, while in my code i have ignored penalizing it.
Third, the pickup arrival time for job 3 is more than its delivery arrival.
Fourth, in the second route, the arrival of the endtime is completely wrong.

I also tried setting penalty on job1 and job4 each with an amount of 4 and 10 respectively. I got the following results:

First, you can see that the arrival time for job3 is 23 and then its delivery is 22, i am not sure how could this happen.
Second, the penalization of job4 is not correct.
Third, the end time for the first route is not correct also.

I am really not sure where did my implementation went wrong.

I have implemented a SoftActivtyConstraint, here is my code:

  public double getCosts(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct,TourActivity nextAct,double prevActDepTime) {
	
	// Get and check job order time
	double orderTime = iFacts.getJob().getOrderTime();
	if (orderTime == 0) {
		return 0;
	}
	
	
	double totalCost = 0;
	if (newAct instanceof DeliverShipment) {
		double arrTimeAtNewAct = prevActDepTime + routingCosts.getTransportTime(prevAct.getLocation(),
				newAct.getLocation(), prevActDepTime, iFacts.getNewDriver(), iFacts.getNewVehicle());
		double endTimeAtNewAct = Math.max(arrTimeAtNewAct, newAct.getTheoreticalEarliestOperationStartTime())
				+ newAct.getOperationTime();

		newAct.setArrTime(arrTimeAtNewAct);
		newAct.setEndTime(endTimeAtNewAct);

		totalCost = rewardAndPenatlies(newAct, arrTimeAtNewAct);

		// Update arrival times & penalties for downstream activities
		boolean start = false;
		for (TourActivity tourActivity : iFacts.getRoute().getActivities()) {
            if (!start && !tourActivity.equals(nextAct))
                continue;
            start = true;
				
			// Memorize values
			prevAct = newAct;
			newAct = tourActivity;
			prevActDepTime = endTimeAtNewAct;

			// Get arrival & end time
			arrTimeAtNewAct = prevActDepTime + routingCosts.getTransportTime(prevAct.getLocation(),newAct.getLocation(), prevActDepTime, iFacts.getNewDriver(), iFacts.getNewVehicle());
			endTimeAtNewAct = Math.max(arrTimeAtNewAct, newAct.getTheoreticalEarliestOperationStartTime())+ newAct.getOperationTime();

			// Set new calculated times
			newAct.setArrTime(arrTimeAtNewAct);
			newAct.setEndTime(endTimeAtNewAct);

			// Set cost
			if (tourActivity instanceof DeliverShipment)
				totalCost += rewardAndPenatlies(tourActivity, arrTimeAtNewAct);
		}		
	}
	
	//Check end activity
	if(nextAct instanceof End){
		double arrTimeAtNewAct = prevActDepTime + routingCosts.getTransportTime(prevAct.getLocation(),
				newAct.getLocation(), prevActDepTime, iFacts.getNewDriver(), iFacts.getNewVehicle());
	    double endTimeAtNewAct = Math.max(arrTimeAtNewAct, newAct.getTheoreticalEarliestOperationStartTime())
				+ newAct.getOperationTime();
		
		double arrTimeAtNextAct = endTimeAtNewAct + routingCosts.getTransportTime(newAct.getLocation(),
				nextAct.getLocation(), endTimeAtNewAct, iFacts.getNewDriver(), iFacts.getNewVehicle());
		double endTimeAtNextAct = Math.max(endTimeAtNewAct, nextAct.getTheoreticalEarliestOperationStartTime())
				+ nextAct.getOperationTime();

		nextAct.setArrTime(arrTimeAtNextAct);
		nextAct.setEndTime(endTimeAtNextAct);
	}
	
	return totalCost;

}

public static double rewardAndPenatlies(TourActivity tourActivity, double arrivalTime) {
	if (tourActivity instanceof DeliverShipment) {
		// If order time is not used
		AbstractJob job = (AbstractJob) ((DeliverShipment) tourActivity).getJob();

		double allowedOrderTime = job.getAllowedOrderTime();
		double orderTime = job.getOrderTime();
		if (orderTime == 0 || allowedOrderTime == 0) {
			return 0;
		}

		// Get delivery duration from order time
		double deliveryOrderTime = Math.max(0, arrivalTime - orderTime);

		// Check if delivery duration time exceeds the allowed time
		if (deliveryOrderTime <= allowedOrderTime)
			return 0; // Reward
		else
			return job.getPenaltyOrderTime(); // Penalty
	}
	return 0;
}`

Also i have implemented an ActivtyCost, here is my code:

	public double getActivityCost(TourActivity tourAct, double arrivalTime, Driver driver, Vehicle vehicle) {
		if (arrivalTime == Time.TOURSTART || arrivalTime == Time.UNDEFINED) {
			return 0;
		}

		double waiting = vehicle.getType().getVehicleCostParams().perWaitingTimeUnit
				* Math.max(0., tourAct.getTheoreticalEarliestOperationStartTime() - arrivalTime);
		double servicing = vehicle.getType().getVehicleCostParams().perServiceTimeUnit
				* getActivityDuration(tourAct, arrivalTime, driver, vehicle);

		// Custom constraints
		// OrderTime
		double orderTimePenalty;
		if(tourAct instanceof End)
			orderTimePenalty = 0;
		else
			orderTimePenalty = OrderTimeConstraint.rewardAndPenatlies(tourAct, arrivalTime);

		return waiting + servicing + orderTimePenalty;
	}

Finally the ObjectiveFunction, here is my code:

		SolutionCostCalculator costCalculator = new SolutionCostCalculator() {	
			@Override
			public double getCosts(VehicleRoutingProblemSolution solution) {
				double costs = 0.;
				for(VehicleRoute route : solution.getRoutes()){
					costs+=route.getVehicle().getType().getVehicleCostParams().fix;
					costs+=stateManager.getRouteState(route, InternalStates.COSTS, Double.class);
					
					for(TourActivity tourActivity : route.getActivities())
						costs+=OrderTimeConstraint.rewardAndPenatlies(tourActivity, tourActivity.getArrTime());
				}
				return costs;
			}
		};

Thank you again and sorry for the trouble.

braktar · April 26, 2016, 2:08pm

Hello,

The use of setArrTime or setEndTime is in cause here. A constraint only test a permutation and don’t ensure that a tested combination will be effectively inserted. You can’t set times with a constraint, you only give a cost. Times are updated by some others mechanisms.

rdbrid · April 26, 2016, 4:05pm

@braktar, thanks for you help.

Can you please tell me or refer me on how to update the arrival & end time for the newAct and other activities (downstream) after the newAct ?

Thanks.

jie31best · April 27, 2016, 3:06am

Hi @rdbrid,

@braktar is right that you should not use .setArrTime() and .setEndTime() in your constraint. We had a related discussion earlier in this post.

I think you have calculated the arrival time and end time of the activities correcly by arrTimeAtNewAct and endTimeAtNewAct. You just don’t need to call .setArrTime() and .setEndTime() to set new calculated times.

Best regards,
He

jie31best · April 27, 2016, 3:22am

btw, I think the calculation of arrTimeAtNewAct and endTimeAtNewAct and the loop over the downstream activities should be done regardless the type of the activity, i.e., they should not be inside if (newAct instanceof DeliverShipment) {}.

In other words, only the calculation of the penalty (totalCost += rewardAndPenatlies(newAct, arrTimeAtNewAct); ) should be inside the if clause.

Best regards,
He

rdbrid · May 12, 2016, 6:20am

Hi @jie31best, @braktar,

Based on the discussion that you have referenced earlier, the shifting of the activities have to be done at the “ActivityTimeTracker” class. This class contains three methods, begin, visit and finish.

My questions are:

On what method should i update the shifting of activities ?
I noticed that in all the three methods, the cost is not part of the time calculation. What role does the constraint plays in calculating the time. I mean i could penalize a shipment and calculate the extra, but then what. How does this effect the arrival time since they are already calculated there.

If you could put a simple example illustrating the concept, that would be great.

Thanks.