时间依赖网络城市物流车辆调度的模型及算法

doi:10.3969/j.issn.1007-7375.e17-4077

工业工程 ›› 2017, Vol. 20 ›› Issue (4): 18-24.doi: 10.3969/j.issn.1007-7375.e17-4077

时间依赖网络城市物流车辆调度的模型及算法

刘兰芬, 杨信丰

兰州交通大学交通运输学院, 甘肃兰州 730070

收稿日期:2017-03-31 出版日期:2017-08-30 发布日期:2017-09-08
作者简介:刘兰芬(1980-),女,河南省人,讲师,硕士,主要研究方向为物流管理等.
基金资助:
国家自然科学基金资助项目（71361018，71671079）；陇原青年创新创业人才资助项目；兰州交通大学青年基金资助项目（2014028）

Model and Algorithm of Vehicle Routing Problem for Urban Logistics in Time-Dependent Network

LIU Lanfen, YANG Xinfeng

School of Traffic & Transportation Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China

Received:2017-03-31 Online:2017-08-30 Published:2017-09-08

摘要/Abstract

摘要： 在城市配送中，车辆在不同时间段通过相同路径的行驶时间可能不同，时间依赖网络能更好地刻画城市物流车辆调度的实际特征，解决时间依赖条件下的城市物流车辆调度优化问题具有更强的实际应用意义。文在分析时间依赖网络车辆行驶时间的基础上，综合考虑顾客及物流公司两方面要求，以总配送时间、使用车辆数最小及客户满意度最大为目标，建立多目标时间依赖网络城市物流车辆调度模型；设计了遗传算法对该模型进行求解，并进行了算例研究，算例分析表明本模型在城市物流车辆调度方面是合理可行的，设计的算法是有效的。

关键词: 物流工程, 车辆调度问题, 时间依赖网络, 多目标, 遗传算法

Abstract: The required travel time in a path may differ from time to time in city delivery. The actual characteristics of vehicle routing can be better described in time-dependent network. It is of more practical significance to solve the problem of urban logistics vehicle routing optimization in time-dependent condition. On the basis of analyzing the vehicle travel time in time-dependent network, both sides of customers and logistics company requirements are considered and a multi-objective vehicle scheduling model in time-dependent network is formulated to minimize total delivery time and the number of vehicles and maximize the customer satisfaction. Then a genetic algorithm is designed to solve the model, upon an analysis by using an example. The simulation results show that the model is feasible and the algorithm effective in urban logistics vehicle scheduling.

Key words: logistics engineering, vehicle routing problem, time-dependent network, multi-objective, genetic algorithm

中图分类号:

F252

刘兰芬, 杨信丰. 时间依赖网络城市物流车辆调度的模型及算法[J]. 工业工程, 2017, 20(4): 18-24.

LIU Lanfen, YANG Xinfeng. Model and Algorithm of Vehicle Routing Problem for Urban Logistics in Time-Dependent Network[J]. Industrial Engineering Journal , 2017, 20(4): 18-24.

参考文献

