The merchant subtour problem

We consider the problem of a travelling merchant who makes money by buying commodities where they are cheap and selling them in other places where he can make a profit. The merchant ships commodities of his own choice in a van of fixed capacity. Given the prices of all the commodities in all of the places, and the cost of driving from one place to another, the problem the merchant faces each day is to select a subset of the cities that he can visit in a day, and to determine the order in which the cities are visited, such that the total profit is maximized. We call this problem the Merchant Subtour Problem. The MSP models the pricing problem of a rather complex pickup and delivery problem that was given to us by the Dutch logistics company Van Gend & Loos. We show that a special case of the MSP has a totally unimodular constraint matrix. This knowledge enables us to develop a tabu-search algorithm for finding good feasible solutions to the MSP, and a branch-and-price-and-cut algorithm for solving the MSP to optimality. The relaxations solved in each node of the branch-and-bound tree are strengthened by lifted knapsack inequalities, lifted cycle inequalities and mod-k cuts. We present computational results on data sets derived from our main instance of the Van Gend & Loos pickup and delivery problem.