基于遗传算法的物流配送路径优化研究VIP免费

用单亲遗传算法求解配送车辆调度问题的研究郎茂祥（北京交通大学交通运输学院，北京100044）摘要：论文建立了物流配送车辆调度问题的数学模型，并针对传统遗传算法对复杂问题搜索效率低，易陷入“早熟收敛”的缺点，构建了求解物流配送车辆调度问题的单亲遗传算法，并进行了实验计算。计算结果表明，用单亲遗传算法求解物流配送车辆调度问题，可以取得比传统遗传算法更优的结果。关键词：物流配送；车辆调度问题；单亲遗传算法；遗传算法StudyonthePartheno-GeneticAlgorithmforPhysicalDistributionVehicleSchedulingProblemLANGMao-xiang，HUSi-ji（SchoolofTrafficandTransportation，NorthernJiaotongUniversity，Beijing100044，China）Abstract：Thispaperestablishedthemodelofphysicaldistributionvehicleschedulingproblem.Onthebasisofanalyzingtheshortcomingsoftraditionalgeneticalgorithminlowsearchingefficiencyand“ImmatureConvergence”,thispaperestablishedapartheno-geneticalgorithmforsolvingphysicaldistributionvehicleschedulingproblemandmadesomeexperimentalcomputations.Thecomputationalresultshaddemonstratedthatthepartheno-geneticalgorithmhadhigheroptimizingefficiencyandqualitythantraditionalgeneticalgorithminsolvingphysicaldistributionvehicleschedulingproblem.Keywords：physicaldistribution;vehicleschedulingproblem;pertheno-geneticalgorithm;geneticalgorithm1引言随着市场经济的发展和物流专业化水平的提高，物流配送业得到了迅速发展。在物流配送业务中，配送车辆调度问题的涉及面较广，对企业提高服务质量、降低物流成本的影响也较大。在现实生产和生活中，邮政投递问题、公共汽车调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为物流配送车辆调度问题。因此，研究物流配送车辆调度问题具有重要的理论和现实意义。物流配送车辆调度问题作为一个NP难题，随着客户数量的增加，可选的车辆路径方案数量将以指数速度急剧增长。因此，用启发式算法求解该问题就成为人们研究的一个重要方向。求解物流配送车辆调度问题的方法很多，常用的有旅行商法、动态规划法[1]、节约法[2]、扫描法[3]、分区配送算法[4]、方案评价法[5]等。遗传算法的出现为求解物流配送车辆调度问题提供了新的工具。Berthold、Malmborg、Ochi、姜大立、李大卫、李军、谢秉磊、张涛等人都曾利用遗传算法求解物流配送车辆调度问题[6-15]，并取得了一些研究成果。作者也尝试采用新的编码方法和遗传算子构造了求解物流配送车辆调度问题的遗传算法，并对文献[9]中的例题进行了实验计算，计算结果表明，虽然利用传统遗传算法能够方便地求得问题的近似最优解，但也暴露出其存在对复杂问题搜索效率低，易陷入“早熟收敛”[16]的缺点。为了提高优化效率和质量，作者构造了求解物流配送车辆调度问题的单亲遗传算法，通过实验计算，取得比传统遗传算法更好的计算结果。2物流配送车辆调度问题的数学模型物流配送车辆调度问题可以描述为：从某物流中心用多台配送车辆向多个客户送货，每个客户的位置和货物需求量一定，每台配送车辆的载重量一定，其一次配送的最大行驶距离一定，要求合理安排车辆配送路线，使目标函数得到优化，并满足以下条件：（1）每条配送路径上各客户的需求量之和不超过配送车辆的载重量；（2）每条配送路径的长度不超过配送车辆一次配送的最大行驶距离；（3）每个客户的需求必须满足，且只能由一台配送车辆送货。设物流中心有K台配送车辆，每台车辆的载重量为Qk（k=1，2，···，K），其一次配送的最大行驶距离为Dk，需要向L个客户送货，每个客户的货物需求量为qi（i=1，2，···，L），客户i到j的运距为dij，物流中心到各客户的距离为d0j（i、j=1，2，···，L），再设nk为第k台车辆配送的客户数（nk=0表示未使用第k台车辆），用集合Rk表示第k条路径，其中的元素rki表示客户rki在路径k中的顺序为i（不包括物流中心），令rk0=0表示物流中心，若以配送总里程最短为目标函数，则可建立如下物流配送车辆调度问题的数学...