A multi-commodity, capacitated pickup and delivery problem: The single and two-vehicle cases

Research output: Contribution to journalJournal articleResearchpeer-review


We explore dynamic programming solutions for a multi-commodity, capacitated pickup and delivery problem. Cargo flows are given by an origin/destination matrix which is not necessarily symmetric. This problem is a generalization of several known pickup and delivery problems, as regards both problem structure and objective function. Solution approaches are developed for the single-vehicle and two-vehicle cases. The fact that for each cargo that goes from a node i to another node j there may be a cargo going in the opposite direction provides the motivation for the two-vehicle case, because one may conceivably consider solutions where no cargoes that travel in opposite directions between node pairs are carried by the same vehicle. Yet, it is shown that such scenarios are generally sub-optimal. As expected, the computational effort of the single vehicle algorithm is exponential in the number of cargoes. For the two-vehicle case, said effort is of an order of magnitude that is not higher than that of the single-vehicle case. Some rudimentary examples are presented or both the single-vehicle and two-vehicle cases so as to better illustrate the method.
Original languageEnglish
JournalEuropean Journal of Operational Research
Issue number3
Pages (from-to)572-580
Publication statusPublished - 2011
Externally publishedYes


  • Routing
  • Scheduling
  • Pickup and delivery


Dive into the research topics of 'A multi-commodity, capacitated pickup and delivery problem: The single and two-vehicle cases'. Together they form a unique fingerprint.

Cite this