文献类型：会议论文

英文题名：Improved algorithms for single vehicle scheduling 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

摘要：The single vehicle scheduling problems based on tree/cycle networks are studied in this paper. Each customer, assumed as a vertex on the given network, has a release time and a service time requirement. The single vehicle starts from the depot and aims to serve all the customers. The objective of the problem is to find the optimal routing schedule so as to minimize the makespan. We provide a 169\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{16}{9}$$\end{document}-approximation algorithm and a 4825\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{48}{25}$$\end{document}-approximation algorithm for the tour-version and path-version of single vehicle scheduling problem on a tree, respectively. For the tour-version and path-version of single vehicle scheduling problem on a cycle, we present a 53\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{5}{3}$$\end{document}-approximation algorithm and a 2917\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{29}{17}$$\end{document}-approximation algorithm, respectively.