环形路网上带有服务时长的在线TSP问题

doi:10.12005/orms.2020.0154

运筹与管理 ›› 2020, Vol. 29 ›› Issue (6): 139-144.DOI: 10.12005/orms.2020.0154

环形路网上带有服务时长的在线TSP问题

樊相宇^1a, 林小果^1b, 武小平^1c

1.西安邮电大学, a.邮政研究院; b.经济与管理学院; c.现代邮政学院,陕西西安 710061

收稿日期:2018-03-02 出版日期:2020-06-25
通讯作者: 林小果(1993-),女,河南,硕士研究生,研究方向:管理科学与工程;武小平(1978-),男,陕西,副教授,博士学位,研究方向:配送路径优化。
作者简介:樊相宇(1960-),男,陕西,教授,学士学位,研究方向:系统工程;通讯作者:林小果(1993-),女,河南,硕士研究生,研究方向:管理科学与工程;武小平(1978-),男,陕西,副教授,博士学位,研究方向:配送路径优化。
基金资助:
不确定视角下快递企业末端配送优化策略研究-以西安市为例(18JK0705);基于网络分区的物流配送碳足迹优化研究(2019JM-369);城市快递网络抗毁性研究—以西安市为例(XDWL1906)

Online TSP Problem with Service Time on the Ring Road Network

FAN Xiang-yu^1a, LIN Xiao-guo^1b, WU Xiao-ping^1c

1. Postal Research Institute, Xi'an University of Posts and Telecommunications, Xi'an 710061, China;
2. College of Economic and Management, Xi'an University of Posts and Telecommunications, Xi'an 710061, China;
3. Modern Postal College, Xi'an University of Posts and Telecommunications, Xi'an 710061, China

Received:2018-03-02 Online:2020-06-25

摘要/Abstract

摘要： 为了提高快递揽件的时效性,需要对快递车辆进行有效调度。针对环形路网上服务时长以及需求无法预知的揽件问题,本文提出了以服务总时间尽可能短为目标的环形路网上带有服务时长的在线旅行商问题。用在线算法分析了此问题竞争比的下界,设计了两个在线算法并分析了各自的竞争比,结果表明服务时长可以改善在线车的性能。最后通过简单算例对两个算法进行说明,本文研究结论可以为环形路网上的快递车辆实时调度提供指导。

关键词: 快递揽件, 旅行商问题, 服务时长, 在线方法, 竞争比

Abstract: In order to improve the timeliness of courier services, it is necessary to dispatch the express vehicles effectively. In order to solve the problem of service time and unpredictable demand on the ring road network,this paper proposes an online traveling salesman problem with service time on the ring road network with the aim of providing the total service time which should be as short as possible. The lower bound of competition ratio of this problem is analyzed by the online algorithm,two online algorithms are designed and their respective competition ratio is analyzed,and the results show that the service time can improve the performance of the online vehicle. At last, the two algorithms are illustrated by a simple example. The conclusions of this paper can provide guidance for the real-time scheduling of express vehicles on the ring road network.

Key words: courier services, traveling salesman problem, service time, online algorithm, competitive ratio

中图分类号:

F224.9

樊相宇, 林小果, 武小平. 环形路网上带有服务时长的在线TSP问题[J]. 运筹与管理, 2020, 29(6): 139-144.

FAN Xiang-yu, LIN Xiao-guo, WU Xiao-ping. Online TSP Problem with Service Time on the Ring Road Network[J]. Operations Research and Management Science, 2020, 29(6): 139-144.

[1]	徐金红, 徐维军, 秦旭. 基于高斯分布的在线采购机制设计及竞争分析[J]. 运筹与管理, 2021, 30(3): 98-103.
[2]	黄学文, 孙榕, 艾亚晴. 招标采购中的采购物品打包模型及其优化算法[J]. 运筹与管理, 2020, 29(9): 18-26.
[3]	马军平, 徐寅峰, 吴腾宇. 有服务时长和服务可选择性的快递车辆调度在线策略研究[J]. 运筹与管理, 2020, 29(1): 38-46.
[4]	徐维军, 董鹏翠, 彭子衿. 基于优惠合同的在线租赁策略设计[J]. 运筹与管理, 2019, 28(3): 183-190.
[5]	张梦颖, 秦进, 梁樑. 包含随机客户的选择性旅行商问题建模及求解[J]. 运筹与管理, 2018, 27(5): 8-14.
[6]	张鹏威, 李英. 考虑充电设施重入的电动汽车旅行商问题研究[J]. 运筹与管理, 2018, 27(2): 54-64.
[7]	马卫民, 张颖, 李刚. 带有交易费用和持有成本的局内采购管理模型竞争分析[J]. 运筹与管理, 2018, 27(1): 171-177.
[8]	吴腾宇,徐寅峰. 带有配额的在线Nomadic旅行商问题[J]. 运筹与管理, 2016, 25(2): 1-6.
[9]	胡茂林,徐维军. 购买价格递减的在线租赁问题策略设计[J]. 运筹与管理, 2015, 24(5): 281-287.
[10]	胡丹, 农庆琴, 方奇志. 单位工件的平行机并行分批在线排序问题的算法[J]. 运筹与管理, 2015, 24(1): 137-141.
[11]	朱莹, 茹少峰, 张文明. 基于在线理论的股票算法交易策略研究[J]. 运筹与管理, 2015, 24(1): 222-230.
[12]	徐金红, 马银戌, 蒋微青. 统计信息下在线反向拍卖的竞争分析[J]. 运筹与管理, 2014, 23(4): 213-218.
[13]	王超, 金淳, 韩庆平. 求解旅行商问题的基于类Kruskal的混合粒子群算法[J]. 运筹与管理, 2014, 23(3): 30-37.
[14]	马卫民, 徐博, 黄卉, 陈香堂. 双人合作的在线雪橇租赁问题[J]. 运筹与管理, 2013, 22(4): 12-19.
[15]	徐寅峰, 曹永峰, 郑斐峰. 单水库在线发电调度策略设计与分析[J]. 运筹与管理, 2011, 20(6): 82-87.

环形路网上带有服务时长的在线TSP问题

Online TSP Problem with Service Time on the Ring Road Network

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics