A Branch-and-price Algorithm for the Multi-Vehicle Covering Tour Problem

Autor:	Vitor A.A. Souza, Alexandre Salles da Cunha, Ramon Lopes
Rok vydání:	2013
Předmět:	Mathematical optimization Heuristic (computer science) Applied Mathematics Branch and price Discrete Mathematics and Combinatorics Combinatorial optimization CPU time Column generation Limit (mathematics) Pruning (decision trees) Resolution (logic) Algorithm Mathematics
Zdroj:	Electronic Notes in Discrete Mathematics. 44:61-66
ISSN:	1571-0653
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::28841bd5284baba621c41f1b93b85442 https://doi.org/10.1016/j.endm.2013.10.010 Zobrazit plný text záznamu Full Text from ScienceDirect