何明宇

摘要：配送运输由于目标客户多，一般城市交通路线又较复杂，如何安排最佳配送路线是非常有挑战性的一项工作，配送路径优化的基本问题往往可以简化为旅行商问题。本文的目的是展示如何在MS Excel中使用VLOOKUP和INDEX函数，结合“规划求解”工具中的Alldifferent约束建立旅行商问题型的配送路径优化求解模型的一种方法，并用实例说明了方法的操作过程及有效性。

Abstract：  Due to the large number of target customers and the complicated urban traffic routes， how to arrange the best delivery route is a very challenging task. The basic problems of distribution route optimization can often be simplified to the traveling salesman problem. The purpose of this paper is to show a method to use the VLOOKUP and INDEX functions in MS Excel to establish a traveling salesman problem-based distribution path optimization solution model by combining the Alldifferent constraint in the "Solver" tool， and illustrate the operation and effectiveness of the method with examples.

关键词：配送;旅行商问题;Alldifferent

Key words： distribution;traveling salesman problem;Alldifferent

中图分类号：F253.9                                        文献标识码：A                                  文章编号：1006-4311（2019）27-0216-03

0  引言

王之泰教授从资源配置的角度定义“配送是以现代送货形式实现资源的最终配置的经济活动。”这一定义认为是配送的主要经济活动是以现代生产力、劳动手段支撑的，依靠科技进步的，使“配”和“送”有机结合的一种送货方式。

在配送过程中，由于配送客户多，城市交通道路纵横交错，相当复杂，配送路线安排是否得当，不仅影响物流成本和车辆的运行时间，还与城市交通压力息息相关。以往配送员大抵是依据经验和城市布局安排的配送路线，缺乏系统的科学理论和技术指导，配送效率和经济性都还有非常大的提升空间。

城市配送的基本问题可以简化为一辆车从一个配送中心出发为若干需求点的客户送货，在现有的城市路网中，选择合适的线路，安排一个最恰当的顺序完成所有客户的送货，从而达到既能按时完成任务，同时总成本最小，因此配送路径优化的基本问题又可以简化为旅行商问题。

1  旅行商问题（Traveling salesman problem，TSP）

旅行商问题（TSP）是运筹学领域的一道经典名题。其一般描述为：有一名旅行推销商人，从某个城市出发，要访遍若干城市各一次且仅一次，最后返回到原出发城市，已知从城市i到j的旅费为Cij，问这名旅行推销商人应该如何安排旅行路线使总旅费最少？

2  TSP模型的数学描述

若仅考虑前三个约束条件簇，则是类似于指派问题的模型。对TSP模型只是必要条件，并不是充分。例如，六个城市的旅行路线若为2-1-6-2和5-4-3-5，则该路线虽然满足前三个约束条件，但是不构成整体巡回路线，它含有两个子巡回，因此需要增加“不含子巡回”的约束条件。

3  文献综述

TSP模型是一个重要的组合优化问题，属于NP-完全问题。迄今为止，仍然没有找到求解它的多项式时间算法，文献[1，2]认为，TSP不能用精确算法得到最优解，甚至得到其近似解也是不容易的。

纵观近几年的研究成果，研究人员解决TSP的研究方法可以归为以下几类，如图1所示。

这些解法都需要在专门的软件平台中编程，对一般管理人员来讲有一定的难度，文献[3]基于TSP的混合整数规划模型，并用EXCEL软件来求解，该方法的优点是不需要专门的商业软件和高深的编程知识，但是为了避免形成子回路引入虚拟变量ui，uj构建约束条件簇：ui-uj+nxijn-1（1i≠jn），ui，uj为常数（i，j=1，…，n）。一方面，对于大多数人来说都难以理解它的数学原理。另外，在建模时，这一约束条件也不容易被表示，且随着模型节点数的增加，约束条件数增加非常快，大大增加模型的復杂度。

本文的目的是展示如何在MS Excel中应用VLOOKUP和INDEX函数，结合规划求解工具中的Alldifferent约束建立旅行商问题（TSP）的模型并求出最优解，该方法的实际意义是可以为目前城市配送路线的优化问题提供一种快速有效的求解方法。

4  利用Excel求解器优化城市配送路径

案例：HQ便利连锁超市是四川省内的一家A股上市公司。公司现建有三座配送中心，为全市2900家连锁超市统一配送货物。根据门店需求信息，第三配送中心DC3需要安排一辆车为周边14家门店进行补货，DC3与14家门店的距离矩阵如图2所示，如何设计配送路线才能使得车辆从配送中心DC3出发，配送完毕后返回到DC3所经过的路程最短？

4.1 EXCEL建模知识准备

4.1.1 VLOOKUP

VLOOKUP 是 Excel 中最常用且最有用的函数之一，用于在表格或区域中按行查找项目。VLOOKUP 的语法如下：

VLOOKUP（lookup_value，table_array，col_index_num，[range_lookup]）

其中：

lookup_value：必需。查阅值;

table_array：必需。包含查阅值的区域;

col_index_num：必需。包含返回值的区域中的列号;

range_lookup：可选。TRUE为近似匹配，FALSE为精确匹配。

4.1.2 INDEX

