王际洲　安徽省烟草公司信息中心，合肥，２３００２２　

摘　要：物流配送是烟草销售业务的重要环节，也是业务成本的主要组成部分。烟草物流大系统中存在很多复杂的优化问题，本文研究了其中的配送中心的数量、配送中心的选址、访送周期的优化、配送线路的优化四个问题的求解方法。其中的一些算法思想已经应用于安徽烟草的物流项目中。对这些问题的深入研究将有利于提高烟草配送业务的效益和服务水平，向精益物流逐步迈进。　

关键词：　烟草　物流　配送中心　访送周期　配送线路　优化　

Ｒｅｓｅａｒｃｈ　ｏｎ　Ｓｅｖｅｒａｌ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ｐｒｏｂｌｅｍｓ　ｗｉｔｈｉｎ　Ｔｏｂａｃｃｏ　Ｌｏｇｉｓｔｉｃｓ　Ｓｙｓｔｅｍ　

ＷＡＮＧ　Ｊｉｚｈｏｕ　

Ｉｎｆｏｒｍａｔｉｏｎ　Ｃｅｎｔｅｒ，Ａｎｈｕｉ　Ｔｏｂａｃｃｏ　Ｃｏｍｐａｎｙ，ｈｅｆｅｉ，２３００２２　

ＡＢＳＴＲＡＣＴ：Ｌｏｇｉｓｔｉｃｓ　ｉｓ　ｎｏｔ　ｏｎｌｙ　ｔｈｅ　ｋｅｙ　ｌｉｎｋｓ　ｏｆ　ｔｏｂａｃｃｏ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｓｅｒｖｉｃｅ，ｂｕｔ　ｔｈｅ　ｓｏｕｒｃｅ　ｏｆ　ｍｏｓｔ　ｐａｒｔ　ｏｆ　ｃｏｓｔ．　Ｔｈｅｒｅ　ａｒｅ　ｓｅｖｅｒａｌ　ｃｏｍｐｌｉｃａｔｅｄ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍｓ　ｉｎ　ｔｏｂａｃｃｏ　ｌｏｇｉｓｔｉｃｓ　ｓｙｓｔｅｍ，　ａｎｄ　ｔｈｉｓ　ｐａｐｅｒ　ｆｏｃｕｓｅｓ　ｏｎ　ｆｏｕｒ　ｏｆ　ｔｈｅｍ，　ｉ．ｅ．　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｃｅｎｔｅｒ　ｎｕｍｂｅｒ　ｄｅｃｉｄｉｎｇ，　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｃｅｎｔｅｒ　ｌｏｃａｔｉｎｇ，　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｐｅｒｉｏｄ　ｐｌａｎｎｉｎｇ，　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｖｅｈｉｃｌｅ　ｒｏｕｔｉｎｇ．　Ｓｏｍｅ　ｏｆ　ｔｈｅ　ｉｄｅａｓ　ｐｒｅｓｅｎｔｅｄ　ｈｅｒｅ　ｈａｖｅ　ｂｅｅｎ　ａｐｐｌｉｅｄ　ｔｏ　ｔｈｅ　ｌｏｇｉｓｔｉｃｓ　ｐｒｏｊｅｃｔ　ｏｆ　ａｎｈｕｉ　ｔｏｂａｃｃｏ　ｃｏｍｐａｎｙ．　Ｉｔ　ｉｓ　ｕｎｄｏｕｂｔｅｄ　ｔｈａｔ　ｔｈｅｓｅ　ｒｅｓｅａｒｃｈ　ｗｉｌｌ　ｂｅ　ｈｅｌｐｆｕｌ　ｔｏ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｂｅｎｅｆｉｔ　ａｎｄ　ｓｅｒｖｉｃｅ，　ａｎｄ　ｂｅ　ａ　ｓｔｅｐ　ｌｅａｄｉｎｇ　ｔｏ　ｌｅａｎ　ｌｏｇｉｓｔｉｃｓ．　

Ｋｅｙｗｏｒｄｓ：　ｔｏｂａｃｃｏ，　ｌｏｇｉｓｔｉｃｓ，　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｃｅｎｔｅｒ，　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｐｅｒｉｏｄ，　ｖｅｈｉｃｌｅ　ｒｏｕｔｉｎｇ，　ｏｐｔｉｍｉｚａｔｉｏｎ　

　　１、引言　

　　现代物流已成为新经济时代经济发展的推进器，在经济和社会发展中发挥着重要作用。对于专卖下的烟草行业来说，烟草物流不仅是客户服务的重要组成内容，也是业务成本的最主要组成部分；同时，烟草物流业务模式也在不断发展中，所以，烟草物流不仅涉及客户关系，也直接影响企业利润，不仅影响当前业务，也关系着未来发展。研究烟草物流的意义不言而喻。　

　　烟草物流是一个复杂的大系统，其中存在许多优化问题，这些问题有两个方面的共同点：一是这些问题都直接关系烟草物流业务的成本、效益和服务水平；二是这些问题都比较复杂，其中许多是ＮＰ难题。本文研究配送中心的数量、配送中心的选址、访送周期的优化、配送线路的优化四个问题的求解方法。这些研究思想部分地在“安徽烟草物流ＧＰＳ和线路优化项目”中得到应用。　　　２、配送中心优化问题　

　　烟草物流配送都是以配送中心为起点的，并且配送中心都是由烟草企业自主经营的。另一方面，区域物流整合是物流发展的一个方向。所以，研究配送中心优化问题具有相当的现实意义。配送中心的优化可以分解为两个问题，一是配送中心的数量，二是配送中心的位置。　

　　２．１配送中心数量　

　　２．１．１问题描述　

　　烟草物流配送中心数量的优化问题可以描述为：对于每一个确定的烟草配送区域，确定在该区域内应该设置多少个物流配送中心，在满足该区域总物流需求的条件下，使总成本最少。　

　　在实际规划中，确定物流配送中心的数量需综合考虑各种因素，本文只在理论上给出一个最佳的配送中心数目计算方法。为研究问题方便起见，做如下假设：首先，设区域内的物流需求量是平均分布的，各物流配送中心的规模相同而且位于其服务区域的中心；其次，设相同规模的物流配送中心在区域内各处的建设费用相等，即物流配送中心的建设费与位置无关。　

　　２．１．２求解分析模型　

　　设所规划物流区域的总面积为Ａ，物流总需求量为Ｇ；设区域配送中心数为ｍ，区域物

流配送总成本为Ｃ

ｔ（ｍ），它由物流配送成本Ｃｄ和配送中心建设成本Ｃ

ｓ

两项组成。由前面的

假设：　

　　每个物流配送中心的服务范围的面积ａ相等，ａ＝Ａ／ｍ；　

　　每个物流配送中心的物流处理量ｇ相等，ｇ＝Ｇ／ｍ；　

　　配送中心配送的平均距离ｄ与服务范围面积ａ的平方根成正比：

　　　确定区域最佳配送中心数问题就是要求整数ｍ，使上式达到最小值。　

　　设ｍ为实数变量，Ｃ

ｔ

（ｍ）为ｍ的连续函数，求解最优配送中心数目问题转化为连续函数求极值问题，最终解为：作为物流中心数量，ｍ的实际最终解可通过该实数取整，以及取整加１后两个整数的函数值比较得到。　

　　２．２配送中心选址　

　　２．２．１问题描述　

　　在确定配送中心数目后，更重要的问题是配送中心选址问题。问题可描述为：在配送对象位置和需求量已知的前提下，在固定区域内选定确定ｋ个配送中心的位置，使得总体配送成本最低。　

　　这个问题可一个归结为一个有距离约束的ｐ－ｍｅｄｉａｎ问题［２］。ｐ－ｍｅｄｉａｎ问题最先由

Ｈａｋｉｍｉ于１９６５年提出，并随后被证明是一个ＮＰ难题［３］。因此对于大规模问题，最优解很难得到。这类问题一般用启发式算法来寻找最优解（或近似最优解），免疫算法［４，５，６］是一种优良的启发式算法，该算法已经有许多在工程领域成功运用的实例。　

　　２．２．２免疫算法概述　

　　免疫系统是抵抗细菌、病毒和其它致病因子入侵的基本防御系统。免疫系统的工作过程可描述为：免疫细胞识别病毒抗原（Ａｎｔｉｇｅｎ），相应免疫细胞被激活并发生克隆和细胞超变异反应，最后通过分泌相应的抗体（Ａｎｔｉｂｏｄｙ）将抗原消灭。免疫系统要消灭入侵的抗原，最关键的一步就是要正确识别入侵的抗原，即免疫系统要以有限的资源识别几乎无限的对象。　

　　免疫系统的识别多样性带来了许多启示，此特性的数学抽象可以描述为对多峰值函数的寻优问题。与一般的确定性优化算法相比，免疫算法有以下显著特点：１）它同时搜索解空间中的一系列的点，而不只是一个点；２）它处理的对象是表示待求解的参数的编码数字串，而不是参数本身；３）它使用的是目标函数本身，而不是其导数或其它附加信息；４）它的变化规则是随机的，而不是确定的。　

　　免疫算法的一般求解步骤为：１）计算亲和度；２）计算期望值；３）构造记忆单元。免疫系统中的抗原和抗体分别对应于优化问题的目标函数和可能解。　

　　其中亲和度有两种形式：一种形式说明了抗体和抗原之间的关系，即解和目标的匹配程度；另一种形式解释了抗体之间的关系，这个独有的特性保证了免疫算法具有多样性。计算期望值的作用是控制适用于抗原（目标）的相同抗体的过多产生。用一组记忆单元保存用于防御抗原的一组抗体（优化问题的可行解）。在这个基础上，免疫算法能够以较快速度收敛到全局最优解。　

　　２．２．３配送中心选址优化策略［７，８］　

　　１、问题数学模型　

　　设Ｃ＝｛１，２，……，ｃ｝是所有客户点的序号集合；ｄ

ｉｊ

表示从客户点ｉ到离它最近的配送

中心ｊ的距离；ｗ

ｉ表示客户点的需求量；ｙ

ｊ

是０、１变量，当客户点ｊ被选为配送中心时，其值为１，否则为０；ｘ

ｉｊ

是一个０、１变量，当其客户点ｉ的需求量由配送中心ｊ供应时，

其值为１，否则为０；ｓ为新建配送中心离由它服务的客户点的距离上限；Ｍｉ为到客户ｉ的

距离小于ｓ的备选配送中心集合，ｉｅｃ，ｍ

ｉ

ｅｃ；　

　　有距离约束的ｐ－ｍｅｄｉａｎ问题需要在满足距离上限的情况下，从ｃ个客户点中找出ｐ个点作为配送中心。目标函数是各配送中心到客户点的以需求量为权重的距离之和最小，即：。　

　　２、配送中心选址的免疫算法　

　　在烟草物流配送中心选址问题的免疫算法中，抗原对应于城市应急系统选址问题及其约束条件，一个抗体就表示一个选址规划方案，亲和度是对选址规划方案的评价结果。针对多目标配送中心系统选址问题，免疫算法的设计将在抗体的编码、亲和度的计算、抗体浓度、生存能力、选择变异操作等几个方面进行展开。　

　　Ｓｔｅｐ１：参数初始化。设置最大进化代数、初始种群大小。　

　　Ｓｔｅｐ２：产生初始抗体。每个抗体代表一个选址方案，表示为一个长度为ｐ客户点序号序列，这里ｐ表示为配送中心数量。　

　　Ｓｔｅｐ　３：计算亲和度。抗原与抗体ｖ之间的亲和度Ａｖ可以由目标函数的变换得到，本文取目标函数的倒数，即：　

　　上式的第二项表示对违反距离约束的解给予惩罚，Ｍ取比较大的正数。　

　　抗体与抗体之间的亲和度反映了抗体之间的相似程度。本文采用了一种依据抗体匹配度的亲和度计算方法，方法为：将其中一个抗体中配送中心的序号和另一个抗体中配送中心的序号逐一比较，得到序号相同的配送中心的个数，将匹配的个数之和除以抗体长度，得到这两个抗体的亲和度。　

　　Ｓｔｅｐ４：计算抗体浓度　

　　抗体浓度ｃｖ的计算方法为：　

　　其中，Ｎ表示抗体个数；Ｂ

ｖ，ｗ为抗体ｖ、ｗ之间的亲和度，Ｔ

ａｃ１

为设定的抗体亲和度阈值。　

　　Ｓｔｅｐ５：产生记忆／抑制细胞　

　　在计算过程中，当一种抗体ｖ的浓度ｃｖ超过一设定的阈值Ｔ

ｃ

时，表明抗体ｖ在群体中占据了较大优势，达到了一个相对最优点，这时生成一个记忆细胞，以记录此局部最优解。

如果记忆细胞库已满，则与抗原亲和度最低的记忆细胞被新产生的有较高抗原亲和度的记忆细胞取代。记忆细胞同时也是抑制细胞，对那些与记忆细胞有较高亲和度的抗体产生抑制作用，使它们的生存力降低。这样做的目的是保证免疫算法不会陷入局部最优解。　

　　Ｓｔｅｐ６：计算抗体生存力　

　　生存力是抗体在下一步的选择中生存下来的期望值，计算公式为：　

　　式中，ｓ表示记忆／抑制细胞；Ｍ表示记忆／抑制细胞的个数；Ｂ

，

ｖ

为设定的记忆细胞亲和度阈值。可见，当抗ｓ为抗体ｖ与记忆／抑制细胞之间的亲和度，Ｔ

ａｃ２

体与抗原的亲和度较大时，抗体存活到下一代的能力较强；当抗体与记忆／抑制细胞亲和度较大时，抗体生存能力降低；浓度较高的抗体，即相似的抗体，受到抑制，这保证了抗体的多样性。　

　　Ｓｔｅｐ７：选择、交叉和变异　

　　１）选择：对群体中的抗体按照各自的生存力进行选择，采用的是赌轮选择的方式。　　　２）交叉：从抗体中随机选择两个父串。这两个父串分别为：　

：１　２　５　６　７　９　

　　Ｐ

１

　　Ｐ

：３　４　７　８　９　１０　

２

　　父串中相同的序号分别移到各自的前端。剩下的按照两点交叉进行交叉操作。如：　

　　　　烟草配送是一种典型的企业物流，与普通的企业物流相比，它具有一些特点，就与即将讨论的问题有关的角度来说，有如下几个方面：　

　　客户相对稳定　

　　烟草配送的客户是经过烟草专卖许可审批的商户，客户信息都在烟草专卖管理部门有备案；同时，专卖部门在审批时，还需要考虑零售户的合理化布局。总之，烟草配送的客户的分布是受宏观控制的，其数量和分布都是相对稳定的。　

　　送货量可预测　

　　由于零售户相对稳定，而且其需求量总是和商户经营规模有关，除了重大节日等因素影响外，零售户的烟草需求量是基本稳定的。进一步，即使考虑需求量的变动因素，需求量也可以通过分析往年需求数量而得到较为准确的估计。　

　　送货期可规划　

　　送货周期是指针对每个零售户，相邻两次送货时间的间隔。当然，也可能存在间隔时间不等的情况，那么送货周期可以更泛化为送货计划。过长的送货周期会带给客户一定的资金积压。排除此因素，烟草的送货周期是可以规划和修改的。　

　　通过以上分析，烟草配送业务中存在着两个方面的优化问题：一是配送周期的优化，二是配送线路的优化。　

　　３．２访送周期的优化　

　　３．２．１问题描述　

　　由于烟草的订单是通过主动电话访销得到的，配送总是访销结合在一起，所以烟草的配送周期也称为访送周期。访送周期的长度关系到如下两个方面：一是客户的资金积压：访送周期越长，客户资金积压越多；在另一方面，由于每次配送涉及的客户较少，配送任务优化越简单。所以，一个适合的配送周期是上述两个方面因素的平衡。　

　　当前安徽烟草的配送一般采用周（７天）为一个访送周期，在此前提下，访送周期优化问题可以归结为一个客户分群问题：如何将所有客户分为若干个群，每个群对应于一个访送日。使得每个群内的客户相似性较强（较为临近），而不同群内的客户相似性较弱（较为远离）。这个描述可以归结为典型的聚类分析问题。此外，还要求每个群内的客户需求总量大致均衡。　

　　３．２．２聚类分析算法　

　　聚类分析是数据挖掘中的一个很活跃的研究领域，聚类算法可以被分为划分方法、层次方法、基于密度方法、基于网格方法和基于模型方法等类型。　

　　划分方法（ＰＡＭ：ＰＡｒｔｉｔｉｏｎｉｎｇ　Ｍｅｔｈｏｄ）　［９］　的思想是首先创建ｋ个划分，然后利用一个循环定位技术通过将对象从一个划分移到另一个划分来改善划分质量。典型的划分方法包括：ｋ－ｍｅａｎｓ［１０］、ｋ－ｍｅｄｏｉｄｓ［１１］、ＣＬＡＲＡ［１１］等。　

　　层次方法创建一个层次以分解给定的数据集，具有自上而下（分解）和自下而上（合并）两种操作方式。典型的层次方法包括：ＢＩＲＣＨ［１２］、ＣＵＲＥ［１３］等。　

　　基于密度方法根据密度完成对象的聚类。它根据对象周围的密度（不断增长聚类。典型的基于密度方法包括：ＤＢＳＣＡＮ［１４］、ＯＰＴＩＣＳ［１５］等。　

　　基于网格方法首先将对象空间划分为有限个单元以构成网格结构；然后利用网格结构完成聚类。典型的机遇网格的方法包括：ＳＴＩＮＧ［１６］　、ＣＬＩＱＵＥ［１７］。　

　　基于模型方法假设每个聚类的模型并发现适合相应模型的数据。典型的基于模型方法包括：统计方法ＣＯＢＷＥＢ［１８］、ＣＬＡＳＳＩＴ［１９］等。　

　　３．２．３访送周期优化策略　

　　层次聚类方法（如ＣＵＲＥ）具有处理噪声数据的能力，而且可以挖掘任意形状的簇，但是该类算法复杂度较高［２０］；而划分聚类方法（如Ｋ－ｍｅａｎｓ）复杂度较低，但是该类算法只能发现非凹的球状簇，对于噪声数据很敏感［２１，２２］。因此，将这两类算法结合，恰好可以互为补充，相得益彰［２３］。基于上述思想，烟草访送周期优化问题的求解步骤为：　

　　定义簇间距离为：对于待聚类的数据集Ｓ，Ｃｉ和Ｃｊ表示其中任意两个簇，它们之间的距离为：两个簇间所有数据对象对之间的最小距离。而数据对象之间的距离定义为：依据道路行驶规则可达的最短距离。　

　　假设希望得到的最终聚类个数为ｋ，即将所有零售户分配到ｋ个访送日中去。假设日均送货量为Ａ。　

　　Ｓｔｅｐ１：随即抽取所有客户点集的样本数据集Ｓ。　

　　Ｓｔｅｐ２：使用Ｋ－ＭＥＡＮＳ　方法将Ｓ　划分为ｋ′个簇（ｋ′一般取ｋ值的１００倍或更大值），得到所有样本数据粗糙聚类集合Ｓ′。　

　　Ｓｔｅｐ３：根据距离定义每次寻找Ｓ′中距离最近的两个簇Ｃ

ｉ和Ｃ

ｊ

，将Ｃ

ｊ

合并入Ｃ

ｉ

中，并

把Ｃ

ｊ

从Ｓ′中删除。并重新计算新簇的中心和代表点集。新簇的代表点集的选择原则是：第

一个代表点是离簇中心最远的一个点，随后的代表点是离前一个选择的代表点最远的点。合

并后返回Ｃ

ｉ

。　

　　Ｓｔｅｐ４：如果据类数目为ｋ或类中需求总量大大于等于Ａ，则停止；否则，转至Ｓｔｅｐ３。　　　３．３配送线路优化　

　　３．３．１问题描述　

　　在制定了访送周期后，每日的配送对象被为特定的客户群。在此基础上，配送线路优化问题可以描述为：将每日的配送任务分配给若干台配送车辆去完成，使得所有参与配送车辆的运行路线总长度为最小。同时，还要求每台配送车辆的配送任务量相对均衡。　

　　烟草配送线路优化问题属于典型的车辆路径问题（ＶＲＰ，Ｖｅｈｉｃｌｅ　Ｒｏｕｔｉｎｇ　Ｐｒｏｂｌｅｍ）。ＶＲＰ问题的一般定义为：对一系列送货点和（或）取货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件（如客户的货物需求量、发送量、交发货时间、车辆容量、车辆行驶里程、时间等）下，达到一定的目标（如车辆数目最少、里程最短、成本最少、时间最短等）。　

