2011/01/20 by Greg N. Frederickson, Frederickson, Greg N., Barry Wittman +1
Computer Science · Engineering · #68W25 (Primary) 90C27 #90C35 (Secondary) #Advanced Manufacturing and Logistics Optimization #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Optimization and Packing Problems #Vehicle Routing Optimization Methods #acm:68W25 #acm:90C27 #acm:90C35 #cs.DS #msc:68W25 #msc:90C27 #msc:90C35
paper · pdf · doi:10.48550/arxiv.1101.3953
7 pages
arxiv created 2011/01/20 · openalex publication_date 2011/01/20 · arxiv updated 2011/01/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Two multivehicle routing problems are considered in the framework that a visit to a location must take place during a specific time window in order to be counted and all time windows are the same length. In the first problem, the goal is to visit as many locations as possible using a fixed number of vehicles. In the second, the goal is to visit all locations using the smallest number of vehicles possible. For the first problem, we present an approximation algorithm whose output path collects a reward within a constant factor of optimal for any fixed number of vehicles. For the second problem, our algorithm finds a 6-approximation to the problem on a tree metric, whenever a single vehicle could visit all locations during their time windows.