INDEX 函数返回表格或区域中的值或值的引用。使用 INDEX函数有两种方法：数组形式和引用形式。本文的模型需要返回指定单元格或单元格数组的值，故选用数组形式。其语法如下：

INDEX（array， row_num， [column_num]）

其中：

array：必需。单元格区域或数组常量;

row_num：必需。选择数组中的某行，函数从该行返回数值;

column_num：可选。选择数组中的某列，函数从该列返回数值。

4.1.3 Alldifferent

一种特殊类型的整数约束（称为“不同”约束），其中n个决策变量的值必须是从1到n的整数排列。主要应用于涉及确定最佳排序类问题。

4.2 建立配送路径优化的EXCEL模型，如图3所示

步骤1：对配送中心及门店进行顺序编号，即D3：R3，B5：B19区域中的数字。输入配送中心DC3与14家门店的距离矩阵。

步骤2：确定决策变量和初始可行解。

从配送中心DC出发，因为可行的次序都要求要访遍所有门店各一次且仅一次，最后返回原出发地，因此，我们选择编号为0的配送中心DC作为起点。

C23：C36区域为决策变量，显示途中的旅程，以数字的次序对配送中心和门店进行排序。当我们抵达第n-1个节点时，必须要回到编号为0的配送中心，所以单元格C37并不是决策变量。

我们设单元格B23为0，无论你选择那一家门店，从编号为0的配送中心到它之间的距离就是C23中的变量，由于要确保这家门店变成下一行程中的“起始”门店，所以在单元格B24中设置公式“=C23”，向下复制填充至B37单元格。

步骤3：建立目标函数。

在单元格D23中输入公式“=INDEX（$D$5：$R$19，B23+1，C23+1）”，该公式的目的是从距离表中查询出从一个节点i出发去到另一节点j走过的路程，然后向下复制填充至D37单元格。

在单元格D38中输入公式“=SUM（D14：D19）”，用于计算走完全部门店后回到配送中心的总路程，它将作为规划求解的目标单元格。

步骤4：将这些节点编号的数值转换成配送中心或门店名称。在单元格F23中输入公式“=VLOOKUP（B23，$B$5：$C$19，2）”，然后向下复制填充至单元格F37。在单元格G23中输入公式“=VLOOKUP（C23，$B$5：$C$19，2）”，然后向下复制填充至单元格G37。

4.3 设置规划求解参数

选中D38单元格，点击数据|规划求解，打开“规划求解参数”对话框，在“设置目标”文本框中输入D38，选中“最小值”单选按鈕，在“可变单元格”文本框中输入C23：C36。

单击“添加”按钮，打开“添加约束”对话框添加约束条件，本例中所包含的约束条件如下：

条件1：C23：H36=ALLDifferent（不含子巡回）

因为模型为非光滑规划求解问题，故求解方法应选择“演化”，规划求解参数全部设置完毕，如图4所示。

4.4 求解模型

单击“规划录解参数”对话框中的“求解”按钮开始求解运算。在“规划求解结果”对话框中并显示找到一个最优结果，如图5所示。

单击的“确定”按钮可以保存求出的最优结果，如图6所示。

通过图5中的可以看出，求得的最优路径为：DC3→N→K→J→L→I→M→F→A→B→G→C→D→E→H→DC3，配送车辆行驶的总里程为82.68千米。

5  结论

①尽管有许多学者利用专业软件对旅行商问题建立了较为系统的算法模型，但是，实际应用中经常遇到许多问题，如需要专业软件环境支持，软件费用昂贵，操作员专业化程度要求很高等。

②灵活运用Excel结合其强大计算能力建立了配送管理中路线优化决策中的基本问题——TSP的ECXCEL模型，为该类问题的求解提供了一种有效的思路。该方法在配送和运输物流领域具有重要的实际意义。

③模型求解花费时间： 89.187 秒。表明使用该模型求解一般的路线优化问题快速且高效。需求地的增加成倍地增加了（寻找最佳行走路线）任务的复杂性，使用MS Excel 规划求解工具可以很容易地解决TSP类型的配送路径优化问题，而不用担心客户的数量。

参考文献：

[1]徐丽蕊.城市配送TSP问题的LINGO求解[J].电子设计工程，2015，23（13）：62-64.

[2]严晨，王直杰.以TSP为代表的组合优化问题研究现状与展望[J].计算机仿真，2007，24（6）：171-174.

[3]张敏，金琴玲.旅行商问题的一种新解法[J].重庆职业技术学院学报，2008（1）：153-154.

[4]戴宗瑞.TSP问题在物流配送车辆运行路线中的应用分析[J].软件导刊，2012，11（6）：93-95.

[5][美]Michael R.Middleton.使用Microsoft Excel进行数据分析[M].北京：中国水利水电出版社，1997.

[6]ExcelHome. Excel 2010数据处理与分析实战技巧精粹[M].北京：人民邮电出版社，2014，1.

[7]王剑文，戴光明，谢柏桥，张全元.求解TSP问题算法综述[J].计算机工程与科学，2008，30（2）：72-74.

[8]潘正君，康立山，陈毓屏.演化计算[M].北京：清华大学出版社，1997.