多模糊时间窗车辆路径问题的建模及求解

交通运输系统工程与信息 ›› 2016, Vol. 16 ›› Issue (6): 182-188.

多模糊时间窗车辆路径问题的建模及求解

闫芳*，王媛媛

重庆交通大学经济与管理学院，重庆400074

收稿日期:2016-05-06 修回日期:2016-06-13 出版日期:2016-12-25 发布日期:2016-12-26
作者简介:闫芳（1985-），女，河南开封人，讲师.
基金资助:
国家自然科学基金/National Natural Science Foundation of China（71401020）；系统科学与企业发展研究中心一般项目/General Project of System Science and Enterprise Development Research Center（Xq15C03）；河北省高等学校人文社会科学研究项目/Humanities and Social Sciences Research Project in Colleges and Universities in Hebei Province（BJ2016057）.

Modeling and Solving the Vehicle Routing Problem with Multiple Fuzzy Time Windows

YAN Fang,WANG Yuan-yuan

School of Economics and Management, Chongqing Jiaotong University, Chongqing 400074, China

Received:2016-05-06 Revised:2016-06-13 Online:2016-12-25 Published:2016-12-26

摘要/Abstract

摘要：

基于现实生活中客户有多个时间段可以接受服务及客户对服务时间要求模糊性的特征，将多个时间窗模糊化，通过服务开始时间的隶属度函数量化客户满意度，在给定一定满意度的基础上，以总成本最小及满意度最大为目标，构建了多模糊时间窗的车辆路径问题模型.根据模型特点，利用惩罚因子处理约束条件，应用粒子群算法求解模型，实验结果表明,该算法能够较好地解决多模糊时间窗的车辆路径问题,并将算例结果与原结果相比较发现，多模糊时间窗车辆路径问题模型能够更加有效地降低配送成本.

关键词: 综合交通运输, 多模糊时间窗, 粒子群, 车辆路径, 顾客满意度

Abstract:

Based on the characteristics that the customers could accept service in multiple time periods and the fuzziness of service time periods, this paper deals with the multiple time windows as fuzzy variables and quantifies the customers’satisfaction level according to the membership function of the beginning time to be served, on the basis of the given acceptable satisfaction level, the vehicle routing model with multiple fuzzy time windows is constructed in order to minimize the total cost and maximize the satisfaction level. Then according to the model characteristics, we use the punishment factors to deal with the constraints and apply particle swarm operations to solve the proposed problems. The experimental results show that the effectiveness of proposed algorithm in solving the vehicle routing problems with multiple fuzzy time windows. Comparing the calculated results with the original results, it is found that our proposed model is more effective to reduce the cost of distribution.

Key words: integrated transportation, multiple fuzzy time windows, particle swarm operations, vehicle routing, customers' satisfaction

中图分类号:

U116.2

闫芳，王媛媛. 多模糊时间窗车辆路径问题的建模及求解[J]. 交通运输系统工程与信息, 2016, 16(6): 182-188.

YAN Fang,WANG Yuan-yuan. Modeling and Solving the Vehicle Routing Problem with Multiple Fuzzy Time Windows[J]. Journal of Transportation Systems Engineering and Information Technology, 2016, 16(6): 182-188.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract19316.shtml

http://www.tseit.org.cn/CN/Y2016/V16/I6/182

参考文献

[1] 马华伟, 叶浩然, 夏维. 允许分割配送的多时间窗车辆调度问题的改进蚁群算法求解[J]. 中国管理科学, 2012 (S1): 43-47. [MA H W, YE H R, XIA W. Improved ant colony algorithm for solving split delivery vehicle routing problem with multiple time windows[J]. Chinese Journal of Management Science, 2012 (S1): 43- 47.]

[2] 闫华, 高黎, 刘国勇, 等. 基于多时间窗的油料保障模型[J]. 计算机应用, 2015, 35(7): 2096-2100. [YAN H, GAO L, LIU G Y, et al. Petrol-oil and lubricants support model based on multiple time windows[J]. Journal of Computer Application, 2015, 35(7): 2096- 2100.]

[3] 马华伟, 左春荣, 杨善林. 多时间窗车辆调度问题的建模与求解[J]. 系统工程学报, 2009, 24(5): 607-613. [MA H W, ZUO C R, YANG S L. Modeling and solving for vehicle routing problem with multiple time windows[J]. Journal of Systems Engineering, 2009, 24 (5): 607-613.]

[4] 黄秋爱, 李珍萍. 多时间窗车辆路径问题的数学模型及算法[J]. 物流技术, 2012, 31(7): 194-196. [HUANG Q A, LI Z P. Mathematical model and algorithm for VRP with multiple time windows[J]. Logistics Technology, 2012, 31(7): 194-196.]

