计算机科学 ›› 2015, Vol. 42 ›› Issue (6): 204-209.doi: 10.11896/j.issn.1002-137X.2015.06.043
周慧,周良,丁秋林
ZHOU Hui, ZHOU Liang and DING Qiu-lin
摘要: 针对物流配送中动态车辆路径优化问题,综合考虑动态需求、路网影响、车辆共享、时间窗以及客户满意度,建立了多目标动态数学规划模型,该模型能更好地描述现代物流配送问题。同时,提出一种两阶段求解策略,第一阶段采用多目标混合粒子群优化算法获取预优化阶段Pareto最优解,采用改进的粒子状态更新策略并融合模拟退火操作提升粒子群搜索性能,采用自适应网格技术保持解的分布性;第二阶段对客户的需求变化采用贪婪插入和变邻域搜索进行实时路径调整。实验表明,该算法在解空间中有更好的探寻能力,并能快速收敛到全局最优,满足动态路径优化实时性要求。
[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] Muoz-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! |
|