　　３．３．２ＶＲＰ求解算法　

　　ＶＲＰ问题是ＮＰ问题，研究者们已经提出了许多求解的方法。同时有研究［２４，２５］表明，现有的求解方法大体上可以分为三类：　

　　精确算法（ｅｘａｃｔ　ａｌｇｏｒｉｔｈｍ）　　　精确算法指可以求出其最优解的方法，精确算法主要有：最小Ｋ－树法（ｍｉｎｉｍｕｍ　Ｋ－ｔｒｅｅｓ）［２６］，分枝定界法（ｂｒａｎｃｈ　ａｎｄ　ｂｏｕｎｄ　ａｐｐｒｏａｃｈ）［２７］，割平面法（ｃｕｔｔｉｎｇ　ｐｌａｎｅｓ　ａｐｐｒｏａｃｈ）［２８］，网络流算法（ｎｅｔｗｏｒｋ　ｆｌｏｗ　ａｐｐｒｏａｃｈ）［２９］，动态规划法（ｄｙｎａｍｉｃ　ｐｒｏｇｒａｍｍｉｎｇ　ａｐｐｒｏａｃｈ）［３０］等，这些方法虽然可以求得精确解，但主要用于小规模问题，对于烟草配送来说并不适用。　　　对于大规模的优化问题，执着地追求精确解往往是不明智的，可取的做法是只要寻求满意解。原因在于如下两点：首先，冲突的多个目标往往导致问题不存在严格的最优解；其次，获得某些问题最优解的成本太大。基于上述思想，衍生出ＶＲＰ问题的很多重要的求解算法，总称为启发式算法。　

　　经典启发式算法（ｈｅｕｒｉｓｔｉｃｓ　ａｌｇｏｒｉｔｈｍ）　

　　启发式算法是通过对过去经验的归纳推理以及实验分析来解决问题的方法，即借助于某种直观推断或试探的方法。目前提出的启发式算法有以下几类［３１］。　

　　构造算法（ｃｏｎｓｔｒｕｃｔｉｖｅ　ａｌｇｏｒｉｔｈｍ）［３２，３３］根据某种启发准则，每次将一个不在已划好线路上的点增加进该线路，直到所有的点都被安排到线路中为止。两阶段算法（ｔｗｏ－ｐｈａｓｅ　ａｌｇｏｒｉｔｈｍ）［３４，３５，３６，３７］是在第一阶段得到一可行解，第二阶段通过对点的调整，在始终保持解可行的情况下，力图不断向最优目标靠近。　

　　现代启发算法　

　　现代启发式算法（亚启发式算法）主要包括禁忌搜索算法（ｔａｂｕ　ｓｅａｒｃｈ）［３８，３９，４０］，遗传算法（ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ）［４１，４２］，模拟退火法（ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ）［４３，４４］及神经网络（ｎｅｕｒａｌ　ｎｅｔｗｏｒｋ）［４５，４６］等，它们是近年来出现的用于求解较复杂的ＶＲＰ问题的方法，能有效改善求解的性能。　

　　３．３．３配送线路优化策略　

　　１、问题的数学模型　

　　假设配货中心有Ｋ辆车，车辆ｋ的载重量为Ｗ

ｋ

（ｋ　＝１，２，？，Ｋ　）　，一次配货的最大行驶

距离为Ｄ

ｋ；需要向ｍ个客户送货，客户ｊ的需求量为ｑ

ｊ

；客户ｉ　到客户ｊ的距离为ｄ

ｉ

，ｊ　，

配货中心到客户ｊ　的距离为ｄ　０，ｊ；第ｋ辆车的配送线路为Ｌ

ｋ（　ｒ

０

，ｒ

１

，？，ｒｎｋ　，ｒ

０

）　，

其中ｒ

ｉ表示配货线路上第ｉ个客户的客户号，ｒ

０

表示配送中心，ｎｋ　表示第ｋ辆车的配货线

路上的客户总数。烟草配送线路问题的数学模型为：　　

　　２、算法描述　

　　禁忌搜索算法的基本思想是：随机给出一个初始解作为当前解，在当前解的邻域中确定若干候选解；如果某一候选解对应的目标值满足藐视规则，则用它替换当前解，并将它加入禁忌表；如果不存在上述解，则选择候选解中的非禁忌的最佳状态为当前解，并将其加入禁忌表；重复上述过程直至满足终止准则。　

　　禁忌搜索算法可做如下改善：每次从一个解的倒、正序两个方向同时搜索，扩大了邻域的搜索范围，提高算法的整体寻优能力。　

　　（１）　解的表示方法：对于有ｍ个客户的车辆路径问题，解表示为一个ｍ个数的排列，排列中的每个数分别表示一个客户的客户号。　

　　（２）　邻域的搜索：本文采用互换法进行邻域操作，即随机交换２个点的位置。　为了减少对当前解的依赖，采用了从当前解的正、倒序２个方向同时搜索的方法。　

　　（３）　禁忌对象的确定：禁忌对象是指那些被置入禁忌表中的变化元素，禁忌的目的是为了避免迂回搜索，这里将每次迭代的最优解作为禁忌对象。　

　　（４）　禁忌长度和候选解的确定：禁忌长度是禁忌对象在不考虑藐视准则的情况下不允许被选取的最大次数，禁忌长度的选取与问题特征和经验有关，它决定了算法的复杂度。本文选取的禁忌长度为ｍ　（ｍ为客户数）。候选解在当前解的邻域中选取，本文分别从每个状态的邻域中选取最优的５个作为候选解。　

　　（５）　藐视准则：在禁忌搜索中，可能会出现候选解全部被禁忌的情况。藐视准则可使某状态解禁。本文采用的是基于适配值的藐视准则，如某个候选解被禁忌，但它的目标值较优，则解禁此候选解。　

　　（６）　终止准则：本文采用了指定迭代步长的终止准则。　

　　４、结语　

　　烟草物流是一个复杂的系统，本文对其中的４个优化问题进行了研究。总体来说，研究都不够深入，表现在：１、相关算法都没有在真实数据环境中得到完全的验证；２、一些求解模型的假设损害了算法的实际可操作性或效果；３、虽然大多数的启发式算法都可对同一个优化问题进行求解，但其适应性和效果也存在差别，文章未及对此进行讨论。　

参考文献　

１、孙焰编著．现代物流管理技术．同济大学出版社．２００４．０８　

２、　Ｈａｋｉｍｉ　Ｓ　Ｌ．Ｏｐｔｉｍｕｍ　ｄｉｓｔｒｉｂｕｔｉｏｎ　ｏｆ　ｓｗｉｔｃｈｉｎｇ　ｃｅｎｔｅｒｓ　ｉｎ　ａ　ｃｏｍｍｕｎｉｃａｔｉｏｎ　ｎｅｔｗｏｒｋ　ａｎｄ　ｓｏｍｅ　ｒｅｌａｔｅｄ　ｇｒａｐｈ　ｔｈｅｏｒｅｔｉｃ　ｐｒｏｂｌｅｍｓ［Ｊ］．Ｏｐｅｒａｔｉｏｎｓ　

