EXCEL辅助进行CW节约算法计算研究

1、 EXCEL辅助进行CW节约算法计算研究 王帆等Summary：针对传统节约里程法求解过程中，节约值矩阵和节约值排序计算工作量大、费时、易出错的问题，借助EXCEL函数和VBA进行辅助加以解决，实现了节约值矩阵和节约值排序表的快速自动求解。Key：CW节约算法；EXCEL；自动求解DOIDOI：10.11907/rjdk.143620：TP312：A ：16727800（2015）0010072020 引言在物流系统中，经常遇到车辆路径规划问题，CW节约算法是解决车辆路径规划问题的利器，具有很强的实用价值。然而，该方法如果依靠手工计算非常复杂，费时还易出错。本文探索了利用EXCEL辅助进行CW

2、节约算法计算的方法，为CW节约算法的实际应用提供了一套新的解决方案。1 CW节约算法常规步骤举下例说明算法：某物流公司有一配送中心P，负责AJ共计10家客户的配送任务，对应的配送路线如图1所示。括号内的数据为发送量（t），路线上的数字表示道路距离（km）。假设能利用的车是载重2t和4t的两种车型，并限制车辆一次运行的最大距离为30km1，请设计配送路线，使行驶路程尽量少。CW节约算法能够有效地求解上述算例，其求解过程可以分为以下4个步骤2。步骤1：根据图1所示客户的位置、距离和用户需求数据计算各客户点对间的最短距离，如图2所示；步骤2：根据最短距离表计算各客户点对的节约值矩阵，如图3所示；步骤

3、3：根据节约值矩阵形成节约值排序，如图4所示；步骤4：根据节约值排序表和约束条件确定配送路线和配载方案。图1 VRP算例配送任务图2 最短距离矩阵图3 节约值矩阵图4 节约值排序在上述算例中，根据条件最终能够确定3条配送路线：1 PJABCP；2 PDEFGP；3 PHIP 。步骤2和步骤3的计算非常繁琐，可以借助EXCEL实现该操作。1.1 步骤2的实现方法新建一个EXCEL文件，在A1L12区域内输入如图2所示的最短距离矩阵。接下来在M2V11区域内计算出节约值矩阵。在N2V2区域依次输入AI这9个字母，在M3M11区域依次输入BJ这9个字母。在N3单元格输入公式：“=IF（ISNUMBE

4、R（C4）， IF（N$2$M3， INDEX（$B$3：$B$12，ROW（M3）-1，1）+INDEX（$B$3：$B$12，COLUMN（N2）-13，1）-C4，），）”拖拽填充到V3单元格，再拖拽填充到V11单元格，得到如图3所示的节约值矩阵。该公式能够实现通过拖拽方式直接生成全部节约值。下面对该公式进行简单解释。节约值的计算公式形如“PX+PYXY”，其中，X和Y分别代表AJ中任意两个不同的点。经过分析，PX和PY两个值都可以在B列找到，XY的值在最短路径表和节约值矩阵中的位置是完全对应的，因此，可以据此设计公式。公式的核心部分是：“INDEX（$B$3：$B$12，ROW（M3）

5、-1， 1）+INDEX（$B$3：$B$12， COLUMN （N2）-13， 1）-C4”在单元格N3中，即代表“PB+PAAB”。其中的绝对引用、相对引用、INDEX函数、ROW函数和COLUMN函数的设置，都是为了能够利用拖拽填充的方法快速求得所有节约值。公式括号内部的IF函数确保右上侧三角区域不生成数据，只生成如图3所示的三角式矩阵。括号外部的IF函数确保当客户节点不足10个时，相应的位置不进行计算。1.2 步骤3的实现方法首先需要将点对名称与节约里程对应起来，要写出所有可能的点对，并标出节约里程。点对可以手动输入，但操作繁琐，这里可以结合CONCATENATE和INDEX两个函数来

6、完成该操作。如图5所示，先在W列和X列输入辅助数据，W列从W2单元格开始输入数字1-9各9个，共81个数字；X列从X2单元格开始输入数字1-9，输入9次，共81个数字。在Y2单元格输入如下公式“=CONCATENATE（INDEX（$M$2：$V$11， 1， 1+W2）， INDEX（$M$2：$V$11， X2+1， 1）”，拖拽填充到Y82单元格。图5 辅助数据的设置节约里程则根据点对名称，利用HLOOKUP函数到节约里程表数据区查找。在Z2单元格输入公式“=HLOOKUP（LEFT（Y2，1），$N$2：$V$11，X2+1）” ，拖拽填充到Z82单元格。接下来需要将节约里程值进行排序

7、，考虑到程序的复用性，可以添加一个按钮，命名为“复制排序”，通过录制并修改宏来实现。修改好的宏代码及注释如下：Sub 复制排序（） 复制排序选择性粘贴Range（Y1：Z82）.SelectSelection.CopyRange（AD1）.SelectSelection.PasteSpecial Paste：=xlPasteValues， Operation：=xlNone， SkipBlanks ：=False， Transpose：=False升序排列Application.CutCopyMode = FalseSelection.Sort Key1：=Range（AE2）， Order1

8、：=xlAscending， Header：=xlGuess， OrderCustom：=1， MatchCase：=False， Orientation：=xlTopToBottom， SortMethod ：=xlPinYin， DataOption1：=xlSortNormal删除无效数据k = Range（AE65536）.End（xlUp）.Row + 1s = 2For i = 2 To kIf Cells（i， 31） Thens = s + 1End IfNext iRange（AD65536：AE & s）.SelectSelection.ClearContents降序排列R

9、ange（AD1：AE & s - 1）.SelectSelection.Sort Key1：=Range（AE2）， Order1：=xlDescending， Header：=xlGuess ， OrderCustom：=1， MatchCase：=False， Orientation：=xlTopToBottom， SortMethod：=xlPinYin， DataOption1：=xlSortNormalEnd Sub这样，在单击“复制排序”按钮之后，程序自动运行，计算结果如图6所示。图6 节约值排序结果接下来，需要根据节约值排序结果和约束条件确定配送路线和配载方案，相应的方法在很多文献里都能找到，这里不再赘述。2 结语节约值排序表的自动计算为管理决策节省了大量宝贵时间，并且能够保证运算的准确性。由于工具易用，有利于CW节约算法的普及，因而有利于提高管理工作的科学性