基于遗传算法的物流配送路径优化研究.docx

用单亲遗传算法求解配送车辆调度问题的研究郎茂祥(北京交通大学交通运输学院,北京100044)摘要:论文建立了物流配送车辆调度问题的数学模型,并针对传统遗传算法对复杂问题搜索效率低,易陷入“早熟收敛”的缺点,构建了求解物流配送车辆调度问题的单亲遗传算法,并进行了实验运算。运算结果表明,用单亲遗传算法求解物流配送车辆调度问题,可以取得比传统遗传算法更优的结果。关键词:物流配送;车辆调度问题;单亲遗传算法;遗传算法StudyonthePartheno-icAlgorithmforPhysicalDistributionVehicleSchedulingProblemLANGMao-xiang,HUSi-ji(SchoolofTrafficandTransportation,NorthernJiaotongUniversity,Beijing100044,China)Abstract:“ImmatureConvergence”,thispaperestablishedapartheno--:physicaldistribution;vehicleschedulingproblem;pertheno-icalgorithm;icalgorithm1引言随着市场经济的发展和物流专业化水平的提高,物流配送业得到了迅速发展。在物流配送业务中,配送车辆调度问题的涉及面较广,对企业提高服务质量、降低物流成本的影响也较大。在现实生产和生活中,邮政投递问题、公共汽车调度问题、电力调度问题、管道铺设问题、运算机网络拓扑设计问题等都可以抽象为物流配送车辆调度问题。因此,研究物流配送车辆调度问题具有重要的理论和现实意义。物流配送车辆调度问题作为一个NP难题,随着客户数量的增加,可选的车辆路径方案数量将以指数速度急剧增长。因此,用启示式算法求解该问题就成为人们研究的一个重要方向。求解物流配送车辆调度问题的方法很多,常用的有旅行商法、动态规划法[1]、节省法[2]、扫描法[3]、分区配送算法[4]、方案评判法[5]等。遗传算法的显现为求解物流配送车辆调度问题提供了新的工具。Berthold、、Ochi、姜大立、李大卫、李军、谢秉磊、张涛等人都曾利用遗传算法求解物流配送车辆调度问题[6-15],并取得了一些研究成果。作者也尝试采用新的编码方法和遗传算子构造了求解物流配送车辆调度问题的遗传算法,并对文献[9]中的例题进行了实验运算,运算结果表明,虽然利用传统遗传算法能够方便地求得问题的近似最优解,但也暴露出其存在对复杂问题搜索效率低,易陷入“早熟收敛”[16]的缺点。为了提高优化效率和质量,作者构造了求解物流配送车辆调度问题的单亲遗传算法,通过实验运算,取得比传统遗传算法更好的运算结果。2物流配送车辆调度问题的