Ｒｅｓｅａｒｃｈ，１９６５，１３（１）：４６２－４７５　

３、　Ｋａｒｉｖ　Ｏ，　Ｈａｋｉｍｉ　Ｓ　Ｌ．Ｔｈｅ　ｐ－ｍｅｄｉａｎ　ｐｒｏｂｌｅｍｓ．Ｉｎ：Ａｎ　ａｌｇｏｒｉｔｈｍｉｃ　ａｐｐｒｏａｃｈ　ｔｏ　ｎｅｔｗｏｒｋ　ｌｏｃａｔｉｏｎ　ｐｒｏｂｌｅｍｓ［Ｊ］．ＳＩＡＭ　Ｊｏｕｒｎａｌ　ｏｎ　Ａｐｐｌｉｅｄ　Ｍａｔｈｅｍａｔｉｃｓ，１９７９，３７（１）：５３９－５６０　

４、胡朝阳，文福拴．免疫算法与其它模拟进化优化算法的比较研究［Ｊ］．电力情报，１９９８，（１）：６１－６３．　　

５、Ｃｈｕｎ　Ｊａｎｇ－Ｓｕｎｇ，Ｊａｎｇ　Ｈｙｕｎ－ｋｙｏ，Ｈａｈｎ　Ｓｏｎｇ－Ｙｏｐ．Ａ　ｓｔｕｄｙ　ｏｎ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｅｒｆｏｒｍａｎｃｅｓ　ｂｅｔｗｅｅｎ　ｉｍｍｕｎｅ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｏｔｈｅｒ　ｈｅｕｒｉｓｔｉｃ　ａｌｇｏｒｉｔｈｍｓ［Ｊ］．ＩＥＥＥ　

Ｔｒａｎｓａｃｔｉｏｎ　ｏｎ　Ｍａｇｎｅｔｉｃｓ，１９９８，３４（５），２９７２－２９７５．　

６、　Ｇｅ　Ｈｏｎｇ，ａｏ　Ｚｏｎｇ－Ｙｕａｎ．Ｉｍｍｕｎｅ　Ａｌｇｏｒｉｔｈｍ［Ｃ］．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　４ｔｈ　Ｗｏｒｌｄ　Ｃｏｎｇｒｅｓｓ　ｏｎ　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｃｏｎｔｒｏｌ　ａｎｄ　Ａｕｔｏｍａｔｉｏｎ，２００１：１７８４－１７８８．　

７、Ｔｏｒｅｇａｓ　Ｃ，　Ｓｗａｉｎ　Ｒ，　Ｒｅｖｅｌｌｅ　Ｃ，ｅｔａｌ．　Ｔｈｅ　ｌｏｃａｔｉｏｎ　ｏｆ　ｅｍｅｒｇｅｎｃｙ　ｓｅｒｖｉｃｅ　

ｆａｃｉｌｉｔｉｅｓ［Ｊ］．Ｏｐｅｒａｔｉｏｎｓ　Ｒｅｓｅａｒｃｈ，１９７１，１９（２）：１３６３－１３７３　

８、　Ｃｈａｕｄｈｒｙ　Ｓ　Ｓ，Ｈｅ　Ｓ　Ｗ，Ｃｈａｕｄｈｒｙ　Ｐ　Ｅ．　Ｓｏｌｖｉｎｇ　ａ　ｃｌａｓｓ　ｏｆ　ｆａｃｉｌｉｔｙ　ｌｏｃａｔｉｏｎ　ｐｒｏｂｌｅｍｓ　ｕｓｉｎｇ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ［Ｊ］．Ｅｘｐｅｒｔ　Ｓｙｓｔｅｍｓ，２００３，２０（２）：８６－９１　

９、　Ｌ．　Ｋａｕｆｍａｎ　ａｎｄ　Ｐ．Ｊ．　Ｒｏｕｓｓｅｅｕ．　Ｆｉｎｄｉｎｇ　Ｇｒｏｕｐｓ　ｉｎ　Ｄａｔａ．　Ｗｉｌｅｙ，Ｎｅｗ　Ｙｏｒｋ，　１９８９．　１０、ＭａｃＱｕｅｅｎ　Ｊ．　Ｓｏｍｅ　ｍｅｔｈｏｄｓ　ｆｏｒ　ｃｌａｓｓｉｆｉｃａｔｉｏｎ　ａｎｄ　ａｎａｌｙｓｉｓ　ｏｆ　ｍｕｌｔｉｖａｒｉａｔｅ　

ｏｂｓｅｒｖａｔｉｏｎｓ：　ｐｒｏｃ．　ｏｆ　ｔｈｅ　５ｔｈ　Ｂｅｒｋｅｌｅｙ　Ｓｙｍｐｏｎ　Ｍａｔｈ　Ｓｔａｔｉｓｔ　［Ｃ　］．　１９６７：　２８１２２９７．　１１、Ｌ．　Ｋａｕｆｍａｎ　ａｎｄ　Ｐ．　Ｒｏｕｓｓｅｅｕｗ，　Ｆｉｎｄｉｎｇ　ｇｒｏｕｐｓ　ｉｎ　ｄａｔａ：　ａｎ　ｉｎｔｒｏｄｕｃｔｉｏｎ　ｔｏ　ｃｌｕｓｔｅｒ　ａｎａｌｙｓｉｓ．　Ｎｅｗ　Ｙｏｒｋ：　Ｊｏｈｎ　Ｗｉｌｅｙ　ａｎｄ　Ｓｏｎｓ，　１９９０．　

１２、　Ｔ．　Ｚｈａｎｇ，　Ｒ．　Ｒａｍａｋｒｉｓｈｎａｎ，　ａｎｄ　Ｍ．　Ｌｉｖｎｙ，“Ｂｉｒｃｈ：　Ａｎ　ｅｆｆｉｃｉｅｎｔ　ｃｌｕｓｔｅｒｉｎｇ　ｍｅｔｈｏｄ　ｆｏｒ　ｖｅｒｙ　ｌａｒｇｅ　ｄａｔａｂａｓｅｓ，”　ｉｎ　ＡＣＭ　ＳＩＧＭＯＤ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｒｅｓｅａｒｃｈ　Ｉｓｓｕｅｓ　ｏｎ　Ｄａｔａ　Ｍｉｎｉｎｇ　ａｎｄ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ，　（Ｍｏｎｔｒｅａｌ），　ｐｐ．　１０３–１１４，　１９９６．　

１３、　Ｓ．　Ｇｕｈａ，　Ｒ．　Ｒａｓｔｏｇｉ，　ａｎｄ　Ｋ．　Ｓｈｉｍ，　“Ｃｕｒｅ：　ａｎ　ｅｆｆｉｃｉｅｎｔ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｌａｒｇｅ　ｄａｔａｂａｓｅｓ，”ｉｎ　ＡＣＭ　ＳＩＧＭＯＤ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　ｔｈｅ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ，　（Ｓｅａｔｔｌｅ，　ＷＡ，　ＵＳＡ），ｐｐ．　７３–８４，　１９９８．　

