A Branch-and-price Algorithm for the Multi-Vehicle Covering Tour Problem |
| |
| Institution: | 1. Departamento de Ciência da Computação, Universidade Federal do Rio de Janeiro, Brasil;2. Institut für Optimierung und Operations Research, Universität Ulm, Germany;1. Instituto de Cálculo and Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina;2. Departamento de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas, Universidad de Chile, Santiago, Chile;3. CONICET, Argentina |
| |
| Abstract: | In this paper, we propose a Branch-and-price (BP) algorithm and a Column Generation Heuristic (CGH) for the Multi-Vehicle Covering Tour Problem (m-CTP). Specific dominance and extension pruning rules are introduced to accelerate the resolution of the pricing problems. To the best of our knowledge, this is the first work dedicated to the exact resolution of m-CTP. The algorithm managed to solve about 30% of the instances in our test bed, within a 4 hour CPU time limit. Our preliminary computational experiments suggest that both the lower bounds provided by the formulation behind BP and the CGH upper bounds are of good quality. |
| |
| Keywords: | Branch-and-price Combinatorial Optimization Routing Problems |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
