带工作时间与时间窗的开放式车辆路径问题

doi:10.3969/j.issn.1000-3428.2012.04.006

计算机工程 ›› 2012, Vol. 38 ›› Issue (04): 17-19.doi: 10.3969/j.issn.1000-3428.2012.04.006

带工作时间与时间窗的开放式车辆路径问题

潘立军 ^1,2，符卓 ¹，刘喜梅 ³

(1. 中南大学交通与运输工程学院，长沙 410075；2. 湖南工程学院经济管理学院，湖南湘潭 411104； 3. 湖南理工职业技术学院科研处，湖南湘潭 411104)

收稿日期:2011-08-01 出版日期:2012-02-20 发布日期:2012-02-20
作者简介:潘立军(1977－)，男，讲师、博士研究生，主研方向：物流系统优化；符卓，教授、博士生导师；刘喜梅，讲师、硕士
基金项目:
国家自然科学基金资助项目(70671108)；湖南省教育厅基金资助项目(10C0558)

Open Vehicle Routing Problem with Working Time and Time Windows

PAN Li-jun ^1,2, FU Zhuo ¹, LIU Xi-mei ³

(1. School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China; 2. School of Economics and Management, Hunan Institute of Engineering, Xiangtan 411104, China; 3. Scientific Research Office, Hunan Vocational Institute of Technology, Xiangtan 411104, China)

Received:2011-08-01 Online:2012-02-20 Published:2012-02-20

摘要/Abstract

摘要： 在BtoC电子商务物流配送活动中，配送公司外包车辆和配送人员上班具有时间限制。为求解带工作时间与时间窗约束的开放式车辆路径问题(OVRPTWWT)，构建其混合整数规划模型，给出一种求解该问题的非代际克隆选择算法，对算法中抗体的更新与抑制策略进行改进，设计出新的克隆选择方法。通过实验验证了该模型与OVRPTWWT非代际克隆选择算法的有效性。

关键词: 开放式车辆路径问题, 时间窗, 工作时间, 人工免疫, 克隆选择, 非代际

Abstract: In BtoC e-commerce logistics distribution activities, many distribution companies using outsourcing vehicles and the drivers have working time limit. On the basis of this, this paper proposes an Open Vehicle Routing Problem with Time Windows and Working Time (OVRPTWWT), and constructs its mixed integer planning model. A clonal selection algorithm for OVRPTWWT is proposed, it improves the antibodies updating procedure, restraining tactics and designs a new clonal selection method for the algorithm. An example verifies the efficiency of the model and algorithm.

Key words: Open Vehicle Routing Problem(OVRP), time windows, working time, artificial immune, clonal selection, non-generational

中图分类号:

U491

潘立军, 符卓, 刘喜梅. 带工作时间与时间窗的开放式车辆路径问题[J]. 计算机工程, 2012, 38(04): 17-19.

BO Li-Jun, FU Zhuo, LIU Chi-Mei. Open Vehicle Routing Problem with Working Time and Time Windows[J]. Computer Engineering, 2012, 38(04): 17-19.

参考文献

