Computer Science ›› 2015, Vol. 42 ›› Issue (6): 204-209.doi: 10.11896/j.issn.1002-137X.2015.06.043

Previous Articles     Next Articles

Modeling and Optimization for Multi-objective Dynamic Vehicle Routing Problem

ZHOU Hui, ZHOU Liang and DING Qiu-lin   

  • Online:2018-11-14 Published:2018-11-14

Abstract: For the dynamic vehicle routing problem in logistics distribution,this paper built a multi-objective and dynamic mathematical programming model synthesizing dynamic demands,the effects on the road network,vehicle sharing,time window and customer satisfaction.This model can describe modern logistics distribution better.Meanwhile,the paper put forward a two-phase solving strategy for it.In the first phase,multi-objective hybrid particle swarm optimization is adopted to get preliminary Pareto solutions.The algorithm uses the modified updating strategy of particle states and simulated annealing operation to improve the searching performance of particles,and uses adaptive grid technique to maintain the dispersion of solutions.In the next phase,greedy insertion and variable neighborhood search are applied to adjust routes according to the changes in demand.The experimental results show that the two-phase algorithm has better exploring ability in solution space, and it can also converge to the global optimum rapidly,and satisfy the real-time requirement.

Key words: Logistics distribution,Vehicle routing problem,Hybrid particle swarm optimization,Simulated annealing,Pareto solution

[1] 赵燕伟,张景玲,王万良.物流配送的车辆路径优化方法[M].北京:科学出版社,2014 Zhao Yan-wei,Zhang Jing-ling,Wang Wan-liang.Vehicle Routing Optimization for Logistics Distribution[M].Beijing:Science Press,2014
[2] 张建勇,李军,郭耀煌.带模糊预约时间的动态VRP的插入启发式算法[J].西南交通大学学报,2008,3(1):107-113 Zhang Jian-yong,Li Jun,Guo Yao-huang.Insertion Heuristic Algorithm for Dynamic Vehicle Routing Problem with Fuzzy Due-Time[J].Journal of Southwest Jiaotong University,2008,3(1):107-113
[3] 李延晖,刘向.沿途补货的多车场开放式车辆路径问题及蚁群算法[J].计算机集成制造系统,2008,4(3):557-562 Li Yan-hui,Liu Xiang.Modeling and its Ant Colony Algorithm for Multi-depot Open Vehicle Routing Problem with Replenishment on the way[J].Computer Integrated Manufacturing Systems,2008,4(3):557-562
[4] 葛显龙,王旭,邓蕾.基于联合配送的开放式动态车辆路径问题及算法研究[J].管理工程学报,2013,3:60-68 Ge Xian-long,Wang Xu,Deng Lei.Research on Open and Dynamic Vehicle Routing Problems based on Joint Distribution[J].Journal of Industrial Engineering,2013,3:60-68
[5] Muoz-Zavala A,Hernández-Aguirre A,Villa-Diharce E.Particle Evolutionary Swarm Multi-Objective Optimization for Vehicle Routing Problem with Time Windows[M]∥Swarm Intelligence for Multi-objective Problems in Data Mining.Springer Berlin Heidelberg,2009:233-257
[6] 陈森,李孟军,李本先,等.变路网情况下车辆路径问题建模及应用[J].计算机科学,2012,9(2):14-17 Chen Sen,Li Meng-jun,Li Ben-xian,et al.Model and Application of Vehicle Routing Problem with Variable Network Structure[J].Computer Science,2012,9(2):14-17
[7] Wei R,Zhang T,Tang H.An Improved Particle Swarm Optimization Algorithm for Vehicle Routing Problem with Simultaneous Pickup and Delivery[M]∥Information Computing and Applications.Springer Berlin Heidelberg,2011:430-436
[8] 戚铭尧,张金金,任丽.基于时空聚类的带时间窗车辆路径规划算法[J].计算机科学,2014,1(3):218-222 Qi Ming-yao,Zhang Jin-jin,Ren Li.Vehicle Routing Algorithm based on Spatiotemporal Clustering[J].Computer Science,2014,1(3):218-222
[9] Zhang J,Wang W,Zhao Y,et al.Multiobjective quantum evolutionary algorithm for the vehicle routing problem with customer satisfaction[J].Mathematical Problems in Engineering,2012:1-19
[10] 赵燕伟,李川,张景玲,等.一种新的求解多目标随机需求车辆路径问题的算法[J].计算机集成制造系统,2012,8(3):523-530 Zhao Yan-wei,Li Chuan,Zhang Jing-ling,et al.Novel Algorithm for Multi-objective Vehicle Routing Problem with Stochastic Demand[J].Computer Integrated Manufacturing Systems,2012,8(3):523-530
[11] Jensen M T.Reducing the Run-time Complexity of Multiobjective EAs:The NSGA-II and Other Algorithms[J].IEEE Transactions on Evolutionary Computation,2003,7(5):503-515
[12] Hansen P,Mladenovi′ N.Variable neighborhood search:Principles and applications[J].European journal of operational research,2001,0(3):449-467
[13] Marinakis Y,Marinaki M.A Hybrid Particle Swarm Optimization Algorithm for the Open Vehicle Routing Problem[M]∥Swarm Intelligence.Springer Berlin Heidelberg,2012:180-187
[14] Ghannadpour S F,Noori S,Tavakkoli-Moghaddam R,et al.AMulti-objective Dynamic Vehicle Routing Problem with Fuzzy Time Windows:Model,Solution and Application[J].Applied Soft Computing,2014,4:504-527
[15] 易云飞,蔡永乐,董文永,等.求解带容量约束的车辆路径问题的改进伊藤算法[J].计算机科学,2013,0(5):213-216 Yi Yun-fei,Cai Yong-le,Dong Wen-yong,et al.Improved IPO Algorithm for Solving the CVRP[J].Computer Science,2013,0(5):213-216

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .