基于混合算法的双向物流路径优化问题的研究.docVIP

基于混合算法的双向物流路径优化问题的研究 　　【摘 要】本文针对双向物流的特点，重点分析研究了车辆配送的策略。为了更好地协调车辆进行路径选择和运输成本间的关系，以及更好地考虑综合因素及实际情况进行节点间的选择，针对双向物流路径问题的研究方法，建立了优化路径的极小化数学模型。最后针对路径优化方法及研究状况，采用了聚类分析及蚁群算法，并经仿真验证，结果合理有效。 　　【关键词】物流配送；双向物流；物流路径优化；蚁群算法；减法聚类 　　Two-way Logistics Path Optimization Problems Based on Clustering Analysis Research 　　LIU Yan-qiu YANG Yong 　　（Shenyang University of Technology， Shenyang Liaoning 110000， China） 　　【Abstract】According to the characteristics of two-way logistics， this paper focus on analysis and research the vehicles distribution. In order to better coordinate the vehicle path selection and the relationship between transport costs， and better conditions for considering comprehensive factors and the choice between nodes， study of two-way logistics path problem method， established the mathematical model of optimal path minimization. Finally based on path optimization method and the research situation， adopted the cluster analysis and the ant colony algorithm， and it has been verified by the simulation， the results reasonable and effective. 　　【Key words】Logistics distribution； Two-way logistics； Logistics path optimization； Ant colony algorithm； Subtraction clustering 　　0 引言 　　物流配送在物流管理中占有重要地位，它是指按照客户的订货需求，在配送中心进行分货、配货，并调度车辆及时为客户配送货物[1]。车辆路径问题（vehicle routing problem，VRP）是车辆配送研究中最核心的问题，一直是组合优化领域的热点和前沿问题[2]，而双向物流路径优化问题（vehicle routing problem with simultaneous delivery and pickup，VRPSDP）是VRP问题中的一个典型，它是指同时带送货取货的物流车辆路径优化问题，既考虑了客户需要的货物从配送中心送到各个客户，又需要把客户需要回送的货物运回到配送中心，要求取货送货同时进行，因此比单向物流问题还要复杂，也是一种NP-hard难题，所以求解复杂度较高，计算量较大。本文在前人研究的基础上通过聚类分析方法和蚁群算法对双向物流路径优化问题进行了求解。 　　1 双向物流配送的数学模型 　　1.1 问题描述 　　双向物流路径优化问题可以这样描述： 　　已知有C个客户点，给定每个客户的坐标点和需求量，货车从配送中心出发，将货物送到各个客户，并同时把客户供应的货物带回到配送中心。车辆应在条件允许下进行服务，当完成任务或者不存在能满足约束条件的情况下，返回配送中心，直到所有的客户的送取货任务完成，整个流程结束。物流路径优化要求在满足约束的条件下，合理安排货车的配送路线，使得运输成本最小。由于运输成本很大程度上是由货车的路径长度决定的，因此本文求解VRPSDP问题的目标函数的最优解就是要求路径最短。 　　1.2 数学模型的建立 　　1.2.1 参数说明 　　1.2.2 数学模型 　　根据上面对VRPSDP问题的描述和已设定的数学参数，加之针对该问题所需要考虑的约束条件，对此问题进行了建模，将服务完所有客户点后所有车辆的行驶总路程定义为目标函 　　2 V