experimental analysis of algorithms

New Benchmark Instances for the Capacitated Vehicle Routing Problem

  • Diego Pecin
  • Artur Alves Pessoa
  • Marcus Poggi de Aragão
  • Anand Subramanian
  • Eduardo Uchoa
  • Thibaut Vidal
    • Categories (Mixed) Integer Linear Programming, Meta Heuristics, Transportation Tags , ,

    The recent research on the CVRP is being slowed down by the lack of a good set of benchmark instances. The existing sets suff er from at least one of the following drawbacks: (i) became too easy for current algorithms; (ii) are too arti cial; (iii) are too homogeneous, not covering the wide range of characteristics found … Read more

    Probability distribution of solution time in GRASP: An experimental investigation

  • Renata M. Aiex
  • Mauricio G.C. Resende
  • Celso C. Ribeiro
    • Categories Meta Heuristics Tags , , , , ,

    A GRASP (greedy randomized adaptive search procedure) is a multi-start metaheuristic for combinatorial optimization. We study the probability distributions of solution time to a sub-optimal target value in five GRASPs that have appeared in the literature and for which source code is available. The distributions are estimated by running 12,000 independent runs of the heuristic. … Read more