面向快递同城运输的车辆路径问题研究

doi:10.3969/j.issn.1007-7375.2019.04.009

工业工程 ›› 2019, Vol. 22 ›› Issue (4): 58-63.doi: 10.3969/j.issn.1007-7375.2019.04.009

面向快递同城运输的车辆路径问题研究

江海, 陈峰

上海交通大学工业工程与管理系, 上海 200240

收稿日期:2018-11-12 出版日期:2019-08-31 发布日期:2019-08-23
作者简介:江海(1993-),男,浙江省人,硕士研究生,主要研究方向为物流与供应链优化
基金资助:
国家自然科学基金资助项目（71672115）

A Study of Vehicle Routing Problem for Urban Transport of Express

JIANG Hai, CHEN Feng

Department of Industrial Engineering and Management, Shanghai Jiao Tong University, Shanghai 200240, China

Received:2018-11-12 Online:2019-08-31 Published:2019-08-23

摘要/Abstract

摘要： 为降低运输成本，研究了快递同城运输中的车辆路径问题。建立多车型，含时间窗约束、容量约束、车辆限行约束，并考虑错峰交货的，以最小化运输成本为目标的混合整数规划模型。提出以点到点集的距离之和作为邻域搜索优先指标的构造性启发式算法，设计了基于“路径−；车型对”的列生成算法，初始列由启发式算法求得。实验结果显示，对于120个点的大规模问题，列生成算法只需175秒就能得到近似最优解，验证了该算法的有效性及对一定规模内快递同城运输问题的适用性。

关键词: 同城运输, 车辆路径问题, 启发式算法, 列生成

Abstract: The problem for urban transport of express is essentially a vehicle routing problem. A mixed-integer programming with the objective of minimum cost is built, which includes the constraints of capacity, time windows, vehicle restriction and it also considers staggering the delivery time. A constructive heuristics is proposed and it takes the distance from one point to the set of points as the priority index for neighborhood search. A column generation algorithm based on pairs of "route-vehicle" is designed and the initial columns are solved by the heuristics. The experimental results show that the approximate optimal solution can be obtained in 175 seconds for the large-scale problem with up to 120 points, which proves the effectiveness of the algorithm and its applicability to VRP for urban transport of express within a certain scale.

Key words: urban transport, vehicle routing problem, heuristics, column generation

中图分类号:

O224

江海, 陈峰. 面向快递同城运输的车辆路径问题研究[J]. 工业工程, 2019, 22(4): 58-63.

JIANG Hai, CHEN Feng. A Study of Vehicle Routing Problem for Urban Transport of Express[J]. Industrial Engineering Journal , 2019, 22(4): 58-63.

参考文献

[1] DANTZIG G B, RAMSER J H. The truck dispatching problem[J]. Management Science, 1959, 6(1):80-91
[2] LAPORTE G. The vehicle routing problem:an overview of exact and approximate algorithms[J]. European Journal of Operational Research, 1992, 59(3):345-358
[3] EKSIOGLU B, VURAL A V, REISMAN A. The vehicle routing problem:a taxonomic review[J]. Computers & Industrial Engineering, 2009, 57(4):1472-1483
[4] 张智海, 吴星玮. 带时间窗车辆路径问题的并行遗传算法[J]. 工业工程, 2007, 10(3):111-114 ZHANG Zhihai, WU Xingwei. Parallel genetic algorithm for vehicle routing problem with time window[J]. Industrial Engineering Journal, 2007, 10(3):111-114
[5] 张文博, 苏秦, 程光路. 基于动态需求的带时间窗的车辆路径问题[J]. 工业工程与管理, 2016, 21(6):68-74 ZHANG Wenbo, SU Qin, CHENG Guanglu. Vehicle routing problem with time windows based on dynamic demands[J]. Industrial Engineering and Management, 2016, 21(6):68-74
[6] LUO J, CHEN M R. Multi-phase modified shuffled frog leaping algorithm with extremal optimization for the MDVRP and the MDVRPTW[J]. Computers & Industrial Engineering, 2014, 72:84-97
[7] 王晓博, 李一军. 多车型单配送中心混合装卸车辆路径问题研究[J]. 系统工程学报, 2010, 25(5):629-636 WANG Xiaobo, LI Yijun. Study on multi-type vehicles and single centre vehicle routing problem with backhauls[J]. Journal of Systems Engineering, 2010, 25(5):629-636
[8] CATTARUZZA D, ABSI N, FEILLET D, et al. Vehicle routing problems for city logistics[J]. European Journal on Transportation and Logistics, 2017, 6(1):51-79
[9] MALANDRAKI C, DASKIN M S. Time dependent vehicle routing problems:formulations, properties and heuristic algorithms[J]. Transportation Science, 1992, 26(3):185-200
[10] DONATI A V, MONTEMANNIA R, CASAGRANDEA N, et al. Time dependent vehicle routing problem with a multi ant colony system[J]. European Journal of Operational Research, 2008, 185(3):1174-1191
[11] GENDREAU M, GUERTIN F, POTVIN J Y, et al. Parallel tabu search for real-time vehicle routing and dispatching[J]. Transportation Science, 1999, 33(4):381-390
[12] FLEISCHMANN B, GNUTZMANN S, SANDVOB E. Dynamic vehicle routing based on online traffic information[J]. Transportation Science, 2004, 38(4):420-433
[13] CHEN H K, HSUEH C F, CHANG M S. The real-time time-dependent vehicle routing problem[J]. Transportation Research Part E, 2006, 42(5):383-408
[14] MAMASIS K, MINIS I, DIKAS G. Managing vehicle breakdown incidents during urban distribution of a common product[J]. Journal of the Operational Research Society, 2013, 64(6):925-937
[15] MINIS I, MAMASIS K, ZEIMPEKIS V. Real-time management of vehicle breakdowns in urban freight distribution[J]. Journal of Heuristics, 2012, 18(3):375-400
[16] 李宏. 城市冷链物流配送车辆路径问题的研究[D]. 长沙:长沙理工大学, 2006. LI Hong. Research on urban vehicle routing problem for cold chain logistics[D]. Changsha:Changsha University of Science & Technology, 2006.
[17] FEILLET D, DEJAX P, GENDREAU M, et al. An exact algorithm for the elementary shortest path problem with resource constraints:application to some vehicle routing problems[J]. Networks, 2004, 44(3):216-229

