Large Multi-variable Optimization Problem

[mfetch22]

There is a large chunk of information necessary as a preface to my question, so bare with me for a paragraph or two. I work for a pond treatment company. We have a set number of ponds we treat during a month, some are contracted to be treated once a month, some are treated twice. The question is simple "How do I maximize profit during a given month of treatment?" Seems simple on the surface, but I am having a lot of trouble with it.

As of now, we have two hourly workers in two separate trucks treating 5 days a week. My boss has three "treatment routes" setup for us to use. Each route consists of a specific set of locations across the city. The first route's members are all those ponds that are under contract to be treated once a month; we can call this set A. The second route's members are all those ponds that are under contract to be treated twice a month, excluding a specific set C. We can call the set associated with the second route B. The last route is precisely the specific set C mentioned before. The routes have been generated using a program that finds the most optimal route between any collection of addresses, such that one of the addresses is used as both the origin and the termination of the route (this address is the address of the company office/shop. This is where we start our treatments everyday). The problem here is that we never finish routes A or B in a single day, and only occasionally do we finish route C in a single day. As a result, we have to make a trip back to the shop (we can call this the origin I suppose) at the end of the day, and then the next day make the trip back to the point on the route at which we stopped the day before. Intuitively, this seems inefficient.

The bottom line is to optimize the amount of money made in a month considering only cost of driving, cost of workers, and income from pond treatments.

All of the locations on a given route are actually sets themselves. Each of these subsets represents a property. Each property is billed for the treatment of their pond/ponds monthly. The amount billed to each property remains constant through out the season. Each property can be billed for treatment only after all members of this subset have been treated as contracted. These subsets will contain at most 8 members (our largest property has 8 ponds). A day of treatment will never be ended in the middle of one of these subsets. Daily routes will only ever be terminated at a given member (pond) if all other members of that subset (property) have been visited.

So, all members of A must be visited once in a given month. All members of B must be visited twice a month. The reason that there exists a set C is because C is technically a single property that cannot be billed till all the members of C have been visited twice. However, there are over 30 ponds in set C, so my boss wants it separate because the completion of treatments for all members of set C brings in a large sum. This only occurs once every member of C has been visited twice for a given month (since C is contracted for treatments twice a month). We see no money from C until this is completed, regardless of weather we have treated some of its subsets already.

A couple values that I am sure will come into play (some will be constants, some will be variable functions):

Wage of worker A
Wage of worker B
Average miles per gallon of truck A
Average miles per gallon of truck B
Derivative of ponds treated with respect to time
Distance between endpoint of a given day to the origin for both workers
Time worked in a given day
Price of gas

My real question here is "How do I even start this problem?" I have a vague notion of how all these pieces fit together but I can't seem to get beyond that. Take the price of gas for example. That changes daily, and not in a well defined manner either. Same goes for ponds treated per day. Some days we move quickly, some days we get stuck spending the better half of that day at one pond. Mileage of the vehicles is variant as well (although I couldn't tell you exactly how it varies). Need I use highway mpg during parts of the route involving the highway and city mpg for the rest? Or will an average mpg suffice? Although there is a huge amount of variation possible in the setup I have given so far, many of the variables will have conditions imposed upon them (for example, time worked in a given day can't possibly exceed 24 hours, but will likely never exceed 12, and most frequently be $(8\pm1.5)$ hours. How do I account for or model these types of 'probabilistic' variables?)

I've always been interested in mathematics, so if concepts beyond calculus arise as a result of what I have explained above, do not be afraid to incorporate them in your response. I know this is a complicated question, but I also know that there must be some way to encapsulate all of these numbers and relations into a mathematical model. Any direction will help. I don't need you to solve this, I just need to know how to solve this. Thanks in advance.

 

[Mark44]

You need some better variables. You are using A for 1) a set of ponds on a property, 2) a worker, 3) a truck. It would be easier to get a handle on things if the names of the quantities were distinct. For example, you could use A, B, and C for the sets of ponds. If you need to break things down by individual ponds, you could identify them as A₁, A₂, A₃, and so on for the ponds in the A property.

