线形网络上单台车辆分群调度问题

doi:10.12005/orms.2017.0118

运筹与管理 ›› 2017, Vol. 26 ›› Issue (5): 125-129.DOI: 10.12005/orms.2017.0118

线形网络上单台车辆分群调度问题

包晓光¹, 刘朝晖², 余炜²

1.上海海洋大学信息学院,上海 201306;
2.华东理工大学理学院,上海 200237

收稿日期:2014-06-25 出版日期:2017-05-25
作者简介:包晓光(1983-),男,蒙古族,讲师,主要从事组合最优化研究;刘朝晖(1970-),男,教授,博士生导师,主要从事组合最优化研究;余炜(1985-),男,副教授,主要从事组合最优化研究。
基金资助:
国家自然科学基金项目(11171106,11301184);上海海洋大学博士科研启动基金(A2-0302-14-300079)

Single Vehicle Scheduling Problems with Cluster and Release Time Constraints on a Line

BAO Xiao-guang¹, LIU Zhao-hui², YU Wei²

1. College of Information Technology, Shanghai Ocean University, Shanghai 201306, China;
2. School of Sciences, East China University of Science and Technology, Shanghai 200237, China

Received:2014-06-25 Online:2017-05-25

摘要/Abstract

摘要： 本文研究线形网络上单台车辆分群调度问题:若干客户分布在一条直线上,它们被划分成若干个连续子集,其中每个子集称为一个群;每个客户有一个释放时间和一个服务时间;一台机器服务所有客户,且要求每个群内的客户连续服务;目标为极小化时间表长。该问题分两种形式:返回型和不返回型。返回型的时间表长定义为机器服务完所有客户后返回其初始位置的时间;不返回型的时间表长则定义为所有客户的最大完工时间。我们的结果是:对每个客户服务时间为零的情形,证明了两种形式均可在O(n²) 时间内解决;对每个客户服务时间任意的情形,就返回型和不返回型,分别给出了16/9和13/7近似算法。

关键词: 运筹学, 近似算法, 线形网络, 车辆路线, 车辆调度

Abstract: We consider the single vehicle scheduling problem in which some customers with release and service time requirements, are located at the vertices of a line, and a vehicle, initially waiting at some vertex, has to serve all the customers. The customers are partitioned into several consecutive clusters, and the customers in each cluster must be served consecutively. 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. In the case where the service time of each customer is zero, we show that both versions can be solved in O(n²)time. In the case where the service time of each customer is given arbitrarily, we present a 16/9-approximation algorithm for the tour-version and a 13/7-approximation algorithm for the path-version.

Key words: operations research, approximation algorithm, line-shaped network, vehicle routing, vehicle scheduling

中图分类号:

O223

包晓光, 刘朝晖, 余炜. 线形网络上单台车辆分群调度问题[J]. 运筹与管理, 2017, 26(5): 125-129.

BAO Xiao-guang, LIU Zhao-hui, YU Wei. Single Vehicle Scheduling Problems with Cluster and Release Time Constraints on a Line[J]. Operations Research and Management Science, 2017, 26(5): 125-129.

参考文献

