In a supplier-manufacturer environment, planning has to be done for multiple periods in advance, for the collection and transportation of a variety of products from suppliers to the manufacturer. When a single product is available with multiple suppliers, there is a need to determine the right set of suppliers to be visited in each period, with the objective of minimizing the total travel distance. In our work, we model this case as a Multi-Product Multi-Period Orienteering Problem (MuPMPOP).

We developed Mixed Integer Linear Programming (MILP) model and heuristics for three scenarios namely, i) Every supplier having a single product; ii) Every supplier having multiple products; iii) In addition to scenario ii), a commitment is associated with all suppliers to collect a certain minimum quantity of products.

Using MILP model, optimal solutions and bounds were obtained. The Tabu Search metaheuristic was applied to scenarios (i) and (ii), while Iterated Tabu Search was used in scenario (iii). To generate starting solutions, Construction Heuristics were developed. The MILP models and heuristics were tested on randomly generated instances and the performance of heuristics was reported.

KEYWORDS: Orienteering Problem, Mixed Integer Linear Programming, heuristics, Multiple Periods, Multiple Products.