Approximation algorithms for single vehicle scheduling problems with release and service times on a tree or cycle

作者：Bao, Xiaoguang; Liu, Zhaohui^*

来源：Theoretical Computer Science, 2012, 434: 1-10.

DOI：10.1016/j.tcs.2012.01.046

• Vehicle routing
• Vehicle scheduling
• Tree
• Cycle
• Approximation algorithm

We consider the single vehicle scheduling problem in which the customers are located at the vertices of a tree or a cycle, and have release and service time requirements. The objective is to minimize the makespan. In the tour-version the makespan means the time when the vehicle returns to its initial location after serving all customers. While in the path-version the makespan refers to the maximum completion time of all customers. For the problem on a tree, we present a 9/5-approximation algorithm for the tour-version and a 27/14-approximation algorithm for the path-version. For the problem on a cycle, we present 12/7-approximation algorithms for both versions.

• 出版日期2012-5-25
• 单位华东理工大学