• • 上一篇    

基于嵌套启发式算法的集中通勤接送服务车次分配与调度优化

何万里1, 董纪阳2   

  1. 1. 大连民族大学理学院, 大连 116650;
    2. 东北财经大学管理科学与工程学院, 大连 116023
  • 收稿日期:2021-06-16 修回日期:2021-12-07 发布日期:2022-08-31
  • 通讯作者: 董纪阳,Email:djyang@dufe.edu.cn.
  • 基金资助:
    辽宁省教育厅科学研究项目(LN2020J05),大连市社科院重大调研课题(2020dlsky031).

何万里, 董纪阳. 基于嵌套启发式算法的集中通勤接送服务车次分配与调度优化[J]. 系统科学与数学, 2022, 42(7): 1820-1836.

HE Wanli, DONG Jiyang. Vehicle Routing and Scheduling Optimization of Centralized Commuting Service Based on Nested Heuristic Algorithm[J]. Journal of Systems Science and Mathematical Sciences, 2022, 42(7): 1820-1836.

Vehicle Routing and Scheduling Optimization of Centralized Commuting Service Based on Nested Heuristic Algorithm

HE Wanli1, DONG Jiyang2   

  1. 1. College of Science, Dalian Minzu University, Dalian 116650;
    2. School of Management Science and Engineering, Dongbei University of Finance and Economics, Dalian 116023
  • Received:2021-06-16 Revised:2021-12-07 Published:2022-08-31
车次分配与调度是交通运输服务行业提供优质服务、节约运营成本的核心技术问题.文章针对集中通勤接送服务中车次分配与调度问题,建立了以最小化成本为目标的0-1整数规划模型,刻画了问题的多目标抵达地、多车协作和多行程车次等特征,并设计了一种嵌套启发式算法求解模型,拓展了构造路径方法.算例数值结果表明,文章所设计的模型和算法是有效的、可行的.
Vehicle routing and scheduling is the core technical problem of transportation service industry to provide high-quality service and save cost. In this paper, a 0-1 mixed integer programming model is established to solve the train number allocation and scheduling problem in the business process of centralized commuting service. The characteristics of the problem, such as multi-objective destination, multi vehicle cooperation and multi journey train number, are described. A nested heuristic algorithm solving model is designed and developed, which expands the method of constructing path. The numerical results show that the proposed model and algorithm are effective and feasible.

MR(2010)主题分类: 

()
[1] Ribeiro G M, Laporte G.An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem.Computers&Operations Research, 2012, 39(3):728-735.
[2] 唐加福,董纲,潘震东.免费接送机场服务的多目标规划模型及算法.管理科学学报, 2008, 11(6):35-42.(Tang J F, Dong G, Pan Z D.Multi-objective programming model and algorithm for free transfer airport service.Journal of Management Science, 2008, 11(6):35-42.)
[3] 许争争,唐加福.基于交汇点协作的车辆调度问题的两阶段算法.系统工程学报, 2013,(5):573-580.(Xu Z Z, Tang J F.A two stage algorithm for vehicle scheduling problem based on intersection cooperation.Journal of Systems Engineering, 2013,(5):573-580.)
[4] 刘兴.基于协作的车辆路径问题研究.博士论文.天津大学,天津, 2006.(Liu X.Research on Vehicle Routing Problem Based on collaboration.Doctoral Thesis.Tianjin University, Tianjin, 2006.)
[5] 孔媛.航空票务公司免费机场接送服务中基于最小化成本的车次分配与调度方法研究.博士论文.东北大学,沈阳, 2010.(Kong Y.Research on train number allocation and scheduling method based on minimizing cost in free airport transfer service of air ticketing company.Doctoral Thesis.Northeastern University, Shenyang, 2010.)
[6] 边展,张倩,徐奇,等.带时间窗取送货问题的混合算法.运筹与管理, 2020, 29(2):97-107.(Bian Z, Zhang Q, Xu Q, et al.Hybrid algorithm for pick up and delivery problem with time window.Operations Research and Management, 2020, 29(2):97-107.)
[7] 王芳,饶德坤,游静,等.基于改进蚁群算法的带硬时间窗的接送机场服务路径优化研究.系统科学与数学, 2019, 39(1):76-89.(Wang F, Rao D K, You J, et al.Research on service path optimization of transfer airport with hard time window based on improved ant colony algorithm.Journal of Systems Science and Mathematical Sciences, 2019, 39(1):76-89.)
[8] Manfred, Gronalt, et al.New savings based algorithms for time constrained pickup and delivery of full truckloads.European Journal of Operational Research, 2003, 151(3):520-535.
[9] Brando J.A tabu search algorithm for the open vehicle routing problem.European Journal of Operational Research, 2004, 157(3):552-564.
[10] 李斌,何万里.一种寻找Heston期权定价模型参数的新方法.数量经济技术经济研究, 2015, 32(3):129-146.(Li B, He W L.A new method to find the parameters of Heston option pricing model.Journal of Quantitative and Technical Economics, 2015, 32(3):129-146.)
[11] Solomon M.Algorithms for the vehicle routing and scheduling problems with time windows constraints.Operations Research, 1987, 35(2):254-265.
[12] Braysy O.A reactive variable neighborhood search for the vehicle-routing problem with time windows.Informs Journal on Computing, 2003, 15(4):347-368.
[13] Clarke G, Wright J W.Scheduling of vehicles from a central depot to a number of delivery points.Operations Research, 1964, 12(4):568-581.
[1] 蒋洪迅, 马仁义. 面向靠桥率及道口冲突率的航班-机位指派问题优化模型及其启发式算法研究[J]. 系统科学与数学, 2021, 41(1): 75-98.
[2] 李珍萍,韩倩倩. 考虑商品订购数量的``货到人''仓储系统订单分批问题研究[J]. 系统科学与数学, 2020, 40(8): 1456-1472.
[3] 袁瑞萍,王慧玲,李俊韬,刘凯. 基于移动机器人的订单拣选系统货位优化模型和算法研究[J]. 系统科学与数学, 2020, 40(6): 1050-1060.
[4] 陆少军,裴军,刘心报,杨善林. 考虑恶化和学习效应的多机制造系统智能优化方法[J]. 系统科学与数学, 2019, 39(10): 1597-1608.
[5] 黄文奇;叶涛. 求解等圆Packing问题的完全拟物算法[J]. 系统科学与数学, 2008, 28(8): 993-1001.
[6] 贾振声;朱永津. 一个关于余直径的度条件[J]. 系统科学与数学, 2003, 23(1): 100-108.
阅读次数
全文


摘要