Traveling Purchaser Problem

The undirected Traveling Purchaser Problem (TPP) defined as follows. Consider a depot$v_0$, a set of markets$M:=\{v_1,\ldots,v_n\}$, and a set of products$K:=\{p_1,\ldots,p_m\}$. Let $G=(V,E)$ be an undirected graph where $V:=\{v_0\}\cup M$ is the vertex set and $E:=\{[v_i,v_j]:v_i,v_j\in V, i<j\}$ is the edge set. Each product $p_k$ can be purchased at a subset $M_k$ of markets. The number of units of product $p_k$ that must be purchased is equal to $d_k$ and only $q_{ki}$ units of $p_k$ are available at market $v_i$. We assume$q_{ki}$ and $d_k$ satisfy $0<{q_{ki}}\leq d_k$ and $\sum_{v_j\in M_k} q_{kj} \geq d_k$ for all $p_k\in K$ and $v_i\in M_k$. The price of product $p_k$ at market $v_i$ is equal to $b_{ki}$, and the travel cost between $v_i$ and $v_j$ is equal to the cost of the edge $e=[v_i,v_j]$ denoted by $c_e$.

The TPP consists of determining a simple cycle in $G$ passing through the depot and a subset of markets so that all products are purchased at a total minimum cost obtained by adding the routing cost and the purchase price. This definition of the TPP generalizes the classical case with unlimited supplies, i.e. $q_{ki}=d_k$ for all $i,k$.

The TPP is $\cal{NP}$-hard since it reduces to the Traveling Salesman Problem (TSP) when $m=n$ and$\vert M_k\vert=1$ for all $k$. The TPP also reduces to the Uncapacitated Facility Location Problem (UFLP) when $M_k=M$ for all $k$,$q_{ki}=d_k$ for all $i,k$, and $c_{ij}=(f_i+f_j)/2$ for all $[v_i,v_j]\in E$, where $f_i$ is the cost of opening facility $v_i$ ($f_0:=0$) and $b_{ki}$ is the cost of serving customer $p_k$ from facility $v_i$.

To our knowledge all previous studies of the TPP are restricted to the classical case where supply is unlimited. The problem was introduced by Burstall(1966) and by Buzacott and Dutta(1971) in relation with job scheduling. In this application, a multi-purpose machine can assume different configurations $v_i$ and each task $p_k$ must be executed using one of several configurations of the machine belonging to a set $M_k$.

The machine is initially in configuration $v_0$, and must return to this configuration after performing all tasks. The changeover and execution times (i.e. $c_{ij}$ and $b_{ki}$, respectively) are given. The problem consists of selecting a set and sequence of configurations to execute all tasks in minimum time. Ramesh(1981) defined the TPP in a routing context, while Singh and van Oudheusden(1997) described other applications in the area of warehousing. Various heuristics for the TPP were proposed by Golden, Levy and Dahl(1981) , Ong(1982) , and Pearn and Chien (1998) . Ramesh(1981) described an exact method based on lexicographic search capable of handling instances with $\vert V\vert\leq 12$ and $\vert K\vert\leq 10$. Singh and van Oudheusden(1997) presented a branch-and-bound algorithm solving directed instances with $\vert V\vert\in\{10,15,20,25\}$ and $\vert K\vert\in\{10,30,50,100\}$, and undirected instances with $\vert V\vert\in\{10,15,20\}$ and $\vert K\vert\in\{15,30,50\}$. They computed the bound by solving a UFLP. We proposed in Laporte, Riera and Salazar (2000) an alternative ILP model and a branch-and-cut algorithm for the TPP with limited supplies that fully exploits this problem's structure. The model and its polyhedral properties are described in Section 2, followed by the algorithm in Section 3 and by the computational results in Section 4. Our approach has solved to optimality instances with up to 200 markets and 200 products within very reasonable computing time of a PC Pentium.

TPP instances: This is a test-bed library containing bench marking instances for testing and comparing new approaches for solving the TPP.Instances are availables in the TPPLIB format In the following weeks we will also insert some instances with optimal solutions.
 

Class-1 generator

Class-2 generator

Class-3 generator

Class-4 generator
 
 

Instance 1 with solution cost=12

Instance 2 with solution cost=13

Instance 3 with solution cost=11