Developing Pareto Front using Watchmaker Framework

[Vikas Agrawal]

Hello All,

I was wondering if there is any way we can solve multi-criterion optimization problem using Watchmaker framework. I wish to develop a Pareto Frontier.

I am working on a package deliver optimization problem. The company has many jobs to fulfill each day using multiple drivers. Company can have two conflicting objectives i.e. to minimize the total distance covered (and while doing so might end up using quite a bit number of drivers) or to minimize the total number of drivers used to complete all the jobs (and while doing so might mean lot more miles covered). So if we can develop a Pareto frontier, it would give a nice selection of alternatives to the company to make the decision from.

Any thoughts on this will be greatly appreciated. 

Thanks for your time...

Vikas

[Paul]

At the risk of belaboring the obvious, evolutionary solvers are metaheuristics, with no explicit proof/guarantee of optimality, so your goal should be to get near to the Pareto frontier.

As to how to do that, I would run a GA on the model using just the first objective function, then again using just the second objective function. After that you can keep rerunning it using convex combinations of the two objectives (weighted sum, positive weights that add up to 1). It might be a good idea to normalize the objectives before weighting them. For instance, you might use w*f_1/f_1^* + (1 - w)*f_2/f_2^* where f_1 and f_2 are the objectives, f_1^* and f_2^* their best known values (from the first two runs), and 0 < w < 1 the weight to combine them. (I'm assuming that both objectives go in the same direction -- both min, or both max.) Do this for a "reasonable sample" of weights (I'll let you define that phrase), plot the function values and see if it looks good enough for your purposes.

Paul

[Vikas Agrawal]

Paul,

I have been thinking about this. Whatever you mentioned makes perfect sense. I am about to to implement this. However is there better way to normalize the objectives? 

Thanks,

Vikas

[Vikas Agrawal]

Because, both objective functions go in opposite direction. I need to minimize the total miles traveled (which could use lots of drivers) or maximize the number of drivers (which will minimize the total miles traveled since more drivers are available.)

[Vikas Agrawal]

I am attaching a file that explains my Pareto Front. May be this might help you understand what I am trying to achieve.

Thanks,

Vikas

[Paul]

Your diagram contradicts what you said in the previous message. (In the diagram, you have at least one different objective, and both are being minimized.)

In any case, everything you've mentioned (miles traveled, driving time, number of drivers) has an associated cost. Are you sure that you don't want to weight each one by its unit cost and minimize the weighted sum (total cost)?

[Vikas Agrawal]

Paul,

I get your point. Sorry for misrepresentation. After reviewing it again, I get that both are being minimized. Right now my top priority constraint is minimizing total miles traveled and secondary constraint is to minimize the total no. of drivers used in case there are multiple solutions for minimum miles traveled.

The formula you mentioned is what I have in mind to implement for the weighted sum i.e.  w*f_1/f_1^* + (1 - w)*f_2/f_2^*  where f_1 and f_2 are the objectives, f_1^* and f_2^* their best known values (from the first two runs), and 0 < w < 1 the weight to combine them. 

But if I take f_1^* as the best know value from my previous runs (which will give the minimum distance to travel), the ratio of f_1/f_1^* could be more than 1. My understanding was that the normalized scores should be between 0 and 1. Please correct me if I am wrong. 

Thanks,

Vikas

[Paul]

Normalizing to the range [0, 1] is common but not a requirement in general. The main purpose of normalization is to strip off units in order to make disparate objectives more comparable.

If you want to stick to minimization, you could use w*f_1^*/f_1 + (1-w)*f_2^*/f_2 (flipping your previous ratios). Since f_j >= f_j^* by definition, this normalizes to the range [0, 1].

If I were a manager, though, I'd be pretty unhappy with what you're doing. At the risk of repeating myself, I would want total cost as the single criterion, not total miles as priority 1 and number of drivers as priority 2 (unless the drivers came free of charge -- are you using conscript labor?). As it stands, you could be piling on pricey drivers in order to shave a few cheap miles off the distance measure.

[Vikas Agrawal]

Paul,

Thanks for your informative response. I would agree with you about using cost as the single criterion. Actually when we talked with the company, they said that they have plenty of drivers available at any given time. So they are not worried about it. Looks like packaging delivery service is just one business out of many others that this company owns. So they may have a pool of drivers which could be used for many different purposes.

Also when we asked about the cost, they said that it's difficult to assign a cost measure as it depends upon not only the distance between the locations but also on the weight of the package, size of the package, worth of the package, size of the vehicle and the experience of the drivers.

I will keep you posted on this for sure as more information becomes available. I really appreciate your comments as it's helping me a lot.

Thanks,

Vikas

[Paul]

Vikas,

The company should talk to someone at UPS. UPS uses analytics models to route vehicles, load packages etc., and they seem to have a pretty good handle on what the cost drivers are and how to measure them.

Meanwhile, good luck with the client!

Paul

[Vikas Agrawal]

Paul,

How would you create a pareto front with just one single weighted score? The fitness function  w*f_1^*/f_1 + (1-w)*f_2^*/f_2 will return just one value. We need two coordinates to plot a point.

Thanks,

Vikas

[Vikas Agrawal]

Should I have f_1^*/f_1 on one axis and f_2^*/f_2 on another?

[Paul]

Yes, although it might be easier for the client if you just use f_1 on one axis and f_2 on the other. You generate points in the plot by solving with different weights.

[Vikas Agrawal]

Thanks for the response. I really appreciate it.

Vikas