[1] 穆东, 王超, 王胜春, 等. 基于并行模拟退火算法求解时间依赖型车辆路径问题[J]. 计算机集成制造系统, 2015, 21(6): 1626-1636.MU Dong, WANG Chao, WANG Shengchun, et al. Solving TDVRP based on parallel-simulated annealing algorithm[J]. Computer Integrated Manufacturing Systems, 2015, 21(6): 1626-1636.
[2] MALANDRAKI C, DASKIN M S. Time dependent vehicle routing problems: formulations, properties and heuristic algorithms[J]. Transportation Science, 1992, 26(3), 185-200.
[3] ICHOUA S, GENDREAU M, POTVIN J Y. Vehicle dispatching with time-dependent travel times[J]. European Journal of Operational Research, 2003, 144(2): 379-396.
[4] HAGHANI A, JUNG S. A dynamic vehicle routing problem with time-dependent travel times[J]. Computers & Operations Research, 2005, 32(11): 2959-2986.
[5] CHEN H K, HSUEH C F, CHANG M S. The real-time time-dependent vehicle routing problem[J]. Transportation Research Part E Logistics & Transportation Review, 2006, 42(5): 383-408.
[6] LECLUYSE C, SÖRENSEN K, PEREMANS H. A network-consistent time-dependent travel time layer for routing optimization problems[J]. European Journal of Operational Research, 2013, 226(3): 395-413.
[7] 李春霞, 张思林, 庞明宝. 基于时间依赖网络的车辆调度问题研究[J]. 交通科技, 2011, 244(1): 104-107.LI Chunxia, ZHANG Silin, PANG Mingbao. Study of vehicle scheduling problem in time-dependent[J]. Transportation Science & Technology, 2011, 244(1): 104-107.
[8] TAS D, DELLAERT N, VAN WOENSEL T, et al. The time-dependent vehicle routing problem with soft time windows and stochastic travel times[J]. Transportation Research Part C Emerging Technologies, 2014, 48: 66-83.
[9] 李宇飞. 基于时间依赖网络的军事物流配送路径优化问题研究[D]. 北京: 北京交通大学, 2016.LI Yufei. Research on military logistics distribution routing optimization based on time dependent network[D]. Beijing: Beijing Jiaotong University, 2016.
[10] RINCON-GARCIA N, WATERSON B, CHERRETT T. A hybrid metaheuristic for the time-dependent vehicle routing problem with hard time windows[J]. International Journal of Industrial Engineering Computations, 2016, 8(1): 141-160.
[11] ALINAGHIAN M, ZAMANLOU K, SABBAGH M S. A bi-objective mathematical model for two-dimensional loading time-dependent vehicle routing problem[J/OL]. (2017-02-08). https://link.springer.com/article/10.1057/s41274-016-0151-x.
[12] HUANG Y X, ZHAO L, VAN WOENSEL T, et al. Time-dependent vehicle routing problem with path flexibility[J]. Transportation Research Part B Methodological, 2017, 95: 169-195.
[13] 杨信丰, 杨庆丰. 随机车辆路径问题的模型及其算法[J]. 交通运输系统工程与信息, 2006, 6(4): 75-80.YANG Xinfeng, YANG Qingfeng. Model and algorithm of vehicle routing problem with stochastic travel time[J]. Journal of Transportation Systems Engineering and Information Technology, 2006, 6(4): 75-80.

[1]	张正敏, 管在林, 岳磊. 基于Lévy Flight的混合GA在柔性作业车间调度问题中的性能分析[J]. 工业工程, 2021, 24(4): 83-92.
[2]	王晓军, 王博, 晋民杰, 杨春霞, 白新利. 改进多种群遗传算法的AutoStore系统多AGV调度优化[J]. 工业工程, 2021, 24(4): 112-118,167.
[3]	王莹莹, 吴立云. 基于改进NSGA-II的多项目多技能人力资源调度研究[J]. 工业工程, 2021, 24(3): 130-138.
[4]	曾创锋, 刘建军, 陈庆新, 毛宁. 求解一类无关并行机调度的遗传迭代贪心算法[J]. 工业工程, 2021, 24(2): 110-118.
[5]	黄露, 纪延光. 考虑顾客延误损失的配送中心选址双层规划问题研究[J]. 工业工程, 2021, 24(2): 141-147.
[6]	王冰怡, 张锦. 考虑网点共享与变更的多级快递网点选址问题[J]. 工业工程, 2021, 24(2): 155-165.
[7]	马跃如, 文铮, 易丹. 考虑老年人满意度的多目标居家养老护理员路径优化[J]. 工业工程, 2021, 24(1): 74-81,103.
[8]	刘雪红, 张涛, 彭兆, 王磊. 面向医疗器械企业灭菌工艺的不同容量平行机批调度[J]. 工业工程, 2021, 24(1): 82-89.
[9]	王玖河, 高辉, 刘欢. 基于遗传算法的共享助力车调度问题研究[J]. 工业工程, 2021, 24(1): 90-96.
[10]	吴斌, 宋琰, 程晶, 董敏. 基于密度峰值聚类的VRPTW问题研究[J]. 工业工程, 2020, 23(5): 58-66,74.
[11]	李博威, 户佐安, 贾叶子, 唐诗韵. 带软时间窗的同时取送货车辆路径问题研究[J]. 工业工程, 2020, 23(5): 75-81.
[12]	王苏林, 邱菲尔, 陈凡, 刘川昆, 鹿腾, 王芷芸. 基于贪心遗传的地下物流节点选择规划研究[J]. 工业工程, 2020, 23(5): 88-95.
[13]	侯艳, 黄康焕, 张亿仙, 伍乃骐. 原油一次加工过程的多目标调度优化[J]. 工业工程, 2020, 23(4): 131-139.
[14]	王泽, 杨信丰, 刘兰芬. 考虑电量消耗的车辆调度优化研究[J]. 工业工程, 2020, 23(4): 140-147.
[15]	曾垂飞, 刘建军, 陈庆新, 毛宁. 装配作业车间分批调度问题的算法对比[J]. 工业工程, 2020, 23(4): 174-182.

时间依赖网络城市物流车辆调度的模型及算法

Model and Algorithm of Vehicle Routing Problem for Urban Logistics in Time-Dependent Network

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价