Abstract: The single vehicle scheduling problems with cluster based on line/cycle networks are studied in this paper. Given a line/cycle network, some customers are distributed on the network. The customers are partitioned into several subsets, each of which is called a cluster. Each customer has a release time and a service time. Given a vehicle, it needs to serve all the customers, and serves the customers in each cluster consecutively. The problem is to compute a schedule that minimizes the time the vehicle returns to its initial location after serving all customers as required. To solve this problem, a 7/4-approximation algorithm for line-shaped network and a 13/7-approximation algorithm for cycle-shaped network are presented, respectively.

Key words: approximation algorithm, cluster, vehicle scheduling, line-shaped network, cycle-shaped network

摘要： 本文研究线型/圈型网络上单台车辆分群调度问题。给定一个线型/圈型网络,若干客户分布其中。所有客户被划分成若干个子集,每个子集称为一个群。每个客户有一个释放时间和一个服务时间。给定一台车辆,其需要服务所有客户,且每个群内的客户连续服务。问题的要求是计算一个时间表,使得车辆能够按要求服务完所有客户并返回初始出发位置所花费的时间最少。针对该问题,就线型网络和圈型网络,分别给出一个7/4和一个13/7近似算法。

关键词: 近似算法, 分群, 车辆调度, 线型网络, 圈型网络