[5] 李珍萍, 赵菲, 刘洪伟. 多时间窗车辆路径问题的智能水滴算法[J]. 运筹与管理, 2015, 24(6): 1-10. [LI Z P, ZHAO F, LIU H W. Intelligent water drops algorithm for vehicle routing problem with multiple time windows[J]. Operations Research and Management Science, 2015, 24 (6): 1-10.]

[6] 李宁, 邹彤, 孙德宝. 带时间窗车辆路径问题的粒子群算法[J]. 系统工程理论与实践, 2004, 24(4): 130-135. [LI N, ZOU T, SUN D B. Particle swarm optimization algorithm for vehicle routing problem with time windows[J]. Systems Engineering Theory and Practice, 2004, 24 (4): 130-135.]

[7] SALMAN A, AHMAD I, AL-MADANI S. Particle swarm optimization for task assignment problem[J]. Microprocessors and Micro systems, 2002, 26(8): 363- 371.

[8] 张良智, 何民爱, 张志海. 基于遗传算法的带时间约束的车辆路径问题优化[J]. 交通运输系统工程与信息, 2006, 6(5): 70-73. [ZHANG L Z, HE M A, ZHANG Z H. Optimizing vehicle routing problem with time constrains based on genetic agorithm[J]. Journal of Transportation Systems Engineering and Information Technology, 2006, 6(5): 70-73.]

[9] 王旭坪, 张凯, 胡祥培. 基于模糊时间窗的车辆调度问题研究[J]. 管理工程学报, 2011, 25(3): 148- 153. [WANG X P, ZHANG K, HU X P. Research of vehicle routing problem based on fuzzy time windows[J]. Journal of Industrial Engineering and Engineering Management, 2011, 25(3): 148-153. ]

[10] 卢冰原, 何力, 程八一. 具有模糊时间窗的有容积约束车辆调度优化问题研究[J]. 计算机应用研究, 2011, 28(9): 3305-3308. [LU B Y, HE L, CHENG B Y. Research on capacitated vehicle scheduling problem with fuzzy time window[J]. Application Research of Computers, 2011, 28(9): 3305-3308.]

[1]	王宁, 张佳蕊, 赵姣. 城际零担货运平台车辆路径问题研究[J]. 交通运输系统工程与信息, 2022, 22(2): 163-177.
[2]	珠兰, 马潇, 刘卓凡. 时间依赖型绿色车辆路径问题研究[J]. 交通运输系统工程与信息, 2021, 21(6): 187-194.
[3]	杨森炎，宁连举，商攀. 基于时空状态网络的电动物流车辆路径优化方法[J]. 交通运输系统工程与信息, 2021, 21(2): 196-204.
[4]	杨华龙，辛禹辰，高浩然. 随机扰动项呈离散分布的库存路径和定价问题的模型与算法[J]. 交通运输系统工程与信息, 2021, 21(2): 211-216.
[5]	左大杰，肖国胜，王孟云. 产业转移背景下西部运输需求的完全分解模型[J]. 交通运输系统工程与信息, 2020, 20(5): 15-20.
[6]	冯涛，彭其渊，陶思宇，陈昕梅. 站城融合模式下既有铁路车站城市功能开发体量预测研究[J]. 交通运输系统工程与信息, 2020, 20(5): 21-28.
[7]	于江霞，杜红亚，罗太波. 基于客户分类的即时配送路径优化研究[J]. 交通运输系统工程与信息, 2020, 20(4): 202-208.
[8]	叶菲菲，杨隆浩，王应明，蓝以信. 基于数据包络分析和扩展置信规则库的交通运输业环境治理成本预测[J]. 交通运输系统工程与信息, 2020, 20(3): 20-27.
[9]	冉昕晨，陈绍宽，陈磊，贾文峥. 考虑客流空间分布的地铁列车节能时刻表优化方法[J]. 交通运输系统工程与信息, 2020, 20(3): 103-110.
[10]	周晓晔，崔瑶，何亮，马小云，王思聪. 基于地铁—货车联运的物流配送路径优化[J]. 交通运输系统工程与信息, 2020, 20(3): 111-117.
[11]	骆晨，李想，钟林峰，胡姗姗. 基于家庭属性差异的大学生出行方式选择行为研究[J]. 交通运输系统工程与信息, 2020, 20(3): 227-232.
[12]	诸立超，刘昭然. 托运人在不同时空下的选择行为差异揭示[J]. 交通运输系统工程与信息, 2020, 20(1): 27-32.
[13]	项昀，徐铖铖，于维杰，华雪东，王炜. 基于人口迁徙大数据的城市对外交通客运方式优势出行距离研究[J]. 交通运输系统工程与信息, 2020, 20(1): 241-246.
[14]	申婵，崔洪军. 基于可靠性最短路的实时定制公交线路优化研究[J]. 交通运输系统工程与信息, 2019, 19(6): 99-104.
[15]	马冰山，胡大伟，陈希琼，胡卉. 半开放式的多配送中心纯电动车辆路径优化问题[J]. 交通运输系统工程与信息, 2019, 19(6): 199-205.