[1] 李三彬, 柴玉梅, 王黎明. 需求可拆分的开放式车辆路径问题研究[J]. 计算机工程, 2011, 37(6): 168-171.
[2] Sariklis D, Powell S. A Heuristic Method for the Open Vehicle Routing Problem[J]. Journal of the Operational Research Society, 2000, 51(5): 564-573.
[3] Brandao J. A Tabu Search Algorithm for the Open Vehicle Routing Problem[J]. European Journal of Operational Research, 2004, 157(1): 552-564.
[4] 符卓. 带装载能力约束的开放式车辆路径问题及其禁忌搜索算法研究[J]. 系统工程理论与实践, 2004, 24(3): 123-128.
[5] Fu Z, Eglese R, Li Lyo. A New Tabu Search Heuristic for the Open Vehicle Routing Problem[J]. Journal of the Operational Research Society, 2005, 56(3): 267-274.
[6] Fu Z, Eglese R, Li Lyo. Corrigendum: A New Tabu Search Heuristic for the Open Vehicle Routing Problem[J]. Journal of the Operational Research Society, 2006, 57(8): 1018-1018.
[7] Tarantilis C, Ioannou G, Kiranoudis C T, et al. A Threshold Accepting Approach to the Open Vehicle Routing Problem[J]. RAIRO Operations Research, 2004, 38(4): 345-360.
[8] Pan Lijun, Fu Z. A Clone Selection Algorithm for the Open Vehicle Routing Problem[C]//Proc. of IEEE WGEC’09. [S. 1.]: IEEE Perss, 2009: 786-790.
[9] Burnet F M. Clonal Selection Theory of Acquired Immunity[M]. [S. 1.]: Cambridge University Press, 1959.
[10] de C L N, Von Z F J. Learning and Optimization Using the Clonal Selection Principle[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(3): 239-251.
[11] 刘若辰, 杜海峰, 焦李成. 免疫多克隆策略[J]. 计算机研究与发展, 2004, 41(4): 571-576.
[12] Pankratz G. A Grouping Genetic Algorithm for the Pickup and Delivery Problem with Time Windows[C]//Proc. of OR’05. 2005: 21-41.
[13] 潘立军, 符卓. 求解带时间窗取送货问题的遗传算法[J]. 系统工程理论与实践, 2012, 32(1): 120-126.

[1]	张艺, 周雯, 梁意文, 谭成予. 基于数字微分的函数化树突状细胞算法模型[J]. 计算机工程, 2020, 46(9): 54-60.
[2]	张玲, 张建伟, 桑永宣, 王博, 侯泽翔. 基于随机森林与人工免疫的入侵检测算法[J]. 计算机工程, 2020, 46(8): 146-152.
[3]	张阳,李雄飞. 基于时间窗口的舆情异动量化模型[J]. 计算机工程, 2019, 45(3): 315-320.
[4]	吴建辉,杨永舒,陈华,张小刚. 免疫双向蛙跳算法及其在多峰函数优化中的应用[J]. 计算机工程, 2018, 44(9): 184-191.
[5]	王劲松,李军燕,张洪玮. 基于IPv6的大规模网络异常流量检测系统设计[J]. 计算机工程, 2018, 44(10): 14-21.
[6]	郭小波,李松涛,张德贤. 基于联合退避-功率感知机制的物联网节点信息防碰撞算法[J]. 计算机工程, 2017, 43(6): 46-52.
[7]	蔡涛,倪晓蓉,王伟生,牛德姣. 面向大数据系统的检测器快速筛选算法[J]. 计算机工程, 2015, 41(9): 45-50.
[8]	韦炜,全渝娟,卓奕涛,陈学亮,林艳. 基于多阶马尔可夫预测的个性化推荐算法[J]. 计算机工程, 2015, 41(11): 59-66.
[9]	王群,戴秀岳,杨莉. 一种基于直觉模糊理论的P2P动态信任模型 [J]. 计算机工程, 2014, 40(8): 133-137.
[10]	杨春明，张晖，石大文. BBS网络舆情的在线自适应话题演化模型[J]. 计算机工程, 2014, 40(7): 317-321.
[11]	张艳梅,王璐. 适应用户兴趣变化的社会化标签推荐算法研究[J]. 计算机工程, 2014, 40(11): 318-321.
[12]	孙靖杰, 赵建军, 杨利斌, 桑德一, 姚刚. 一种人工免疫分类方法在故障诊断中的应用[J]. 计算机工程, 2013, 39(8): 208-214.
[13]	王连锋, 宋建社, 曹继平, 叶庆. 带硬时间窗模糊车辆路径问题的多目标优化[J]. 计算机工程, 2013, 39(4): 9-13,17.
[14]	方贤进，蔡妙琪. 基于人工免疫系统的入侵检测研究[J]. 计算机工程, 2013, 39(11): 136-138,142.
[15]	刘海龙，张凤斌，席亮. 基于协同进化的免疫检测器分布优化算法[J]. 计算机工程, 2013, 39(11): 154-157.

带工作时间与时间窗的开放式车辆路径问题

Open Vehicle Routing Problem with Working Time and Time Windows

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10