Vehicle routing with split deliveries

Moshe Dror, Gilbert Laporte, Pierre Trudeau

Research output: Contribution to journalArticlepeer-review

180 Scopus citations


This paper considers a relaxation of the classical vehicle routing problem (VRP), in which split deliveries are allowed. As the classical VRP, this problem is NP-hard, but nonetheless it seems more difficult to solve exactly. It is first formulated as an integer linear program. Several new classes of valid constraints are derived, and a hierarchy between these is established. A constraint relaxation branch and bound algorithm for the problem is then described. Computational results indicate that by using an appropriate combination of constraints, the gap between the lower and upper bounds at the root of the search tree can be reduced considerably. These results also confirm the quality of a previously published heuristic for this problem.

Original languageEnglish (US)
Pages (from-to)239-254
Number of pages16
JournalDiscrete Applied Mathematics
Issue number3
StatePublished - May 20 1994


  • Connectivity constraints
  • Fractional cycle elimination constraints
  • Split delivery vehicle routing problem
  • Subtour elimination constraints
  • k-split cycles

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Vehicle routing with split deliveries'. Together they form a unique fingerprint.

Cite this