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

刘艳秋　杨勇

【摘 要】本文针对双向物流的特点，重点分析研究了车辆配送的策略。为了更好地协调车辆进行路径选择和运输成本间的关系，以及更好地考虑综合因素及实际情况进行节点间的选择，针对双向物流路径问题的研究方法，建立了优化路径的极小化数学模型。最后针对路径优化方法及研究状况，采用了聚类分析及蚁群算法，并经仿真验证，结果合理有效。

【关键词】物流配送；双向物流；物流路径优化；蚁群算法；减法聚类

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 VRPSDP模型的求解

本文中求解模型的方法，首先是通过FCM聚类，把需要提供服务的城市进行分类，然后再用蚁群算法在满足约束的情况下对每个分类进行求解最优路径，具体做法如图1所示。

图1 求解流程图

3 实例仿真

为了检验上述双向物流路径优化方法的有效性，本文采用实例数据对其进行性能分析。设车辆从配送中心出发，为各个客户提供服务，配送中心坐标位置是（0km，0km），车辆在满足约束的情况下向 30 个客户配送货物。

首先经matlab仿真得到的30个城市的聚类图如图2所示。

图2 经FCM聚类的城市坐标图

然后经过蚁群算法对每个聚类进行路径优化，得到的车辆配送路径图如图3所示。

图3 车辆配送路线图

4 结论

本文针对双向物流的特点，首先给出了问题的相关描述，然后通过抽象建模，给出了带路程和负载量约束的双向物流路径优化模型。根据给出的VRPSDP问题模型，用基于FCM聚类和蚁群算法的混合算法对模型进行求解。最后通过仿真实验，证明了本文混合算法求解双向物流路径优化问题的的正确性和有效性。

【参考文献】

[1]杨燕霞，伍岳庆，姚宇，等.带时间窗车辆调度问题的启发式算法研究与应用[J].计算机应用，2013，33（S1）：59-61.

[2]谈晓勇，刘秋菊.应急配送车辆调度优化研究综述与展望[J].8.计算机应用研究，2012，29（9）：3212-3215，3220.

[3]Knoke D， Burt R S. Applied network analysis[M]. Newbury Park：Sage， 1983：195-222.

[责任编辑：杨玉洁]