１４、　Ｍ．　Ｅｓｔｅｒ，　Ｈ．－Ｐ．　Ｋｒｉｅｇｅｌ，　Ｊ．　Ｓａｎｄｅｒ，　ａｎｄ　Ｘ．　Ｘｕ，　“Ａ　ｄｅｎｓｉｔｙ－ｂａｓｅｄ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｄｉｓｃｏｖｅｒｉｎｇ　ｃｌｕｓｔｅｒｓ　ｉｎ　ｌａｒｇｅ　ｓｐａｔｉａｌ　ｄａｔａｂａｓｅｓ　ｗｉｔｈ　ｎｏｉｓｅ，”　ｉｎ　Ｓｅｃｏｎｄ　

Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｋｎｏｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ　（Ｅ．　Ｓｉｍｏｕｄｉｓ，　Ｊ．　Ｈａｎ，　ａｎｄ　Ｕ．　Ｆａｙｙａｄ，　ｅｄｓ．），　（Ｐｏｒｔｌａｎｄ，　ＯＲ），　ｐｐ．　２２６–２３１，ＡＡＡＩ　Ｐｒｅｓｓ，　１９９６．　

１５、　Ａｎｋｅｒｓｔ　Ｍ，　Ｂｒｅｕｎｉｇ　Ｍ，　Ｋｒｉｅｇｅｌ　Ｈ，　ｅｔ　ａｌ．　ＯＰＴＩＣＳ：　Ｏｒｄｅｒｉｎｇ　Ｐｏｉｎｔｓ　ｔｏ　Ｉｄｅｎｔｉｆｙ　ｔｈｅ　Ｃｌｕｓｔｅｒｉｎｇ　Ｓｔｒｕｃｔｕｒｅ［Ｃ］／／Ｐｒｏｃ．　ｏｆ　ＡＣＭ　Ｓｉｇｍｏｄ　Ｉｎｔ．　Ｃｏｎｆ．　ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ．　１９９９：　４９－６０．　　

１６、Ｗａｎｇ　Ｗｅｉ，　Ｙａｎｇ　Ｊｉｏｎｇ，　Ｍｕｎｔｚ　Ｒ．　ＳＴＩＮＧ：　Ａ　Ｓｔａｔｉｓｔｉｃａｌ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｇｒｉｄ　Ａｐｐｒｏａｃｈ　ｔｏ　Ｓｐａｔｉａｌ　Ｄａｔａ　Ｍｉｎｉｎｇ［Ｃ］／／Ｐｒｏｃ．　ｏｆ　ｔｈｅ　２３ｒｄ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｖｅｒｙ　Ｌａｒｇｅ　Ｄａｔａ　Ｂａｓｅｓ，　１９９７．　

１７、　Ｒａｋｅｓｈ　Ａ，　Ｊｏｈａｎｎｅｒｓ　Ｇ，　Ｄｉｍｉｔｒｉｏｓ　Ｇ，　Ｐｒａｂｈａｋａｒ　Ｒ．　Ａｕｔｏｍａｔｉｃ　ｓｕｂｓｐａｃｅ　ｃｌｕｓｔｅｒｉｎｇ　ｏｆ　ｈｉｇｈ　ｄｉｍｅｎｓｉｏｎａｌ　ｄａｔａ　ｆｏｒ　ｄａｔａ　ｍｉｎｉｎｇ　ａｐｐｌｉｃａｔｉｏｎｓ．　Ｉｎ：　Ｓｎｏｄｇｒａｓｓ　ＲＴ，　Ｗｉｎｓｌｅｔｔ　Ｍ，　ｅｄｓ．　Ｐｒｏｃ．　ｏｆ　ｔｈｅ　１９９４　ＡＣＭ　ＳＩＧＭＯＤ　Ｉｎｔ’ｌ　Ｃｏｎｆ．　ｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ．　Ｍｉｎｎｅａｐｏｌｉｓ：　ＡＣＭ　Ｐｒｅｓｓ，　１９９４．　９４￣１０５．　　

１８、　Ｈａｎ　Ｊｉａｗｅｉ，　Ｋａｍｂｅｒ　Ｍ．　Ｄａｔａ　Ｍｉｎｉｎｇ：　Ｃｏｎｃｅｐｔｓ　ａｎｄ　Ｔｅｃｈｎｉｑｕｅｓ［Ｍ］．　Ｓａｎ　Ｆｒａｎｃｉｓｃｏ：　Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ　Ｐｕｂｌｉｓｈｅｒｓ，　２０００．　　

１９、　êＧｅｎｎａｒｉ，êＪ．êＨ．，êＬａｎｇｌｅｙ，êＰ．，êａｎｄêＦｉｓｈｅｒ，êＤ．　Ｍｏｄｅｌｓ　ｏｆ　ｉｎｃｒｅｍｅｎｔａｌ　ｃｏｎｃｅｐｔ　ｆｏｒｍａｔｉｏｎ．　Ａｒｔｉｆｉｃｉａｌ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，　４０，　ｐｐ．ê１１－６１；　１９８９．　

２０、Ｃｈｅｎ　Ｎｉｎｇ，　Ｃｈｅｎ　Ａｎ，　Ｚｈｏｕ　Ｌｏｎｇ－　ｘｉａｎｇ．Ａｎ　ｅｆｆｅｃｔｉｖｅ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｉｎ　ｌａｒｇｅ　ｔｒａｎｓａｃｔｉｏｎ　ｄａｔａｂａｓｅｓ［Ｊ］．Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ，　２００１，　１２（４）　：　４７５－　４８４．　

２１、Ｈａｎ　Ｊｉａ－　ｗｅｉ，　Ｋａｍｂｅｒ　Ｍ．Ｄａｔａ　ｍｉｎｉｎｇ：　ｃｏｎｃｅｐｔｓ　ａｎｄ　ｔｅｃｈｎｉｑｕｅｓ　［Ｍ］．［Ｓ．ｌ．］：　Ｈｉｇｈｅｒ　Ｅｄｕｃａｔｉｏｎ　Ｐｒｅｓｓ，　Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ　Ｐｕｂｌｉｓｈｅｒｓ，　２００２．　

２２、　甄彤．基于层次与划分方法的聚类算法研究［Ｊ］．计算机工程与应用，２００６，　４２（　８）　：　１７８－　１８０．　

２３、袁方，　孟增辉，　于戈．对ｋ－　ｍｅａｎｓ　聚类算法的改进［Ｊ］．计算机工程与应用，　２００４，　

４０（　３６）　：　１７７－　１７８．　

