EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
2977. Formulations and Exact Solution Methods for the Undirected Team Orienteering Arc Routing Problem
Invited abstract in session MD-29: Vehicle Routing II, stream Combinatorial Optimization.
Monday, 14:30-16:00Room: 157 (building: 208)
Authors (first author is the speaker)
| 1. | Wenjin Yan
|
| IDS, ESSEC Business School of Paris | |
| 2. | Elena Fernandez
|
| Statistics and Operations Research, University of Cadiz | |
| 3. | Ivana Ljubic
|
| IDS, ESSEC Business School of Paris |
Abstract
Given an undirected graph, we study the team orienteering arc routing problem which asks to find a set of maximum profits routes starting and ending at the depot satisfying the vehicles' travelling time constraints. This problem has many important applications in practice, such as waste collection, snow plowing, and security patrolling, etc. In this article, we propose three new integer linear programming (ILP) formulations with only binary variables for this problem. To solve this problem in large instances, we introduce a Logic-based Benders decomposition (LBBD) and incorporate it into a branch-and-cut framework. We design problem-specific techniques to further improve the performance of the algorithm, such as Benders cuts strengthening approaches, repair heuristics, as well as symmetric breaking constraints and valid inequalities. In the computational study, we compare the performance of these formulations and different techniques.
Keywords
- Combinatorial Optimization
- Vehicle Routing
- Branch and Cut
Status: accepted
Back to the list of papers