%A Mulati, Mauro Henrique
%A Miyazawa, Flávio Keidi
%D 2017
%T Tighter Analysis of an Approximation for the Cumulative VRP
%K
%X We deal with the cumulative vehicle routing problem (VRP), a generalization of the capacitated VRP, which objective is to minimize the fuel consumption. Gaur et al. in 2013 gave a 4-approximation based on a well-known partition heuristic to the traveling salesperson problem (TSP). We present a tighter analysis obtaining a (4 - 4/(3s 3 Q 2 ))-approximation, where Q is the capacity of the vehicle and s is a scaling factor. To the best of our knowledge, this is the best proved approximation for the cumulative VRP so far.
%U https://sol.sbc.org.br/index.php/etc/article/view/3202
%J Anais do Encontro de Teoria da Computação (ETC)
%0 Journal Article
%R 10.5753/etc.2017.3202
%P 100-103%@ 2595-6116
%8 2017-07-02