星型网络上单台车辆分群调度问题  

Single Vehicle Scheduling Problem with Cluster on Start Network

作　　者：包晓光[1] 焦长春 BAO Xiaoguang;JIAO Changchun(College of Information Technology,Shanghai Ocean University,Shanghai 201306,China)

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

出　　处：《重庆师范大学学报（自然科学版）》2021年第5期6-11,共6页Journal of Chongqing Normal University:Natural Science

基　　金：国家自然科学基金(No.11701363)。

摘　　要：【目的】星型网络上单台车辆分群调度问题是运筹学和计算机科学中一个重要的组合优化问题。【方法】对客户服务时间为零的情形,证明存在一个具有良好性质的最优解;对客户服务时间任意的情形,设计两个候选时间表然后选择表长较短者作为最终的近似解。【结果】对第1种情形,给出一个多项式时间最优算法;对第2种情形,给出一个近似比为5/3的近似算法。【结论】研究结果可为交通运输、生产制造、生物科学等相关行业提供有效决策支持。[Purposes]The vehicle scheduling problem with cluster is studied.It is an important combinatorial optimization problem in operations research and computer science.[Methods]In the case where the service time of each customer is zero,an optimality property of the problem is proved.In the case where the service time of each customer is given arbitrarily,two candidate schedules are first designed and then the shorter one is selected as the final approximate solution.[Findings]For the former,apolynomial-time optimal algorithm is presented.For the latter,a 5/3-approximation algorithm is proposed.[Conclusions]The results obtained can provide effective decision support for transportation industry,industrial manufacture,biological science,and so on.

关 键 词：运筹学 车辆调度 客户分群 星型网络 近似算法 

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