多目标动态车辆路径问题建模及优化.pdf

《多目标动态车辆路径问题建模及优化.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第42卷第6期计算机科学Vo1．42No．62015年6月ComputerScieneeJune2015多目标动态车辆路径问题建模及优化周慧周良丁秋林(南京航空航天大学计算机科学与技术学院南京210016)摘要针对物流配送中动态车辆路径优化问题，综合考虑动态需求、路网影响、车辆共享、时间窗以及客户满意度，建立了多目标动态数学规划模型，该模型能更好地描述现代物流配送问题。同时，提出一种两阶段求解策略，第一阶段采用多目标混合粒子群优化算法获取预优化阶段Pareto最优解，采用改进的粒子状态更新策略并融合模拟

2、退火操作提升粒子群搜索性能，采用自适应网格技术保持解的分布性；第二阶段对客户的需求变化采用贪婪插入和变邻域搜索进行实时路径调整。实验表明，该算法在解空间中有更好的探寻能力，并能快速收敛到全局最优，满足动态路径优化实时性要求。关键词物流配送，车辆路径问题，混合粒子群优化算法，模拟退火，Pareto最优解中图法分类号TP18文献标识码ADOI10．11896／j．issn．1002—137X．2015．6．043ModelingandOptimizationforMulti—objectiveDynamic

3、VehicleRoutingProblemZHOUHuiZHOULiangDINGQiu-lin(CollegeofComputerScienceandTechnology，NanjingUniversityofAeronauticsandAstronautics，Nanjing210016，China)AbstractForthedynamicvehicleroutingprobleminlogisticsdistribution，thispaperbuiltamulti-objectiveanddy

4、—namicmathematica1programmingmode1synthesizingdynamicdemands，theeffectsontheroadnetwork，vehiclesha-ring，timewindowandcustomersatisfaction．Thismodelcandescribemodernlogisticsdistributionbetter．Meanwhile，thepaperputforwardatwo-phasesolvingstrategyforit．Int

5、hefirstphase，multi—objectivehybridparticleswalTnopti—mizationisadoptedtogetpreliminaryParetosolutions．Thealgorithmusesthemodifiedupdatingstrategyofparticlestatesandsimulatedannealingoperationtoimprovethesearchingperformanceofparticles，andusesadaptivegrid

6、tech—niquetomaintainthedispersionofsolutions．Inthenextphase，greedyinsertionandvariableneighborhoodsearchareappliedtoadjustroutesaccordingtothechangesindemand．Theexperimentalresultsshowthatthetwo—phasealgo—rithmhasbetterexploringabilityinsolutionspace，and

7、itcanalsoconvergetotheglobaloptimumrapidly，andsatisfythereal-timerequirement．KeywordsLogisticsdistribution，Vehicleroutingproblem，Hybridparticleswarmoptimization，Simulatedannealing，Paretosolution提出了带补货控制因子的蚁群算法，该模型较好地描述了大1引言区域多仓库多需求点的实际配送需求，但没有考虑随机需求车辆路径问

8、题(VehicleRoutingProblem，VRP)通常可以对路径优化的影响。葛显龙等l_4]引入时间轴概念将动态问题描述为：对一系列装货点和(或)卸货点组织适当的行车路线，转化为静态问题，建立考虑车载率的开放式车辆路径模型，利使车辆有序地通过，在满足一定的约束条件(如货物需求量、用云模型中云滴的随机性与稳定倾向性，改进遗传算法中交发送量、交发货时间、车辆容量等限制)下，达到一定的目标叉与变异概率的设置方式，采用两阶段求解策略对ODVR