The workers could be identified as W₁ and W₂, and the trucks as T₁ and T₂, or whatever other scheme you come up that eliminates the duplication that you have.

If I were doing this, I would keep track of things for a month or two (maybe you already do this), so I could get reasonable estimates for the two truck mileages. Instead of miles per gallon, maybe it would be easier to use some other measure, like how many gallons of fuel to treat all ponds on property A, on property B, on property C. As an alternative, the number of gallons of fuel for each truck for a week. That would take into account driving on highways and on city streets. If you have a reasonable value for gallons of fuel per month (or week), you can figure the cost by multiplying by the cost per gallon.

One of the values that you list puzzles me - "derivative of ponds treated with respect to time" What does that mean? To me, this seems less like a calculus problem, and more like a linear programming problem, where the goal is to optimize (minimize, in this case) your cost, subject to a number of constraints (such as the hours worked per day by each worker).

Linear programming is part of a mathematical field named operations research. Many large companies analyze their business operations using this technique, or so I understand.

 

[AlephZero]

You can eliminate some things with a bit of logic. For example, as you said you can't forecast the price of gas from day to day, but driving less mileage will use less gas (assuming all the routes have similar driving conditions) and also take less working time.

I would start trying to reduce the mileage by doing something like the following. From experience you know how many working days it takes per month to treat all the ponds. So that is a reasonable starting point for the number of trips you need to make per month, say N. Now, find the N ponds that are furthest from your office (counting the ponds twice if you have to treat them twice a month). Whatever plan you make, you have to drive out to those N ponds and return. So try to fit the other ponds around the "shortest" routes to and from those N ponds, with the right number of ponds on each route to make an average day's work.

Compare the mileage from that work plan with what you are currently doing. If it is a significant improvement, stop planning and try it out for real. If it's not an improvement, you should have learned something new about the problem as you went through the process.

You might be able to do better than the simple minded version above. For example if there is a "cluster" of ponds a long way away, it might be better to treat all of them in one trip (and ignore any nearer home that you drive past on the way out and back) so you only have to make one long trip to that neighborhood per month, and not two.

 

[mfetch22]

One of the values that you list puzzles me - "derivative of ponds treated with respect to time" What does that mean? To me, this seems less like a calculus problem, and more like a linear programming problem, where the goal is to optimize (minimize, in this case) your cost, subject to a number of constraints (such as the hours worked per day by each worker).

Correct. I was thinking this would end up in the realm of linear programing/linear algebra but I still think rates of change and calculus can be applied. I wasn't sure where they all fit in, and who was to become the primary player, so I figured I'd start with the calculus board. As far as "derivative of ponds treated with respect to time" goes, I mean to say how fast the ponds are getting treated. As I type this I think that possibly a better derivative to address may be "acreage treated per unit time". The amount billed to the property owners is given as:

$B=B_0+At$

where...$B_0=Minimal\:Charge\:Possible\:For\:Treatment$[itex]A=Acreage\f\:pond[/itex]and$t=Cost\:per\:Acre$

The acreage primarily determines the amount of money brought in by each pond, so it may be a better variable to examine.

I would start trying to reduce the mileage by doing something like the following. From experience you know how many working days it takes per month to treat all the ponds. So that is a reasonable starting point for the number of trips you need to make per month, say N. Now, find the N ponds that are furthest from your office (counting the ponds twice if you have to treat them twice a month). Whatever plan you make, you have to drive out to those N ponds and return. So try to fit the other ponds around the "shortest" routes to and from those N ponds, with the right number of ponds on each route to make an average day's work.

This makes sense, but I see another factor of the final function of...

$Profit=P_k(R(c_1, c_2, c_3...c_n))$

where [itex]k=Day\f\:Month[/itex]

and $R(c_1, c_2, c_3...c_n)=Optimal\:Route\:According\:to\:c_{0...n}$

where

$c_n=Route\:Determining\:Condition\:n$

