开放式多中心需求可拆分VRP及混沌遗传模拟退火算法

doi:10.12005/orms.2022.0014

运筹与管理 ›› 2022, Vol. 31 ›› Issue (1): 92-98.DOI: 10.12005/orms.2022.0014

开放式多中心需求可拆分VRP及混沌遗传模拟退火算法

范厚明, 徐振林, 李阳, 杨翔

大连海事大学交通运输工程学院,辽宁大连 116026

收稿日期:2017-12-27 出版日期:2022-01-25 发布日期:2022-02-11
作者简介:范厚明(1962-),男,山东蓬莱人,博士,教授,博士生导师,研究方向:交通运输规划与管理。
基金资助:
国家自然科学基金资助项目(61473053);辽宁省教育厅科学技术一般项目(L2014196)

Chaos Genetic Simulated Annealing Algorithm for the Open Multi-depot Split Delivery Vehicle Routing Problem

FAN Hou-ming, XU Zhen-lin, LI Yang, YANG Xiang

Dalian Maritime University, Transportation Engineering college, Liaoning Dalian 116026

Received:2017-12-27 Online:2022-01-25 Published:2022-02-11

摘要/Abstract

摘要： 综合考虑客户需求量允许被拆分、配送系统拥有多个配送中心且车辆可就近返回配送中心的运输模式,建立以配送中心日均建设成本、车辆派遣成本、理货成本和油耗成本之和最小为目标的数学模型,并根据问题特征设计了混沌遗传模拟退火算法对问题进行求解。通过对不同规模以及不同类型的算例进行实验,验证了混沌遗传模拟退火算法求解本文问题的有效性。

关键词: 车辆路径问题, 多中心开放式, 需求可拆分, 混沌遗传算法, 模拟退火算法

Abstract: Considering the transportation mode of customer demand to be split, the distribution system with multiple depots and the vehicle can return the nearest depot, the mathematical model finding out of minimal sum of depots’ daily construction cost, vehicles’ fixed cost, tally cost and energy consumption cost is formulated. According to the characters of problem, the chaos genetic simulated annealing algorithm is designed to solve it. The effectiveness of the chaos genetic simulated annealing algorithm to solve this problem studied in this paper is verified by instances on different scale and different types.

Key words: vehicle routing problem, open multi-depot, split delivery, chaos genetic algorithm, simulated annealing algorithm

中图分类号:

N945
TP301.6

范厚明, 徐振林, 李阳, 杨翔. 开放式多中心需求可拆分VRP及混沌遗传模拟退火算法[J]. 运筹与管理, 2022, 31(1): 92-98.

FAN Hou-ming, XU Zhen-lin, LI Yang, YANG Xiang. Chaos Genetic Simulated Annealing Algorithm for the Open Multi-depot Split Delivery Vehicle Routing Problem[J]. Operations Research and Management Science, 2022, 31(1): 92-98.

参考文献

[1] Gulczynski D, Golden B, Wasil E. The multi-depot split delivery vehicle routing problem: an integer programming-based heuristic, new test problems, and computational results[J]. Computers & Industrial Engineering, 2011, 61(3): 794-804.
[2] Gulczynski D, Golden B, Wasil E. The split delivery vehicle routing problem with minimum delivery amounts[J]. Transportation Research Part E Logistics & Transportation Review, 2010, 46(46): 612-626.
[3] Dror M, Trudeau P. Split delivery routing[J]. Naval Research Logistics, 1990, 37(3): 383-402.
[4] Soeanu A, Ray S, Debbabi M, et al. A decentralized heuristic for multi-depot split-delivery vehicle routing problem[C]//IEEE International Conference on Automation and Logistics, Ical 2011, Chongqing, China, 15-16 August. 2011: 70-75.
[5] Ray S, Soeanu A, Berger J, et al. The multi-depot split-delivery vehicle routing problem: model and solution algorithm[J]. Knowledge-Based Systems, 2014, 71: 238-265.
[6] Wang X, Golden B, Wasil E, et al. The min-max split delivery multi-depot vehicle routing problem with minimum service time requirement[J]. Computers & Operations Research, 2016, 71: 110-126.
[7] 徐振林.资源共享型配送路径优化研究[D].大连海事大学,2019.
[8] 殷脂,叶春明.多配送中心物流配送车辆调度问题的分层算法模型[J].系统管理学报,2014(4):602-606.
[9] 葛显龙,许茂增,王伟鑫.基于联合配送的城市物流配送路径优化[J].控制与决策,2016(3):503-512.
[10] 高延峰,许瑛.混沌遗传模拟退火组合算法性能研究[J].计算机应用与软件,2008,25(11):238-240.
[11] Stanojević M, Stanojević B, Vujošević M. Enhanced savings calculation and its applications for solving capacitated vehicle routing problem[J]. Applied Mathematics & Computation, 2013, 219(20): 10302-10312.
[12] Gulczynski D J. Integer programming-based heuristics for vehicle routing problems, Ph.D. thesis, Robert H. Smith School of Business, University of Maryland, USA, 2010.

