55 views

Skip to first unread message

Aug 14, 2014, 9:28:44 AM8/14/14

to watch...@googlegroups.com

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

Aug 14, 2014, 2:04:09 PM8/14/14

to watch...@googlegroups.com

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

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

Oct 25, 2014, 1:38:36 PM10/25/14

to watch...@googlegroups.com

Paul,

Vikas

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

Oct 25, 2014, 1:41:11 PM10/25/14

to watch...@googlegroups.com

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

Oct 26, 2014, 4:41:02 PM10/26/14

to watch...@googlegroups.com

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)?

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)?

Oct 26, 2014, 6:56:44 PM10/26/14

to watch...@googlegroups.com

Paul,

Vikas

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

Oct 29, 2014, 3:16:03 PM10/29/14

to watch...@googlegroups.com

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.

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.

Nov 2, 2014, 9:20:24 AM11/2/14

to watch...@googlegroups.com

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

Nov 2, 2014, 11:54:05 AM11/2/14

to watch...@googlegroups.com

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

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

Nov 4, 2014, 8:38:27 PM11/4/14

to watch...@googlegroups.com

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

Nov 4, 2014, 8:41:47 PM11/4/14

to watch...@googlegroups.com

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

Nov 5, 2014, 11:51:08 AM11/5/14

to watch...@googlegroups.com

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.

Nov 6, 2014, 10:15:29 AM11/6/14

to watch...@googlegroups.com

Thanks for the response. I really appreciate it.

Vikas

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu