130. Exact Separation of Rounded Capacity Inequalities for the Capacitated Vehicle Routing Problem
Invited abstract in session ME-19: Vehicle Routing, cluster Combinatorial Optimization.
Monday, 16:15-17:45Room: FENH105
Authors (first author is the speaker)
| 1. | Konstantin Pavlikov
|
| Department of Business and Management, University of Southern Denmark | |
| 2. | Niels Christian Petersen
|
| Department of Business and Economics, University of Southern Denmark |
Abstract
The family of Rounded Capacity (RC) inequalities is one of the most important sets of valid inequalities for the Capacitated Vehicle Routing Problem (CVRP). This study considers the problem of separation of violated RC inequalities and develops an exact procedure employing mixed integer linear programming - very efficient for small- and medium-sized problem instances. For larger-scale problem instances, an iterative decomposition approach for exact separation of RC inequalities is developed, combining column and row generation and allowing the introduction of variables only when needed. A computational study demonstrates scalability of the proposed separation routines and provides exact RC-based lower bounds for some of the publicly available unsolved CVRP instances.
Keywords
- Routing
- VRP
- Mixed Integer Programming
Status: accepted
Back to the list of papers