面向快递同城运输的车辆路径问题研究

A Study of Vehicle Routing Problem for Urban Transport of Express

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	闫军, 常乐, 王璐璐, 赵彤. 带时间窗的同时取送货车辆路径问题求解算法[J]. 工业工程, 2021, 24(5): 72-76.
[2]	曹振宇, 蒋阳升, 罗孝羚, 杨洁, 张姚. 中小城市直达公交网络优化[J]. 工业工程, 2020, 23(6): 117-123.
[3]	李博威, 户佐安, 贾叶子, 唐诗韵. 带软时间窗的同时取送货车辆路径问题研究[J]. 工业工程, 2020, 23(5): 75-81.
[4]	朱向, 向延平. 多车多件货物平衡装载优化研究[J]. 工业工程, 2020, 23(3): 123-131.
[5]	芦娟, 夏扬坤, 邹安全, 符卓, 王松, 魏占国, 符瑛. 带装载能力的需求依背包拆分车辆路径问题[J]. 工业工程, 2019, 22(6): 67-73.
[6]	冯春, 秦冰芳, 叶露. 共享电动车电池配送问题研究[J]. 工业工程, 2019, 22(3): 52-56.
[7]	陈炫锐, 陈庆新, 毛宁. 板式家具企业的订单组批问题研究[J]. 工业工程, 2019, 22(2): 96-102.
[8]	户佐安, 贾叶子, 李博威, 刘陆. 考虑客户满意度的车辆路径优化研究[J]. 工业工程, 2019, 22(1): 100-107.
[9]	伊雅丽. 研发型企业多项目人力资源调度研究——基于蚁群优化的超启发式算法[J]. 工业工程, 2018, 21(4): 104-109.
[10]	黄锦钿, 黄伟, 郑耿灶. 加工时间存在双重约束的批调度模型及算法[J]. 工业工程, 2017, 20(2): 78-85.
[11]	周娜, 舒帆, 金佩卿. 基于混合启发式算法的设备混合布局问题[J]. 工业工程, 2017, 20(1): 77-82.
[12]	蓝海燕. 基于优化模型求解方法的多级供应链生产-库存研究进展与趋势[J]. 工业工程, 2016, 19(6): 9-16.
[13]	何梦莹, 徐梅, 张宁波, 晏福. 基于启发式算法的乘用车物流运输问题分析[J]. 工业工程, 2015, 18(5): 141-147.
[14]	贺政纲，刘沙. 考虑均衡负载的车辆路径问题及算法设计[J]. 工业工程, 2015, 18(4): 140-145.
[15]	陈震1，徐丽萍2. 碳政策下货运企业运营成本比较分析[J]. 工业工程, 2015, 18(3): 55-62.