２４、Ｌａｐｏｒｔｅ　Ｇ．Ｔｈｅ　Ｖｅｈｉｃｌｅ　Ｒｏｕｔｉｎｇ　Ｐｒｏｂｌｅｍ：Ａｎ　ｏｖｅｒｖｉｅｗ　ｏｆ　ｅｘａｃｔ　ａｎｄ　ａｐｐｒｏｘｉｍａｔｅ　ａｌｇｏｒｉｔｈｍｓ．Ｅｕｒｏｐｅａｎ　Ｊｏｕｒｎａｌ　ｏｆ　Ｏｐｅｒａｔｉｏｎａｌ　Ｒｅｓｅａｒｃｈ，１９９２，５（９）：３４５－３５８　

２５、Ｌａｐｏｒｔｅ　Ｇ，Ｏｓｍａｎ　Ｈ．Ｒｏｕｔｉｎｇ　ｐｒｏｂｌｅｍｓ：ａ　ｂｉｂｌｉｏｇｒａｐｈｙ．Ａｎｎａｌｓ　ｏｆ　Ｏｐｅｒａｔｉｏｎｓ　

Ｒｅｓｅａｒｃｈ，１９９５，（６１）：２２７－２６２　

２６、Ｆｉｓｈｅｒ　Ｍ　Ｌ．Ｏｐｔｉｍａｌ　ｓｏｌｕｔｉｏｎ　ｏｆ　ｖｅｈｉｃｌｅ　ｒｏｕｔｉｎｇ　ｐｒｏｂｌｅｍｓ　ｕｓｉｎｇ　ｍｉｎｉｍｕｍ　

ｋ－ｔｒｅｅｓ．Ｏｐｅｒａｔｉｏｎｓ　Ｒｅｓｅａｒｃｈ，１９９４，４２（４）：６２６－６４２　

２７、　Ｌａｐｏｒｔｅ　Ｇ．Ｔｈｅ　Ｖｅｈｉｃｌｅ　Ｒｏｕｔｉｎｇ　Ｐｒｏｂｌｅｍ：Ａｎ　ｏｖｅｒｖｉｅｗ　ｏｆ　ｅｘａｃｔ　ａｎｄ　ａｐｐｒｏｘｉｍａｔｅ　ａｌｇｏｒｉｔｈｍｓ．　Ｅｕｒｏｐｅａｎ　Ｊｏｕｒｎａｌ　ｏｆ　Ｏｐｅｒａｔｉｏｎａｌ　Ｒｅｓｅａｒｃｈ，１９９２，５（９）：３４５－３５８　

２８、　Ｂａｌｉｎｓｋｉ　Ｍ，Ｑｕａｎｄｔ　Ｒ．Ｏｎ　ａｎ　ｉｎｔｅｇｅｒ　ｐｒｏｇｒａｍ　ｆｏｒ　ａ　ｄｅｌｉｖｅｒｙ　ｐｒｏｂｌｅｍ．Ｏｐｅｒａｔｉｏｎｓ　Ｒｅｓｅａｒｃｈ，１９６２，（１２）：３００－３０　

２９、Ｌａｐｏｒｔｅ　Ｇ，Ｎｏｂｅｒｔ　Ｙ，Ｄｅｓｒｏｃｈｅｒ　Ｍ．Ｏｐｔｉｍａｌ　ｒｏｕｔｉｎｇ　ｕｎｄｅｒ　ｃａｐａｃｉｔｙ　ａｎｄ　ｄｉｓｔａｎｃｅ　ｒｅｓｔｒｉｔｉｏｎｓ．Ｏｐｅｒａｔｉｏｎｓ　Ｒｅｓｅａｒｃｈ，１９８５，（３３）：１０５０－１０７３　

３０、Ｅｉｌｏｎ　Ｓ，Ｗａｔｓｏｎ　Ｄ　Ｔ，Ｃｈｒｉｓｔｏｆｉｄｅｓ　Ｎ，Ｄｉｓｔｒｉｂｕｔｉｏｎ　ｍａｎａｇｅｍｅｎｔ：ｍａｔｈｅｍａｔｉｃａｌ　

ｍｏｄｅｌｌｉｎｇ　ａｎｄ　ｐｒａｃｔｉｃａｌ　ａｎａｌｙｓｉｓ．Ｌｏｎｄｏｎ：Ｇｒｉｆｆｉｎ，１９７１　

３１、Ｃｅｓａｒ　Ｒｅｇｏ．Ａ　ｓｕｂｐａｔｈ　ｅｊｅｃｔｉｏｎ　ｍｅｔｈｏｄ　ｆｏｒ　ｔｈｅ　ｖｅｈｉｃｌｅ　ｒｏｕｔｉｎｇ　ｐｒｏｂｌｅｍ．　Ｍａｎａｇｅｍｅｎｔ　Ｓｃｉｅｎｃｅ，１９９８，４４（１０）：１４４７－１４５９　

３２、Ｃｌａｒｋｅ　Ｇ，Ｗｒｉｇｈｔ　Ｊ　Ｗ．Ｓｃｈｅｄｕｌｉｎｇ　ｏｆ　ｖｅｈｉｃｌｅｓ　ｆｒｏｍ　ａ　ｃｅｎｔｒａｌ　ｄｅｐｏｔ　ｔｏ　ａ　ｎｕｍｂｅｒ　ｏｆ　ｄｅｌｉｖｅｒｙ　ｐｏｉｎｔｓ．Ｏｐｅｒａｔｉｏｎｓ　Ｒｅｓｅａｒｃｈ，１９６４，（１２）：５６８－５８１　３３、Ｇｅｎｄｒｅａｕ　Ｍ，Ｈｅｒｔｚ　Ａ，Ｌａｐｏｒｔｅ　Ｇ．Ｔｈｅ　ｔｒａｖｅｌｉｎｇ　ｓａｌｅｓｍａｎ　ｐｒｏｂｌｅｍ　ｗｉｔｈ　

ｂａｃｋｈａｕｌｓ．Ｃｏｍｐｕｔｅｒｓ＆Ｏｐｅｒａｔｉｏｎｓ　Ｒｅｓｅａｒｃｈ，１９９６，（２３）：５０１－５０８　

３４、Ｇｉｌｌｅｔｔ　Ｂ，Ｍｉｌｌｅｒ　Ｌ．Ａ　ｈｅｕｒｉｓｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｈｅ　ｖｅｈｉｃｌｅ　ｄｉｓｐａｔｃｈ　

ｐｒｏｂｌｅｍ．Ｏｐｅｒａｔｉｏｎｓ　Ｒｅｓｅａｒｃｈ　Ｑｕａｒｔｅｒｌｙ，１９７６，（２７）：３６７－３８４　

３５、Ｒｅｎａｕｄ　Ｊ，Ｂｏｃｔｏｒ　Ｆ，Ｌａｐｏｒｔｅ　Ｇ．Ａｎ　ｉｍｐｒｏｖｅｄ　ｐｅｔａｌ　ｈｅｕｒｉｓｔｉｃ　ｆｏｒ　ｔｈｅ　ｖｅｈｉｃｌｅ　ｒｏｕｔｉｎｇ　ｐｒｏｂｌｅｍ．Ｊｏｕｒｎａｌ　ｏｆ　Ｏｐｅｒａｔｉｏｎａｌ　Ｒｅｓｅａｒｃｈ　Ｓｏｃｉｅｔｙ，１９９６，４７：３２９－３３６　

３６、Ｌｉｎ　Ｓ．Ｃｏｍｐｕｔｅｒ　ｓｏｌｕｔｉｏｎｓ　ｏｆ　ｔｈｅ　ｔｒａｖｅｌｌｉｎｇ　ｓａｌｅｓｍａｎ　ｐｒｏｂｌｅｍ．Ｂｅｌｌ　ｓｙｓｔｅｍ　

Ｔｅｃｈｎｉｃａｌ　Ｊｏｕｒｎａｌ，１９６５，（４４）：２２４５－２２６９　

３７、　Ｔｏｔｈ　Ｐ，Ｖｉｇｏ　Ｄ．Ａ　ｈｅｕｒｉｓｔｉｃａ　ｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｈｅ　ｓｙｍｍｅｔｒｉｃ　ａｎｄ　ａｓｙｍｍｅｔｒｉｃ　ｒｏｕｔｉｎｇ　ｐｒｏｂｌｅｍｓ　ｗｉｔｈ　ｂａｃｋｈａｕｌｓ．Ｅｕｒｏｐｅａｎ　Ｊｏｕｒｎａｌ　ｏｆ　Ｏｐｅｒａｔｉｏｎａｌ　

Ｒｅｓｅａｒｃｈ，１９９９，（１１３）：５２８－５４３　

３８、Ｇｌｏｖｅｒ　Ｆ．Ｆｕｔｕｒｅ　ｐａｔｈｓ　ｆｏｒ　ｉｎｔｅｇｅｒ　ｐｒｏｇｒａｍｍｉｎｇ　ａｎｄ　ｌｉｎｋｓ　ｔｏ　ａｒｔｉｆｉｃｉａｌ　

ｉｎｔｅｌｌｉｇｅｎｃｅ．Ｃｏｍｐｕｔｅｒｓ＆Ｏｐｅｒａｔｉｏｎｓ　Ｒｅｓｅａｒｃｈ，１９８６，１（３）：５３３－５４９　

３９、Ｇｅｎｄｒｅａｕ　Ｍ，Ｈｅｒｔ　Ｚ　Ａ，Ｌａｐｏｒｔｅ　Ｇ．　Ａ　ｔａｂｕ　ｓｅａｒｃｈ　ｈｅｕｒｉｓｔｉｃ　ｐｒｏｂｌｅｍ．Ｍａｎａｇｅｍｅｎｔ　

Ｓｃｉｅｎｃｅ，１９９４，４０（１０）：１２７６－１２８９　

４０、Ｂａｒｂａｒｏｓｏｇｌｕ，Ｇｕｌａｙ，Ｏｚｇｕｒ．Ｔａｂｕ　ｓｅａｒｃｈ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｈｅ　ｖｅｈｉｃｌｅ　ｒｏｕｔｉｎｇ　

ｐｒｏｂｌｅｍ．Ｃｏｍｐｕｔｅｒｓ＆Ｏｐｅｒａｔｉｏｎａ　Ｒｅｓｅａｒｖｈ，１９９９，２６（３）：２５５－２７０　

４１、Ｏｌｉｖｅｒ　Ｍ，Ｓｍｉｔｈ　Ｄ　Ｊ，Ｈｏｌｌａｎｄ　Ｊ．Ａ　Ｓｔｕｄｙ　ｏｆ　Ｐｅｒｍｕｔａｔｉｏｎ　Ｃｒｏｓｓｏｖｅｒ　Ｏｐｅｒａｔｏｒｓ　ｏｎ　ｔｈｅ　Ｔｒａｖｅｌｉｎｇ　Ｓａｌｅｓｍａｎ　Ｐｒｏｂｌｅｍ．Ｐｒｏｃｅｅｄｉｎｇ　ｏｆ　Ｔｈｉｒｄ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍｓ，Ｍｏｒｇａｎ　Ｋａｕｆａｎｎ　Ｐｂｕｌｉｓｈｅｒｓ，１９８９，２２４－２３０　

４２、Ｆｏｇｅｌ　Ｄ　Ｅ．Ａｐｐｌｙｉｎｇ　ｅｖｏｌｕｔｉｏｎａｒｙ　ｐｒｏｇｒａｍｍｉｎｇ　ｔｏ　ｓｅｌｅｃｔｅｄ　ＴＳＰｓ．Ｃｙｂｅｍ　ａｎｄ　ｓｙｓｔ：　Ａｎ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｊｏｕｒｎａｌ，１９９３，（２４）：２７－３６　

４３、Ｏｓｍａｎ　Ｉ　Ｈ．Ｍｅｔａｓｔｒａｔｅｇｙ　ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ａｎｄ　ｔａｂｕ　ｓｅａｒｃｈ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｔｈｅ　ｖｅｈｉｃｌｅ　ｒｏｕｔｉｎｇ　ｐｒｏｂｌｅｍｓ．Ａｎｎａｌｓ　ｏｆ　Ｏｐｅｒａｔｉｏｎｓ　Ｒｅｓｅａｒｃｈ，１９９３，（４１）：４２１－４５２　

４４、Ｌａｐｏｒｔｅ　Ｇ．Ｏｓｍａｎ　Ｉ．Ｈ．，Ｍｅｔａｃｈｅｕｒｉｓｔｉｃｓ　ｉｎ　ｃｏｍｂｉｎａｔｏｒｉａｌ　ｏｐｔｉｍｉｚａｔｉｏｎ：　ａ　

ｂｉｂｌｉｏｇｒａｐｈｙ　Ａｎｎ．Ｏｐｅｒａｔｉｏｎｓ　Ｒｅｓｅａｒｃｈ，１９９６，（６３）：５１３－６２８　

４５、Ｎｙｇａｒｄ　Ｋ，Ｊｕｅｌｌ　Ｐ，Ｋａｄａｂａ　Ｎ．Ｎｅｕｒａｌ　ｎｅｔｗｏｒｋｓ　ｆｏｒ　ｓｅｌｅｃｔｉｎｇ　ｖｅｈｉｃｌｅ　ｒｏｕｔｉｎｇ　

ｈｅｒｕｒｉｓｔｉｃｓ．ＯＲＳＡ　Ｊｏｕｒｎａｌ　Ｃｏｍｐｕｔｅｒ，１９９０，（２）：３５３－３６４　

４６、Ｔｏｒｋｉ，Ａｂｄｏｌｈａｍｉｄ，Ｓｏｍｈｏｎ．Ｃｏｍｐｅｔｉｔｉｖｅ　ｎｅｕｒａｌ　ｎｅｔｗｏｒｋ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｓｏｌｖｉｎｇ　

ｖｅｈｉｃｌｅ　ｒｏｕｔｉｎｇ　ｐｒｏｂｌｅｍ．Ｃｏｍｐｕｔｅｒｓ＆Ｉｎｄｕｓｔｒｉａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ，１９９７，３３（３）：４７３－４７６　下载本文