• Graduate program
    • Why Tinbergen Institute?
    • Program Structure
    • Courses
    • Course Registration
    • Recent PhD Placements
    • Admissions
    • Facilities
  • Research
  • News
  • Events
    • Events Calendar
    • Tinbergen Institute Lectures
    • Annual Tinbergen Institute Conference
    • Events Archive
    • Summer School
      • Inequalities in Health and Healthcare
      • Research on Productivity, Trade, and Growth
      • Behavioral Macro and Complexity
      • Business Data Science Summer School Program
  • Summer School
  • Alumni
  • Times
Home | Events Archive | A P-step Formulation for the Capacitated Vehicle Routing Problem

A P-step Formulation for the Capacitated Vehicle Routing Problem

  • Series
  • Speaker
    Remy Spliet (Erasmus University Rotterdam)
  • Field
  • Location
    Erasmus University Rotterdam, E-Building, Room EB-12
  • Date and time

    May 03, 2019
    12:00 - 13:00


For vehicle routing problems there are two main types of formulations that are commonly used: arc-flow formulations and set-partitioning formulations. Arc-flow formulations typically include decision variables specifying whether an arc is used or not, while set-partitioning formulations include decision variables specifying whether a route is used or not. The former are known for providing weak LP-bounds that can be computed fast, while the latter provide strong LP-bounds that require more computation time. We provide a new formulation based on partial routes containing exactly p arcs, referred to as p-steps. This provides a family of formulations, one for every choice of p, that has arc-flow and set partitioning formulations at its extremes. We are able to show that the LP-bounds are increasing in p, although non-monotonically. Furthermore, we propose a column generation algorithm to compute these bounds. We investigate whether the computation time also increases in p. The goal is to find a value p that provides a good trade-off between strength of the LP-bound and computation time to speed up the branching algorithms to find integer optimal solutions.