• Graduate program
• Why Tinbergen Institute?
• Program Structure
• Courses
• Course Registration
• Facilities
• Students offices
• Location
• Housing
• Student Council
• Admissions
• Recent PhD Placements
• Research
• News
• Events
• Summer School
• Behavioral Macro and Complexity
• Econometrics and Data Science Methods for Business and Economics and Finance
• Inequalities in Health and Healthcare
• Introduction in Genome-Wide Data Analysis
• Research on Productivity, Trade, and Growth
• Summer School Business Data Science Program
• Events Calendar
• Tinbergen Institute Lectures
• Annual Tinbergen Institute Conference
• Events Archive
• Summer School
• Alumni
• PhD Theses
• Master Theses
• Selected Recent Placements
• Key alumni publications
• Alumni Community
• Times
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.