线型/圈型网络上单台车辆分群调度问题  

Single Vehicle Scheduling Problems with Cluster on a Line/Cycle

作　　者：包晓光[1] 焦长春 BAO Xiao-guang;JIAO Chang-chun(College of Information Technology,Shanghai Ocean University,Shanghai 201306,China)

机构地区：[1]上海海洋大学信息学院,上海201306

出　　处：《运筹与管理》2022年第7期17-21,共5页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(11701363)。

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

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

分 类 号：O223[理学—运筹学与控制论]