1 模型构建

最优配送路线是NP问题，有许多种求解该问题的方法。本文要解决的是一个TSP问题，即路径最短，且无重复路线的一条最佳配送路线。因此本文要解决的是如何找出一个距离矩阵，使得该矩阵中任意两点之间的距离最小。首先要找出所有点与这两点之间的距离矩阵。然后运用 WinQSB软件中的分支定界法来得出这两点之间的最短路线。

1.2 TSP问题

旅行者问题（TSP）是一类具有代表性的组合优化问题。它可以这样来形容：对 N个城市，他们之间的距离已知，有一位旅行商人要从某一城市开始，把所有的城市都走一遍，而且每个城市只有一次机会，最终才会返回出发城市，请问，怎样才能让他所走的路程最短？

1.3 模型设计

  送路配线的问题是 TSP的一个简单应用，对于包含 n个区域的 TSP，定义 d_ij代表从区域 i到区域 j的距离，定义0-1的变量 x_ij代表的是供应商从区域 i到区域 j，反之， x_ij=0^【1】，那么 TSP的数学模型可以被表达为一个整数规划问题：

                                  式（1）

                式（2）

其中，辅助变量 u_i 是可以连续变化的，尽管这些变量在最优解中取一般的整数值（因此在约束条件中可以将这些变量限定为整数）。在此模型中，首先考虑了各区域内货物的到达情况，其次考虑了各区域间的距离，再次考虑了各区域间的距离，最后考虑了子回路间的距离。此模型的规模为： n （n+1）个 X_ij变量、 n个 U_i变量、（n+1）个第1种约束、（n+1）个第2种约束、 n（n-1）个第3种约束，由此，为了避开子回路而加入的第3种约束会极大地增加现实问题中约束的数目，并且 n很大时，这些约束的数目也会很大。

2京客隆配送中心

2.1配送中心与配送需求点位置

此次本文选取京客隆配送中心附近的39家需要进行货物配送的店铺，在这39家店铺中选取37家作为原有需求点，2家作为新需求点，模拟需求变动。这些配送需求点编号，初始需求点标记为1,2......37,之后插入的需求点标记为38,39。通过整理与调研对这39家店铺的生鲜农产品配送需求量，可以得出以下结论：①生鲜农产品服务时间 Si：分别是指供应商在配送中心的服务时间、客户对产品的需求时间以及供应商在配送中心的工作时间；②生鲜农产品时间窗[Ei, Fi]：分别是指供应商在配送中心服务期间可以开始进行收货和进行退货处理；③物流企业在送货时，需要考虑到车辆固定成本、单位运输成本等参数取值。

2.2算例求解结果与分析

采用 WinQSB软件，并结合相关算法，进行求解。首先，我们得到了分配路线规划的初步结果，在需求变动后，我们使用插入法进行求解，最终得到的结果，最后对结果进行了分析。

2.3静态需求下的求解结果

（1）最优车辆配送路径

运用WinQSB对原有37个便利店进行配送服务的初始规划，得到的最终配送方案，其中最优配送路线规划图如图1所示^【2】。

图1初始配送路线规划图

如图1所示，该配送路线有4条最优路径，需要分配4辆配送车辆才能完成配送任务。因此，需要将4辆车分别分配给这4条路径，并根据表1中的数据，生成每辆车负责的配送路线规划结果。因此，在表1中，共有4辆车分别为1、2、3、4。

表1 初始配送路线规划结果

（2）配送成本

程序运行后求得的最终各项成本统计表如表2所示。

表2 初始结果各项成本统计

综上所述，本文提出的算法可以在冷链物流企业新鲜农产品物流配送过程中，帮助企业获得最优的配送路径和计划，并给出了相关案例计算结果。时间窗惩罚成本、固定成本、制冷设备成本、运输成本占总成本的比例分别为1.55%、7.05%、27.03%和64.6%。除了运输成本之外，新鲜产品的冷却成本也在总成本中占有一定的比例，由于新鲜产品的分布具有一定的不均匀性，为防止货物在运输过程中分解和损坏，我们需要在配送货物时进行制冷处理。由于制冷设备成本较高，因此本文理论模型中对制冷设备成本的分析和考虑具有一定的实际意义。其次，影响客户满意度的时间窗惩罚成本也是一个重要因素，根据本文得出的结果可以看出，时间窗惩罚在总成本中占总成本的比例相对较低。由于本文提出的方法可以将整体物流配送成本降到最低，因此也能够使客户满意度有一定程度上的提升。

3需求变动后的求解结果

增加了静态需求商店的数量，进一步验证本文基于上述结果的模型和算法的有效性。

新的需求点38需求量为1.5吨，39需求量为1.0吨分别在6:00及5:30产生需求。基于最初方案，38号仅能能在满足车辆的最大负载要求时选择插入车辆4的配送路径，39号可以选择插入车辆2或车辆4的配送路径，最后根据初始最优解选择额外成本最低的解决方案，将需求点38和39插入到车辆4的配送路线中，最优路线为0-1-30-29-32-31-34-39-33-38-0。多付出的成本为226.6元，4号车目前的装载能力为88%。路线如图2所示。

图2 需求变动后的路线规划图

图2所示为配送的需求变化后的路线图，插入算法确保了最初的配送路线不会受到过多的影响。同时，在原分配计划中增加了新的需求点，表3为需求变化后的配送分配计划。

表3 需求变动后的配送路线规划结果

每个项目的费用列于表4。

表4 需求变动后的各项成本统计

从上述表格不难看出，在配送运输过程中插入新的需求点时，采用插入算法可以比较便捷的求出最优解，且在不打乱原有的配送路线计划的前提下，还可以提高原有配送路线中车辆利用率，最大化利用配送资源，最小化额外成本。完成货物配送。

4总结

城市物流系统中，配送系统是最主要的一个。其中，运输是最关键的环节，由于其在整个物流过程中所占的比例几乎达到了百分之五十，因此，在整个物流过程中，最主要的方法就是减少运输成本。本文在取得配送中心及配送需求点基础数据基础上，运用 WinQSB 进行配送路线优化设计，得出比较可行的配送路线方案。并进一步验证了此方法具有一定的稳定性和适用性，即使数据较多时也具有可行性。

参考文献

[1] 陆翠萍,邓萍.WinQSB在运输问题实验教学中的应用[J].试题与研

究 , 2019 , (34):196-197

[2] 董继荣,物流配送线路优化方案设计[J].兰州石化职业技术学院学

报,2018,18(02):46-48 统仿真学报,2021,33(07):1670-1681.

基金项目：2023年大连科技学院大学生创新创业训练计划项目（校级）“基于WinQSB的物流配送路线优化设计”。