The Travelling and Purchase Problem Domain ========================================== This is a relatively recent planning domain that has been investigating in Operation Research (OR) for several years. The Travelling Purchase Problem (TPP) is a known generalization of the Travelling Salesman Problem, and is defined as follows. We have a set of products and a set of markets. Each market is provided with a limited amount of each product at a known price. The TPP consists in selecting a subset of markets such that a given demand of each product can be purchased, minimizing the routing cost and the purchasing cost. This problem arises in several applications, mainly in routing and scheduling contexts, and it is NP-hard. In OR, computing optimal or near optimal solutions for TPP instances is still an active research topic. For IPC-5, we have formalized several variants of this domain in PDDL. One of them is equivalent to the original TPP, while the others are different formulations or significant (we believe and hope) extensions. In all these domain variants, plan quality is important, although for some instances even finding an arbitrary solution could be quite difficult for a fully-automated planner. Note that for this domain we have both a Metric version (no time) and a MetricTemporal version. The metric version is a PDDL formulation that is equivalent to the original formulation of TPP in OR. Domain Variants =============== We start the description from the Metric version because it is the one equivalent to the original formulation of TPP. TPP Metric ---------- This version is equivalent to the original formulation of TPP in OR. There are only three operators, two of which are used to model the purchasing actions: "buy-all" and "buy-allneeded". The first buys at a certain market (?m) the whole amount of a good (?g) sold by the market (?m and ?g are operator parameters); while the second one buys at ?m the amount of ?g that is needed to complete the purchase of ?g (as specified in the problem goals). Note that every market is *directly* connected to every other market and to the depots. Moreover, there is only one depot and only one truck. TPP propositional ----------------- This version models a variant of the original TPP where: (1) there can be more than one depot and more than one truck; (2) the amount of goods are discrete and represented by qualitative levels; (3) every type of good has the same price, independent from the market where we buy it; (4) there are two new operators for loading and unloading goods to/from trucks (5) markets and depots can be indirectly connected. TPP SimplePreferences --------------------- The operators in this domain are the same as in the propositional version. The difference is in the goals. All goals are soft goals (preferences). These preferences concern maximizing the level of goods that are stored in the depots, constraints between the levels of different stored goods, and the safety condition that all purchased goods are stored at some market. Note that there is an equivalent sub-version, "GroundedPreferences", where the quantified variables appearing in the preferences have been instantiated. This is a sub-directory of the directory containing the SimplePreference version. TPP Qualitative preferences --------------------------- The operators in this version are the same as in the propositional version. All goals are preferences concerning maximizing, for every good, the purchased and stored levels. This version includes preferences over trajectory constraints. These are constraints between the levels of two types of stored goods; constraints about the use of the trucks for loading goods; constraints imposing the use of every truck. Moreover, we have the preference that in the final state all purchased goods are stored at some depot. TPP MetricTemporal ------------------ With respect to the simpler Metric version, which is equivalent to the original formulation of TPP, this version has the the following main differences: same as points (1), (4), (5) illustrated in the description of the Propositional variants; each action has a duration and the plan quality is a linear combination of total-time (makespan) and the total cost of traveling and purchasing; the operator "buyall" has a "rebate" rate (if you buy the whole amount of a good that is sold at a market, then you have a discount). TPP MetricTemporalConstraints ----------------------------- The operators in this version are the same as in the MetricTemporal version. In addition, in the domain file, we have some strong constraints imposing that in the final state all purchased goods are stored, every market can be visited by at most one truck at the same time, every truck is used. Moreover, in the problem specification, we have several strong constraints about the relative amounts of different types of goods stored in a depot, the number of times a truck can visit a market, the order in which goods should be stored, the order in which we should store some good and buy another one, and deadlines about delivering goods once they have been loaded in a truck. **PLESE NOTE THAT** while we tried to generate the constraints in such a way that the problems remain solvable, there is no guarantee that every problem instance is solvable. Unfortunately, there is no planner that we could use to make this check. TPP MetricTemporalComplexPreferences ------------------------------------ The operators in this version are the same as in the MetricTemporal version. In addition, it contains many preferences over state trajectory constraints that are similar to those used for the MetricTemporalConstraints version.