ASAP vs Less time possible (Feature)

[agausachs]

The cost of the total time of different routes, it's the sum of the times per cost per time. It would be great if you could choose to do the services as fast as possible or in the less time possible. Let me explain, if I have 2 vehicles, maybe the algorithm finds a fast solution that it's only one route of 30 minutes, leaving the other vehicle without services to do. So, my services will be solved in 30 minutes. But if I want to solve the services in the less time possible, maybe it's a better solution 2 routes of 20 minutes because even the time will be greater (30 vs 40), in 20 minutes everything will be solved.

[jsprit]

we probably require am objective function than min max tp-times and an apropriate adaptation of the insertion heuristic, i.e. a soft-constraint that somehow penalyzes a shift of max route.

[pierredavidbelanger]

+1 for this one!

Is there a way to do it right now with the master branch code, using a custom made SoftConstraint ? I guess not, since we need to adapt de insertion heuristic.

[jsprit]

Give me a few days, then you have full and easy control over the overall objective function and over what drives the insertion heuristic to min this function (actually you already have but it is kind of inconvenient). Then we can start experimenting with custom objective functions and soft contraints to min max transport times.

@pierredavidbelanger I pointed agausachs to your cluster method. Do you have a brief doc of how to use it?

[jsprit]

With https://github.com/jsprit/jsprit/blob/master/jsprit-core/src/main/java/jsprit/core/algorithm/VehicleRoutingAlgorithmBuilder.java you can now set your own objective function as well as constraints to optimize whatever you want to optimize. You control the overall meta-heuristic with the objective function and with the way the insertion-heuristic inserts your job-(activities). I implemented and documented a simple example that shows you the way I minimized max transport times (see https://github.com/jsprit/playground/blob/master/src/abe/AbeProblemMinMax.java). You can run it with the latest SNAPSHOT (1.2.1). It works surprisingly well. Basically, my objective function is min max routes' transport times. Addtionally, I specified a soft constraint such that the insertion of a jobActivity which results in a shift of that maximum will be penalyzed. If you additionally want to keep the overall time low, you can put it into the objective function (as sort of secondary goal) as well. Also my other artificial test cases were quite satisfying. But still, it needs to be further tested to finally evaluate the quality of this approach. But it seems to be really promising.

If you find state and constraint definition awkward, let me know and we can think simplifying it further.

I will be writing further example and putting it into the example folder.

I am quite curious about your experience. Let me know.

[agausachs]

Sounds great! I will tryit and comment about it. Thanks!

[agausachs]

Hi Stefan,

I have tried your approach and it's working well. I tested with different scaling factors and the results are good. Now I'm trying to also implement the distance and the fixed cost on the solution calculation because not only time is important in my case, because even the time values on the solution could be very good, if distance isn't affordable a new solution should be calculated. I'm still looking on your source code to see which is the default formula for calculating the default costs and try to adapt it.

I found that the algorithm file you used on the example achieves better results but it's slower than the one you used initially on the Discapacitated People Transport example. I think it's the use of schrimpfAcceptance vs acceptNewRemoveWorst. For the same vehicles and services, the old algorithm takes less than 5 seconds, and the new one about 2 minutes but with better results.

About if the constraint definition is awkward, well, it's less intuitive than the super easy costPerDistance or costPerTime, but after a while of study, it's affordable. Although it would be great if there was a costPerMaxTime parameter to use it as you use the scaling factor on the example, favoring the maximum time over the total time. ;-)

Thank you again!

[agausachs]

Update: After modifying my code, I have a little more information. Also my "5 seconds vs 2 minutes" sentence was very exaggerated (a problem on my code). As I said, there's a difference on the speed of the results but it seems it's not the different algorithm file, that only adds a couple of seconds. It seems it's the penalyzeShiftOfMaxTransportTime constraint what adds 5-10 seconds more to the result calculation, depending on the number of vehicles and services. What it's true, is that with this objectiveFunction and the constraints in the example, is slower than without (only capacity and tw constraints), which I understand it's normal.

[jsprit]

Great, thanks a lot for your effort. Sounds good that the max-time concept works reasonably :). If you want to add additonal cost components to the objective function you need to have two things in mind: First, you need to scale the components appropiately. Thus you need to somehow normalize them. One way is to find a generalized cost function that maps your components to cost values. Second, you need to account for additional cost components in your insertion heuristic. If your insertion heuristic always prefers say the employment of red vehicles, you hardly end up with a solution that minimzes fixed, variables and max-time-costs. Thus, if you hv a heterogeneous fleet with diff fixed costs, add the FixCostCalculator (Softconstraint) to the insertion heuristic. You are right, computational time is not only dependent on the problem, the number of iterations and the acceptance func, but also on additional constraints, since they need to be checked when inserting a new job. ActivityLevelConstraints are harder than RouteLevelConstraints. Thus the avoidance of needless ActivityLevelConstraints does have significant impact on the overall performance. You can avoid it for example by clustering jobs first and by formulating an appropriate HardRouteLevelConstraint. When it comes to performance measures I just published analysis.toolbox.ComputationalLaboratory.java with which you can make sensitivity studies concurrently. You can use it to elaborate on an algorithm that fits your needs by testing and comparing different algorithms on the same problem or one algorithm on different problems. I am sending you a message once I prepared an example of hoe to use it. Thank you again for your efforts.

[jsprit]

Update: @ Although it would be great if there was a costPerMaxTime parameter to use it as you use the scaling factor on the example, favoring the maximum time over the total time.

Yes. It would certainly be :). It is always a fine line between making things simple and general. I thought costPerTime and Distane is important in almost all problems whereas costPerShiftOfMaxTime might be too specific? I ll be thinking about it. But generally I think it is more important to simplify the way of customizing the objective function.