All of the subsets have a differing value of money to be billed to them. So, intuitively, some properties have more 'worth' than others, and would therefore be more profitable to treat. I suppose this isn't necessarily true since, for example, if we are located in Boston, a pond in California that brings in $50 per treatment would not be worth the gas, but I believe you get my point. As a counterpoint, consider a large collection of private ponds in Iowa, with our theoretical shop still located in Boston. Let's say, all together, these ponds are billed for $10,000 (I wish we could charge that much, but, unfortunately, charging $10,000 is just for the sake of my argument). Almost certainly these ponds would be worth the drive. After delineating both extrema, its clear that minimizing mileage does not necessarily maximize profit.

Also, I believe the optimal route changes daily base off of what happened the day before. Of primary interest is the terminating position of the route on the previous day. I need to model it in such a way that all the factors of the previous day are taken into account every day of the month and than the route is reevaluated every day to ensure that

$P_k(R(c_{0...n}))$

reaches its maximum value for that given $k$

How do I model that mathematically and systematically so that we can come in everyday and know precisely the route that will optimize our profit based off of our initial conditions (the initial conditions being the final conditions of the previous day)?

EDIT: Also, as a point of clarification, the values of $c_n$ would be at least the following:

[itex]c_1=Ending\:position\:in\:route\f\:previous\:day[/itex]

$c_2=Income\:generated\:during\:previous\:day$

[itex]c_3=Cost\f\:workers\:during\:previous\:day[/itex]

[itex]c_4=Mileage\f\:previous\:day[/itex]

$c_5...c_n=Any\:further\:conditions\:not\:previously\:defined\:up\:to\:condition\:n$

 

[Mark44]

One of the values that you list puzzles me - "derivative of ponds treated with respect to time" What does that mean? To me, this seems less like a calculus problem, and more like a linear programming problem, where the goal is to optimize (minimize, in this case) your cost, subject to a number of constraints (such as the hours worked per day by each worker).

Correct. I was thinking this would end up in the realm of linear programing/linear algebra but I still think rates of change and calculus can be applied. I wasn't sure where they all fit in, and who was to become the primary player, so I figured I'd start with the calculus board. As far as "derivative of ponds treated with respect to time" goes, I mean to say how fast the ponds are getting treated. As I type this I think that possibly a better derivative to address may be "acreage treated per unit time". The amount billed to the property owners is given as:

$B=B_0+At$

where...


$B_0=Minimal\:Charge\:For\:Treatment$

[itex]A=Acreage\f\:pond[/itex]

and

$t=Cost\:per\:Acre$

The acreage primarily determines the amount of money brought in by each pond, so it may be a better variable to examine.

't' is an unfortunate choice for cost per acre, as it is almost universally used to represent time. I still don't see the need for derivatives, as it seems to be a fixed value.

 

[mfetch22]

't' is an unfortunate choice for cost per acre, as it is almost universally used to represent time. I still don't see the need for derivatives, as it seems to be a fixed value.

Correct and correct. 't' is not the best choice but I was simply trying to define the relationship between the variables I have introduced, not create a universally compatible system of studying this problem.

My usage of 'ponds treated with respect to time' is somewhat vague, but I mean to say "ponds treated per unit time". I do not posses a function to differentiate to arrive at this value. The rate of pond treatment changes after every single pond I treat. It is a discrete function that I was thinking may have a continuous analog. My hope was to illicit any application of differential equations to my problem (if there existed any such application) by referencing a derivative as a result of the qualitative meaning of the derivative, rather than computing it from a continuous function.

 

[AlephZero]

You want to separate out the things you can change from the things you can't. If you have a customer signed up, you can't change the location or size of their ponds, and presumably you can't change the price without agreeing a new contract. You can change the cost of traveling, and maybe other things as well.

If your prices are based only on the size of the ponds and independent of location (so you average out the transport costs for all customers) that's a separate issue from reducing the operating costs.

Also, I believe the optimal route changes daily base off of what happened the day before. Of primary interest is the terminating position of the route on the previous day.

The way I understood your OP, the initial "optimal" route did not take account of the length of the working day, so the planned route was not actually completed. In real life, the terminating position of the route is always the same - it is back at your base. That is the amount of gas you are paying for.

This seems to be a variation on the http://en.wikipedia.org/wiki/Travelling_salesman_problem which has been extensively studied - but there is no known algorithm for finding the "perfect" solution.