The merchant subtour problem

Bram Verweij, Karen Aardal

Research output: Contribution to journalArticleScientificpeer-review


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 maximised. 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.
Original languageEnglish
Pages (from-to)295-322
Number of pages28
JournalMathematical Programming
Issue number2-3
Publication statusPublished - 2003
Externally publishedYes


  • Feasible Solution
  • Computational Result
  • Total Profit
  • Price Problem
  • Constraint Matrix

Fingerprint Dive into the research topics of 'The merchant subtour problem'. Together they form a unique fingerprint.

Cite this