文献类型：会议论文

英文题名：Better Approximation Ratios for the Single-Vehicle Scheduling Problems on Tree/Cycle Networks

作者：Wu, Yuanxiao[1];Lu, Xiwen[1]

机构：[1]East China Univ Sci & Technol, Shanghai, Peoples R China

会议论文集：11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

会议日期：DEC 16-18, 2017

会议地点：Shanghai, PEOPLES R CHINA

语种：英文

外文关键词：Vehicle; Routing; Scheduling; Network; Approximation algorithm

摘要：We investigate the single vehicle scheduling problems based on tree/cycle networks. Each customer, assumed as a vertex on the given network, has a release time and a service time requirements. The single vehicle starts from the depot and aims to serve all the customers. The objective of the problem is to find the relatively optimal routing schedule so as to minimize the makespan. We provide a 16/9-approximation algorithm and a 48/25-approximation algorithm for the tour-version and the path-version of single vehicle scheduling problem on a tree, respectively. For the tour-version of single vehicle scheduling problem on a cycle, we present a 5/3-approximation algorithm.