[agausachs]

It would be great on the definition of the problem if we could pass a factor priorizing maxtime over totaltime, but yes, this parameter would be too specific for a small group of cases (as mine), so don't worry. But If you end up adding it, it would be welcome. To achieve it manually, I'm testing using a custom formula for the SolutionCalculator:

return totalCostsFromDistance + ((maxTransportTime + (scalingParameter * sumTransportTime)) * globalTimeCostFactor);

Instead of adding a costPerTime on the vehicleType, I use it a global TimeCostFactor. My goal it's to find the best solutions playing with these three factors, costPerDistance, on every vehicle type, globalTimeCostFactor and scalingParameter, to priorize maxTransportTime over sumTransportTime.

I don't know if it's already correct. I'm still testing and checking the results.

[jsprit]

Seems to be a very important thread for the whole project. Thus I reopen it again. I would really appreciate you could keep me updated with your experiments :).

[agausachs]

@pierredavidbelanger Returning to the comment by Stefan on 03/24, I have been looking on your website and if I'm not wrong Stefan is talking about ekmeans. Do you have your cluster routine integrated with jsprit or should I do clustering first and then use the clusters on jsprit? Thanks.

[pierredavidbelanger]

@agausachs Yes he is talking about ekmeans.

No, I did not integrate it into jsprit. Instead, in one of my projet I use both libs separately, and use some glue (Constraint) to make it work together.

First, I use ekmean to cluster the jobs (data points are jobs and centroids are drivers). The end result is an array with the assignments.

After, I call jsprit normally, except that I add a special SoftRouteConstraint that check for each JobInsertionContext, if the ctx.newVehicle.id is assigned to ctx.job.id in the assignments. If yes, getCosts returns 0, if not It returns an extra cost (ie: double the original cost).

[agausachs]

Thanks @pierredavidbelanger ! I will take a look on your approach.

[authent1c]

I have the same problem with heterogeneous fleet with different skills and timewindow delivery but with only one route(from one depot to another). Current algorithm search jobs only for 100 vehicles from 250+, and more than 100 job stay unassigned, but I can manually find suitable jobs for free vehicles and unassigned jobs. Have You any complex examples for 1.4 version? Skills starts in 1.4 and besides it example code at 27 May doesnt compile and run with 1.4. Or may be it can be tuned by FixedCost or costByTime costByDistance options in vehicleType?

[jsprit]

If you have unassigned jobs, even you have enough available capacities, then the way unassigned jobs are penalyzed is not appropriate for you. Look at this to solve it: https://groups.google.com/forum/#!topic/jsprit-mailing-list/z6SjCgImM34. Version 1.4 contains break changes, i.e. older code might not compile anymore. Look at the changelog to adapt to 1.4.x. You also find a link to an example that might make adapting easier.

[authent1c]

@jsprit thanx for Yr reply. I've checked this solution but have no success. Looks like TW constraint on insertion bit others and I have no many different allocations for vehicles and jobs

[karussell]

@pierredavidbelanger the ekmeans library looks useful, why the GPL license :) ? Thats the reason I'll have to prefer apache commons

[pierredavidbelanger]

@karussell Good question. Indeed the apache commons-maths lib is less restrictive, and their KMeans impl is probably more flexible (but also complex) and more tested than mine. But they do not have the special "equals" option I am trying to achieve (https://code.google.com/p/ekmeans/#Motivation). The reason I choose GPL for this particular project (all my others projects are LGPL or MIT), is that I want to force commercial applications developers to contribute back to my project if they fix my bug (https://code.google.com/p/ekmeans/#Known_bugs). But, I have had a couple requests to use my (unmodified) lib in commercial applications, and I always said OK (https://code.google.com/p/ekmeans/#License).

[PGWelch]

Hi Pierre,

Is it possible for you to give a quick overview of how ekmeans works? Does it run an optimisation?

@karussell ODL Studio has a capacitated clusterer under LGP licence https://github.com/PGWelch/com.opendoorlogistics/tree/master/com.opendoorlogistics.components/src/com/opendoorlogistics/components/cluster/capacitated/solver but this only enforces a maximum size, not a minimum. Technically it's a p-median solver. If anyone was going to use it I could pull it out into a separate library.

Philip Welch http://uk.linkedin.com/in/welchphilip http://www.opendoorlogistics.com

On 16 Dec 2014, at 01:37, Pierre-David Bélanger notifications@github.com wrote:

@karussell Good question. Indeed the apache commons-maths lib is less restrictive, and their KMeans impl is probably more flexible (but also complex) and more tested than mine. But they do not have the special "equals" option I am trying to achieve (https://code.google.com/p/ekmeans/#Motivation). The reason I choose GPL for this particular project (all my others projects are LGPL or MIT), is that I want to force commercial applications developers to contribute back to my project if they fix my bug (https://code.google.com/p/ekmeans/#Known_bugs). But, I have had a couple requests to use my (unmodified) lib in commercial applications, and I always said OK (https://code.google.com/p/ekmeans/#License).

— Reply to this email directly or view it on GitHub.

[karussell]

@pierredavidbelanger oh, if its because of the bugs I would have put this probably under AGPL ;). Anyway: seems useful and will contact you if necessary! @PGWelch thanks! The p-median seems to be even better suited if you know the vehicle its positions up-front, nice! Will have a look into it! Without this information maybe the best approach would be also a graph partitioning algorithm. @jsprit +1 for having this 'spatial data partitioner' inbuilt in jsprit ;)

[lfreneda]

@agausachs did you solve it?