Consider the following three problems. The first is intended to be a simplification of the second that might be amenable to solution methods the second is not amenable to.
First problem: Assume we have an undirected graph, each vertex of which has a payout associated with visiting it (e.g. five dollars). Each edge has an associated travel duration (e.g. fifteen minutes). Given a time limit (e.g. eight hours), find the route that takes less than this time limit to traverse that maximizes the payout.
Second problem: In this variant, the payout is not a scalar in dollars, but a vector of apples, oranges, and plums. Instead of a single payout value associated with each vertex, there are multiple payouts (e.g. visiting a certain vertex comes with a payout of one apple, two oranges, and a plum). Which route, under the time limit, maximizes the number of fruit paid out in the smallest component (e.g. {two apples, two oranges, one plum} is preferable to {one apple, two oranges, zero plums}) (EDITED to correct earlier mistake pointed out by prubin).
Third problem: The same as the second problem, but instead of looking for a single optimal solution, we are looking for a description of the non-dominated set. So if one path gets {one apple, two oranges, one plum} and another gets {two apples, one orange, one plum}, both are returned because neither is better in all dimensions.
Can all three problems be formulated as mixed integer linear programs? Are any in a named class of optimization problems? Are there known optimal algorithms for these problems?