• Graduate program
  • Research
  • News
  • Events
    • Summer School
      • Climate Change
      • Gender in Society
      • Inequalities in Health and Healthcare
      • Business Data Science Summer School Program
      • Receive updates
    • Events Calendar
    • Events Archive
    • Tinbergen Institute Lectures
    • Conference: Consumer Search and Markets
    • Annual Tinbergen Institute Conference
  • Summer School
    • Climate Change
    • Gender in Society
    • Inequalities in Health and Healthcare
    • Business Data Science Summer School Program
    • Receive updates
  • Alumni
  • Magazine
Home | Events Archive | A P-step Formulation for the Capacitated Vehicle Routing Problem
Seminar

A P-step Formulation for the Capacitated Vehicle Routing Problem


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

    May 03, 2019
    12:00 - 13:00

Abstract:

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.