浅议零星物资配送路径优化

杨洋

摘要：随着物资集约化的深化，零星物资应用电商化采购，零星物资采购单价低、规格品种多、需求频次高的特点使得其配送具有多品种、小批量、多批次的特点，而较高的送货频率和较多的车辆数量导致了配送效率的下降和配送成本的增加，本文通过介绍配送路径优化的模型和算法，以零星物资配送的特点为出发点，考虑运输成本和惩罚成本来建立相应的数学模型，并提出了模糊聚类分析和节约算法相结合的混合算法，为路径优化问题提供了一种思路。

关键词：零星物资；车辆路径问题；模糊聚类—节约混合算法

一、配送路径优化的模型

（1）旅行商问题（TSP）。旅行商问题是指旅行商从一个城市出发去其他城市，每个城市他去一次，并且只去一次，最后回到出发城市，如何选择行程路线使总路程最短。（2）中国邮递员问题。中国邮递员问题也称“一笔画”问题。如果在某邮递员所负责的范围内，街道图中没有奇点（边的个数为奇数），那么他就可以从邮局出发，走过每条街道一次且仅一次，最后回到邮局，这样他所走的路程也就是最短的路程。对于有奇点的街道图，就必须在某些街道上重复走一次或多次。（3）车辆路径问题（VRP）。车辆路径问题是设计合理的路线，使车辆有序地通过一系列客户的需求点，在满足物资需求量、发货时间、发货量、行驶里程限制、车辆载重量限制、时间限制等约束条件下，达到时间最短、费用最少、里程最短、车辆利用率高的优化目标。

二、配送路径优化的算法

（一）解决两点之间最短路问题的算法——狄克斯法

解决两点之间最短路问题的算法是狄克斯（Dijkstra）法。这种算法的基本思路是找出从起点到终点的最短路径点的顺序，算法进行时对每一个点给定一个标号，分为临时标号和固定标号：表示从起点到点的最短距离的上界，表示从起点到点的实际最短距离。

（二）解决中国邮递员问题的算法——奇偶点图上作业法

解决中国邮递员问题的算法也称作奇偶点图上作业法。这种算法的基本思路是在含有奇点的图中增加一些重复边，并且使重复边的总权数最小。

（三）解决TSP和VRP问题的算法

解决旅行商问题和车辆路径问题的算法有精确算法、传统启发式算法、现代启发式算法。精确算法包括动态规划法、分支定界法、切平面法。传统启发式算法在路径优化问题求解时是从初始解出发，以邻域搜索的方式改进解，并在短时间内获得一个可接受的解：包括邻接算法、扫除算法、插入算法、节约算法。这里介绍一下节约算法（算法）：

假定为网点、为用户、为用户需求量、为到的最短距离、为到的最短距离、有种车、载重量为的车有台，且。其基本思路是依据节约量公式，在汽车负载允许条件下，将供货范围内的用户按节约量的大小（先大后小）依次连接入巡回路线，直至汽车满载为止。

现代启发式算法不要求在每次迭代中均沿目标值下降，允许在算法中适当接受目标值有所上升甚至不可行的解，其目的是能够跳出局部搜索领域：包括遗传算法、蚁群算法、禁忌搜索算法、模拟退火算法。

解决旅行商问题和车辆路径问题的三种算法中，精确算法适用于求解小规模问题，传统的启发式算法不太适用于现在实际遇到的问题，现代启发式算法由于跳出了局部搜索领域，能解决实际当中所遇到各种复杂问题，而遗传算法和蚁群算法又是经常被用来解决车辆路径问题。

三、零星物资配送路径优化的数学模型

零星物資配送具有多品种、小批量、多批次的特点，据此在建立数学模型时要考虑两个目标数：总费用最小和运输时间及时，其中运输时间及时指物资能否按照要求及时送到客户手中，若提前或及时送到则不进行惩罚，否则要进行惩罚。

零星物资配送路径优化问题可描述为在设施位置、客户点位置已知并且各道路状况一致的条件下，由一个配送中心用辆车对个客户进行配送，确定一套车辆运输路线以满足运输成本和惩罚成本最小。其中每条路线的总负荷不能超过负责该配送路线的汽车的最大载重量，并且每个客户必须而且只能被服务一次。

四、零星物资配送路径优化的算法——模糊聚类—节约混合算法

遗传算法和蚁群算法被经常用来解决VRP问题，在实际应用遗传算法时，往往出现早熟收敛等缺点，因此出现了许多用来改进遗传算法的策略。由于遗传算法实际应用需要使用mat lab软件，而本文只是提出了其使用原理，并未探究软件编程，所以本文将模糊聚类分析法和节约算法相结合，先用最大树法原理对客户进行模糊聚类分析，将客户分为若干子类，然后对每类采用节约算法求解零星物资配送路径优化。

五、实际运用

在实际配送情况中，不同时间段和路段的交通拥挤程度不同，而本文所提出的模型假设了各道路状况一致，所以本文只是对零星物资配送路径优化问题作了初步的模型建立和相应算法探讨。本文建立的数学模型及算法在进行配送路线决策时比较适用于以下条件：

1.配送点及客户坐标位置可计量；

2.各点间道路交通状况一致；

3.客户重点关心物资是否延期送到，将提前送到与及时送到认为效率一致。

在实际运用方面，对于满足上述三点条件的配送情况，可通过软件编程的方式，将本文建立的数学模型及算法转化为操作软件，通过将实际客户转化为坐标值的方式，在软件中录入信息值，然后运用软件自动匹配出配送方案，避免人工决策的片面性和计算的复杂性、低效率性。

（作者单位：国网四川省电力公司成都供电公司）

参考文献

[1]孙洪茹.城市物流配送体系及其路线优化的研究[D].山东科技大学，2005.

[2]王涛.城市物流外部不经济问题研究[D].武汉理工大学管理学院，2007.

[3]刘云忠，宣慧玉.车辆路径问题的模型及算法研究综述[N].管理工程学报，2005-01（19）.

[4]王转，程国全，冯爱兰.物流系统工程[M].高等教育出版社，2004.

[5]张潜.物流配送路径优化调度建模与实物[M].中国物资出版社，2006