• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book chapter

Tolerance-Based vs. Cost-Based Branching for the Asymmetric Capacitated Vehicle Routing Problem

P. 1-10.
Mikhail Batsyn, Boris Goldengorin, Anton Kocheturov, Panos M. Pardalos.

In this paper, we consider the asymmetric capacitated vehicle routing problem (ACVRP). We compare the search tree size and computational time for the bottleneck tolerance-based and cost-based branching rules within a branch-and-bound algorithm on the FTV benchmark instances. Our computational experiments show that the tolerance-based branching rule reduces the search tree size by 45 times and the CPU time by 2.8 times in average.

In book

Vol. 59. NY: Springer, 2013.