Optimization Online


A modern POPMUSIC matheuristic for the capacitated vehicle routing problem

Eduardo Queiroga (eduardoqueiroga***at***id.uff.br)
Ruslan Sadykov (ruslan.sadykov***at***inria.fr)
Eduardo Uchoa (uchoa***at***producao.uff.br)

Abstract: This work proposes a partial optimization metaheuristic under special intensification conditions (POPMUSIC) for the classical capacitated vehicle routing problem (CVRP). The proposed approach uses a branch-cut-and-price algorithm as a powerful heuristic to solve subproblems whose dimensions are typically between 25 and 200 customers. The whole algorithm can be seen as the application of local search over very large neighborhoods, starting from a single initial solution. The main computational experiments were carried out on instances having between 302 and 1000 customers. Using initial solutions generated by some of the best available metaheuristics for the problem, POPMUSIC was able to obtain consistently better solutions for long runs of up to 32 hours. In a final experiment, starting from the best known solutions available in CVRP library (CVRPLIB), POPMUSIC was able to find new best solutions for several instances, including some very large ones.

Keywords: Capacitated vehicle routing problem; POPMUSIC; Matheuristic; Local search

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Meta Heuristics )

Category 3: Applications -- OR and Management Sciences

Citation: @techreport{QueirogaEtAl2020, Author = {Eduardo Queiroga and Ruslan Sadykov and Eduardo Uchoa}, Title = {A modern POPMUSIC matheuristic for the capacitated vehicle routing problem}, Institution = {Cadernos do LOGIS-UFF}, Address = {Niter{\'o}i, Brazil}, Number = {L-2020-2}, pages = {28}, month = {November}, Year = {2020} }

Download: [PDF]

Entry Submitted: 11/06/2020
Entry Accepted: 11/09/2020
Entry Last Modified: 11/09/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society