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

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