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

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

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

CLC Number:

F252

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.

References

[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]	YAN Jun, CHANG Le, WANG Lulu, ZHAO Tong. A Solution Algorithm for the Problem of Taking Delivery Vehicle Path at the Same Time with Time Window [J]. Industrial Engineering Journal, 2021, 24(5): 72-76.
[2]	ZHANG Zhengmin, GUAN Zailin, YUE Lei. Performance Analysis of Hybrid GA Based on Lévy Flight in Flexible Job-shop Scheduling Problem [J]. Industrial Engineering Journal, 2021, 24(4): 83-92.
[3]	WANG Xiaojun, WANG Bo, JIN Minjie, YANG Chunxia, BAI Xinli. Multi AGV Scheduling Optimization of AutoStore System Based on Improved Multi Population Genetic Algorithm [J]. Industrial Engineering Journal, 2021, 24(4): 112-118,167.
[4]	WANG Yingying, WU Liyun. A Research on Multi-project Multi-skill Human Resource Scheduling Based on Improved NSGA-II [J]. Industrial Engineering Journal, 2021, 24(3): 130-138.
[5]	ZENG Chuangfeng, LIU Jianjun, CHEN Qingxin, MAO Ning. A Genetic Algorithm-Iterative Greedy Algorithm for a Kind of Unrelated Parallel Machine Scheduling Problem [J]. Industrial Engineering Journal, 2021, 24(2): 110-118.
[6]	HUANG Lu, JI Yanguang. A Bi-level Optimization Model for Logistics Distribution Center Location Problem under Customer Delay Cost [J]. Industrial Engineering Journal, 2021, 24(2): 141-147.
[7]	WANG Bingyi, ZHANG Jin. A Multi-level Express Outlets Layout under Network Sharing and Change [J]. Industrial Engineering Journal, 2021, 24(2): 155-165.
[8]	MA Yueru, WEN Zheng, YI Dan. Multi-objective Home-health-care Staff for the Elderly Routing Optimization Considering Elderly Satisfaction [J]. Industrial Engineering Journal, 2021, 24(1): 74-81,103.
[9]	LIU Xuehong, ZHANG Tao, PENG Zhao, WANG Lei. Batch Scheduling of Parallel Machines with Different Capacity for Sterilization Process in Medical Equipment Enterprises [J]. Industrial Engineering Journal, 2021, 24(1): 82-89.
[10]	WANG Jiuhe, GAO Hui, LIU Huan. A Research on Shared Motorcycle Scheduling Problem Based on Genetic Algorithms [J]. Industrial Engineering Journal, 2021, 24(1): 90-96.
[11]	WANG Zhen, GUO Jianquan. Research on Remanufacturing Closed-loop Supply Chain Considering Supply Disruption in Uncertain Environment [J]. Industrial Engineering Journal, 2021, 24(1): 140-146.
[12]	WU Bin, SONG Yan, CHENG Jing, DONG Min. A Research on Vehicle Routing Problems with Time Windows Based on Density Peak Clustering [J]. Industrial Engineering Journal, 2020, 23(5): 58-66,74.
[13]	LI Bowei, HU Zuoan, JIA Yezi, TANG Shiyun. A Research on Vehicle Routing Problem with Simultaneous Pick-up and Delivery and Soft Time Windows [J]. Industrial Engineering Journal, 2020, 23(5): 75-81.
[14]	WANG Sulin, QIU Feier, CHEN Fan, LIU Chuankun, LU Teng, WANG Zhiyun. A Research on Underground Logistics Node Selection Planning Based on Greedy Genetic Algorithm [J]. Industrial Engineering Journal, 2020, 23(5): 88-95.
[15]	HOU Yan, HUANG Kanghuan, ZHANG Yixian, WU Naiqi. A Multi-objective Scheduling Optimization for Crude Oil Operations [J]. Industrial Engineering Journal, 2020, 23(4): 131-139.