[1] Chisman J A. The clustered traveling salesman problem[J]. Computers & Operations Research, 1975, 2: 115-119.
[2] Weintraub A, Aboud J, Fernandez C, Laporte G, Ramirez E. An emergency vehicle dispatching system for an electric utility in Chile [J]. Journal of the Operational Research Society, 1999, 50: 690-699.
[3] Laporte G, Palekar U. Some applications of the clustered traveling salesman problem[J]. Journal of the Operational Research Society, 2002, 53: 972-976.
[4] Guttmann-Beck N, Hassin R, Khuller S, Raghavachari B. Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem[J]. Algorithmica, 2000, 28: 422-437.
[5] Bao X, Liu Z. An improved approximation algorithm for the clustered traveling salesman problem[J]. Information Processing Letters, 2012, 112: 908-910.
[6] Psaraftis H, Solomon M, Magnanti T, Kim T U. Routing and scheduling on a shoreline with release times[J]. Management Science, 1990, 36: 212-223.
[7] Yu W, Liu Z. Vehicle routing problems on a line-shaped network with release time constraints[J]. Operations Research Letters, 2009, 37: 85-88.
[8] Tsitsiklis J N. Special cases of traveling salesman and repairman problems with time windows[J]. Networks, 1992, 22: 263-282.
[9] Bhattacharya B, Carmi P, Hu Y, Shi Q. Single vehicle scheduling problems on path/tree/cycle networks with release and handling times[J]. Lecture Notes in Computer Science, 2008, 5369: 800-811.
[10] Yu W, Liu Z. Single-vehicle scheduling problems with release and service times on a line[J]. Networks, 2011, 57: 128-134.
[11] Bao X, Liu Z. Approximation algorithms for single vehicle scheduling problems with release and service times on a tree or cycle[J]. Theoretical Computer Science, 2012, 434: 1-10.
[12] Nagamochi H, Mochizuki K, Ibaraki T. Complexity of the single vehicle scheduling problems on a graphs[J]. Information Systems and Operations Research, 1997, 35: 256-276.

[1]	黄辉, 梁星, 李梦想, 张娟. 应急物资联合配送决策研究[J]. 运筹与管理, 2021, 30(6): 48-54.
[2]	吴晨晨, 王丽, 徐春明, 徐大川. 鲁棒动态设施选址问题的近似算法[J]. 运筹与管理, 2020, 29(5): 61-66.
[3]	汪洪涛, 张翔, 王珂. 1996~2017年《Operations Research》期刊发文统计分析[J]. 运筹与管理, 2020, 29(2): 229-239.
[4]	井彩霞, 吴瑞强, 贾兆红. 并行分批排序综述[J]. 运筹与管理, 2020, 29(1): 223-239.
[5]	王诺, 丁凯, 吴迪, 吴暖. 面向远海岛礁群的双向物流网络规划[J]. 运筹与管理, 2019, 28(6): 118-128.
[6]	林鑫, 邵乾虔, 杨珍花, 徐奇, 靳志宏. 基于实际路网情境的配送车辆调度优化[J]. 运筹与管理, 2019, 28(3): 13-23.
[7]	陈江涛, 吕建秋. 基于知识图谱的运筹学发展现状及趋势研究[J]. 运筹与管理, 2019, 28(1): 194-199.
[8]	张萌,王能民. 重大事故规避的危险品运输车辆路径优化研究[J]. 运筹与管理, 2018, 27(8): 1-9.
[9]	王星, 徐大川. 软容量约束带随机需求的设施选址问题的近似算法[J]. 运筹与管理, 2018, 27(4): 35-38.
[10]	高沛然, 张金隆, 艾学轶, 李明, 马自香. PLS-DEMATEL方法及其应用研究——以组织敏捷性的IT影响因素分析为例[J]. 运筹与管理, 2018, 27(3): 126-132.
[11]	郭小威, 李保刚, 滕克难. 基于可用度的复杂结构装备检修时机决策模型[J]. 运筹与管理, 2018, 27(2): 11-14.
[12]	董锋, 树琳, 李靖云, 乔均. 产学研协同创新效率及提升路径研究[J]. 运筹与管理, 2018, 27(10): 185-192.
[13]	张源凯, 孙丽君, 胡祥培. 成品油配送多车舱车辆指派及路径优化问题研究[J]. 运筹与管理, 2017, 26(7): 1-9.
[14]	王道平, 徐展, 杨岑. 基于两阶段启发式算法的物流配送选址-路径问题研究[J]. 运筹与管理, 2017, 26(4): 70-75.
[15]	韩伟一. 一种基于虚拟决策单元的排序方法的完善和扩展[J]. 运筹与管理, 2017, 26(11): 65-69.

线形网络上单台车辆分群调度问题

Single Vehicle Scheduling Problems with Cluster and Release Time Constraints on a Line

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics