| 标题 | EXCEL辅助进行CW节约算法计算研究 |
| 范文 | 王帆等 摘要：针对传统节约里程法求解过程中，节约值矩阵和节约值排序计算工作量大、费时、易出错的问题，借助EXCEL函数和VBA进行辅助加以解决，实现了节约值矩阵和节约值排序表的快速自动求解。 关键词：CW节约算法；EXCEL；自动求解 DOIDOI：10.11907/rjdk.143620 中图分类号：TP312 文献标识码：A 文章编号文章编号：16727800（2015）001007202 0 引言 在物流系统中，经常遇到车辆路径规划问题，CW节约算法是解决车辆路径规划问题的利器，具有很强的实用价值。然而，该方法如果依靠手工计算非常复杂，费时还易出错。本文探索了利用EXCEL辅助进行CW节约算法计算的方法，为CW节约算法的实际应用提供了一套新的解决方案。 1 CW节约算法常规步骤 举下例说明算法：某物流公司有一配送中心P，负责AJ共计10家客户的配送任务，对应的配送路线如图1所示。括号内的数据为发送量（t），路线上的数字表示道路距离（km）。假设能利用的车是载重2t和4t的两种车型，并限制车辆一次运行的最大距离为30km[1]，请设计配送路线，使行驶路程尽量少。 CW节约算法能够有效地求解上述算例，其求解过程可以分为以下4个步骤[2]。 步骤1：根据图1所示客户的位置、距离和用户需求数据计算各客户点对间的最短距离，如图2所示； 步骤2：根据最短距离表计算各客户点对的节约值矩阵，如图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（ISNUMBER（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）-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两个函数来完成该操作。如图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单元格。 接下来需要将节约里程值进行排序，考虑到程序的复用性，可以添加一个按钮，命名为“复制排序”，通过录制并修改宏来实现。修改好的宏代码及注释如下： Sub 复制排序（） ' 复制排序 选择性粘贴 Range（"Y1：Z82"）.Select Selection.Copy Range（"AD1"）.Select Selection.PasteSpecial Paste：=xlPasteValues， Operation：=xlNone， SkipBlanks ：=False， Transpose：=False 升序排列 Application.CutCopyMode = False Selection.Sort Key1：=Range（"AE2"）， Order1：=xlAscending， Header：=xlGuess， OrderCustom：=1， MatchCase：=False， Orientation：=xlTopToBottom， SortMethod ：=xlPinYin， DataOption1：=xlSortNormal 删除无效数据 k = Range（"AE65536"）.End（xlUp）.Row + 1 s = 2 For i = 2 To k If Cells（i， 31） <> "" Then s = s + 1 End If Next i Range（"AD65536：AE" & s）.Select Selection.ClearContents 降序排列 Range（"AD1：AE" & s - 1）.Select Selection.Sort Key1：=Range（"AE2"）， Order1：=xlDescending， Header：=xlGuess ， OrderCustom：=1， MatchCase：=False， Orientation：=xlTopToBottom， SortMethod：=xlPinYin， DataOption1：=xlSortNormal End Sub 这样，在单击“复制排序”按钮之后，程序自动运行，计算结果如图6所示。 图6 节约值排序结果 接下来，需要根据节约值排序结果和约束条件确定配 送路线和配载方案，相应的方法在很多文献里都能找到，这里不再赘述。 2 结语 节约值排序表的自动计算为管理决策节省了大量宝贵时间，并且能够保证运算的准确性。由于工具易用，有利于CW节约算法的普及，因而有利于提高管理工作的科学性。 |
| 随便看 |
|
科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。