[1]	闫妍, 张锦, 唐秋宇, 张洪基. 航线联盟下航空货运网络枢纽点选址问题研究[J]. 运筹与管理, 2021, 30(9): 64-72.
[2]	王愚勤, 胡卉, 刘富鑫, 王艳慧, 赵姣, 韩毅. 智能网联下无人车配送路径优化[J]. 运筹与管理, 2021, 30(8): 52-58.
[3]	向婷, 李妍峰. 基于成本和加班时长的双目标家庭护理人员调度问题[J]. 运筹与管理, 2021, 30(8): 233-239.
[4]	张晓楠, 范厚明. 求解带时间窗车辆路径问题的混合Memetic算法[J]. 运筹与管理, 2021, 30(7): 128-135.
[5]	范厚明, 孔靓, 岳丽君. 考虑出口箱进出场及预翻箱的箱位分配与场桥调度协同优化[J]. 运筹与管理, 2021, 30(6): 26-34.
[6]	王新, 王征, 徐伟. 面向多个无人机站点的车辆与无人机联合配送路径问题研究[J]. 运筹与管理, 2021, 30(5): 31-37.
[7]	薛桂琴, 王征. 带客户协同分仓的动态车辆路径问题研究[J]. 运筹与管理, 2021, 30(11): 19-25.
[8]	刘长石, 王松, 罗亮, 邓胜前. 时变路网条件下联合配送的开放式车辆路径问题[J]. 运筹与管理, 2021, 30(11): 26-33.
[9]	陈玉龙, 赖志柱. 不确定条件下的乡村中小学布局优化[J]. 运筹与管理, 2021, 30(11): 65-70.
[10]	林鑫, 邵乾虔, 杨珍花, 徐奇, 靳志宏. 基于实际路网情境的配送车辆调度优化[J]. 运筹与管理, 2019, 28(3): 13-23.
[11]	魏洁, 王佳鑫. 生鲜农产品多配送中心连续选址FCM-ISA算法及应用[J]. 运筹与管理, 2019, 28(11): 85-90.
[12]	张建同, 丁烨. 变邻域模拟退火算法求解速度时变的VRPTW问题[J]. 运筹与管理, 2019, 28(11): 77-84.
[13]	潘立军, 符卓, 刘喜梅. 共享单车再平衡问题及其容差插入启发式算法[J]. 运筹与管理, 2019, 28(10): 26-32.
[14]	徐国勋, 李妍峰, 李军, 徐冠宇. 多类型公共自行车调运问题[J]. 运筹与管理, 2019, 28(1): 116-124.
[15]	俞武扬, 方俊俊. 制造单元布局问题的双目标模型与算法研究[J]. 运筹与管理, 2018, 27(6): 100-106.

开放式多中心需求可拆分VRP及混沌遗传模拟退火算法

Chaos Genetic Simulated Annealing Algorithm for the Open Multi-depot Split Delivery Vehicle Routing Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics