A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree |
| |
Authors: | Tetsuo Asano Naoki Katoh Kazuhiro Kawashima |
| |
Institution: | (1) School of Information Science, JAIST, Asahidai, Tatsunokuchi, 923-1292, Japan;(2) Department of Architecture and Architectural Systems, Kyoto University, Yoshida-Honmachi, Sakyo-ku, Kyoto, 606-8501, Japan |
| |
Abstract: | This paper presents a new approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot. Customers are located on vertices of the tree, and each customer has a positive demand. Demands of customers are served by a fleet of identical vehicles with limited capacity. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. Each tour begins at the depot, visits a subset of the customers and returns to the depot without violating the capacity constraint. We propose a 1.35078-approximation algorithm for the problem (exactly,
), which is an improvement over the existing 1.5-approximation. |
| |
Keywords: | capacitated vehicle routing approximation algorithm |
本文献已被 SpringerLink 等数据库收录! |
|