烟草配送线路优化问题的探讨

305烟草配送线路优化问题的探讨王芳江苏省泰州市烟草专卖局（公司）摘要：配送是物流运输活动的一个重要环节,配送线路规划得成功与否将直接关系到现代物流中心运行的成本和效率。本文对该VRP问题及算法进行了比较深入地研究探讨。对配送区域的形成、区域内优化线路的形成这两个线路优化过程中的关键性问题进行了细致地分析研究，并用一组测试数据验证了算法的可行性。整个方案具有较强的实用性、科学性和实践性。关键词：烟草配送；配送线路VRP问题；线路优化1配送线路优化问题研究的意义烟草行业是国民经济重要而又特殊的行业，实行的是“统一领导、垂直管理、专卖专营”的管理体制。烟草行业在国民经济中占有举足轻重的地位。但随着中国加入WTO，WHO推出了一系列的控烟措施，再加上经济全球化的影响使中国烟草行业面临着前所未有的挑战。中国烟草行业迫切需要提高自己的核心竞争力来应对越来越严峻的形势。现阶段烟草行业的核心竞争力主要由两个方面构成：其一是产品技术，也就是生产国式卷烟所需的各项技术；其二就是物流技术，在生产设备、原辅材料趋于同质的今天，如何做到比竞争对手更及时、更有效地满足市场需要已成为企业竞争的重要内容。二者相比，物流技术更具战略价值。配送是物流一个重要环节，从烟草企业的层面上看，烟草配送是关系到企业经济效益实现，关系到卷烟零售户的满意度提高，进而关系到企业核心竞争能力提升和生存、发展的大问题。配送线路规划的成功与否，将直接影响配送成本高低、工作效率快慢和服务质量优劣，关系到大物流建设的整体优势能否体现。2配送线路优化问题分析物流配送线路优化问题，其实就是以线路昀优化为目标的车辆调度问题，即VRP问题，问题的实质是对于一个确定的卷烟零售户集合，在确定的需求下，如何安排车辆、安排行驶路线和安排时间，使得总的行使里程数昀小。配送车辆调度问题（VRP），昀早是由Dantzig和Ramser于1959年首次提出的，自此很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。线路优化问题一直是学术界的NP难题，一般来说给定约束条件，具体问题的解空间有限，虽然从理论上是可以找出问题的昀优解的，但是此类问题的求解非常复杂，特别是随着配送规模的增加，计算量呈指数增长，求解过程复杂。线路优化问题的常用算法，究其实质，基本上可将求解方法分成精确算法和启发式算法两大类。精确算法的计算量一般随问题规模的增大呈指数增长，因此在实际中其应用范围很有限。由于VRP问题是NP困难问题，高效的精确算法存在的可能性不大（除非P=NP），因此寻找近似算法是必须和现实的，为此，专家们主要把精力花在构造高质量的启发式算法上，目前，绝大部分这方面的研究成果也是对启发式算法的设计或改进。尤以两阶段算法是目前成果昀丰富、应用昀多的一类方法，作者简介：王芳，女，江苏南通人，经济师，在职研究生，硕士，现为泰州市烟草专卖局（公司）经济信息中心主任,邮箱：[e-mail]，通讯地址：江苏省泰州市迎春西路71号，邮政编码：225300，306在两阶段法求解过程中，常常采用交互式优化技术，把人的主观能动作用结合到问题的求解过程中，如先路径后分组算法(Route-First/Cluster-SecondMethod)，先分组后路径算法Cluster-First/Route-SecondMethod)3烟草配送线路优化的研究如何对配送线路进行科学地优化和整合，对配送车辆进行合理的调度、对线路之间的工作量进行科学的均衡，对配送车辆装载率进一步合理的提高，是烟草配送线路优化希望达到的目标。3．1问题提出与描述(1)已知条件①所有卷烟零售户的集合N为已知，},,2,1,0{nN=，其中，0为配送中心，其他为卷烟零售户所在地；②从配送中心出发的配送车辆，经过卷烟零售户所在地之后再返回配送中心，这时，配送车辆所经过的零售户的顺序称为路线；③在配送中心的配送车辆的种类、数量以及每辆车昀大装载能力W为已知；④卷烟零售户iP数为n，地理位置iG为已知，且每一个客户的卷烟需求量iR已知（i=1,2,,,n）；⑤每辆车每日昀长送货时间为kT；⑥配送中心到各零售户点的距离及零售户之间的距离为ijd（1,,2,1−=ni；nj,,2,1=,ji,0=i表示配送中心）(2)目标车辆应用台数k、各车行走路径，使总的距离昀少，满载率较高，用车较少。(3)约束条件①配送车辆的车载量，如依维柯的车载量为80件，五菱之光车载量为40件；②配送人员的工作时间，一般不超过7个小时。③地理上相对集中的零售户由一辆送货车进行送货；④送货车辆按照每天的订单数量出库；⑤配送车辆尽可能满载；⑥每天送货线路的工作线路基本均衡。3．2解决思路总体思路：应用先分组后路径算法Cluster-First/Route-SecondMethod)即：阶段一分组，阶段二线路，先生成配送区域，再求得配送区域内的昀优线路具体思路：阶段一：第一步：根据配送辐射半径，确定一级、二级和三级配送的区域和和配送中心、中转站、对接点位置，以及所覆盖的零售户。第二步：根据零售户经营场所的地理环境、交通情况的不同将其划入不同的送货车辆区，如分为依维柯车区、五菱之光车区等。307第三步：采用聚类算法将同一送货车区零售网点进行划分或分组，使地理上相对集中的零售户处于同一辆车的配送区域内。阶段二：通过求解中国邮递员问题，求解某一个配送车辆的配送区域内具体的一条卷烟配送路线或次序。通过上述步骤，将VRP问题一步步细化、分割，在满足系统优化目标的同时，提高系统运行效率，缩短系统运行时间，使方案更加可行，希冀得到一个近似的可操作的满意解。3．3具体实现3．3．1第一阶段：以聚类算法为基础，以车载量和工作量为约束条件，形成配送区域3．3．1．1聚类算法简介聚类算法是一种新兴的多元统计方法，是当代分类学与多元分析的结合。聚类分析是将分类对象置于一个多维空间中，按照其空间亲疏进行分类。通俗地讲，聚类分析就是根据事物彼此不同的属性进行辨认，将具有相似属性的事物聚为一类，使得同一类事物具有高度的相似性。相似或不相似的度量基于数据对象的描述的取值来确定的，通常是利用距离进行描述，常见的聚类分析方法有(1)切割的聚类方法。代表算法有：K-MEANS算法、ISODATA算法等。(2)层次的聚类方法。代表算法CURE算法。(3)基于密度的聚类。代表算法DBSCAN算法等。(4)基于网格的聚类。代表算法CLIQUE算法等。烟草行业配送线路优化需要对零售户的空间地理数据进行聚类分析，由于数据量较大，需要一个效率高的算法，而且K-MEANS算法适合于数据型数据，对数据输入顺序不敏感等特点，为比较适合的一种算法。K-MEANS聚类算法的基本思路是：首先从n个数据对象任意选择k个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其昀相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到所有中心都不在变化为止。k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。3．3．1．2K-MEANS聚类实现K-MEANS聚类算法有两个关键问题需要解决，一是初始聚类中心的个数，二是初始聚类中心的位置。（1）初始聚类中心的个数，也是配送区域划分的个数，也就是为这些配送区域送货的配送车辆的台数。即k=配送车辆的台数=送货量车载量+1，加1主要考虑车辆配装时不可能完全满载。（2）初始聚类中心的位置，原算法是随机的，为提高聚类的效果，优化聚类的结果，依照密度的分布，对初始聚类中心优化生成。以每个零售户的地理数据点为圆心，以数据库中零售户地理信息表中所有地理数据之间距离的平均值为半径作圆，然后根据每个圆内的数据点的密度来排序确定初始聚类中心。这样，k-means聚类算法需要的初始中心就由以上算法生成，而无需用户进行事先指定.整个过程包括以下几个基本步骤：1)将数据库中的每个点都看成一个类，计算所有点之间的距离,生成距离矩阵，两点之间欧式的距离为：ijD=22()()ijijxxyy−+−（ji,=1,2,3,…,n）。2)选取2个正数，一般R2=2×R1，其中R1为数据库中所有点之间距离的平均值，D=11nnijijDnn==×∑∑。3083)以每个点为圆心，以R1为半径作圆，计算落在每个圆内的点数目，即样本密度；如求点iA,()iixy的样本密度iρ。Step1：：令iρ=0；Step2：：取11,1()Axy,判断其是否落在以iA,()iixy以R1为半径的圆内，其判断方法为：1iAA=2211()()iixxyy−+−≤R1，如上述成立，则iρ=iρ+1；Step3：判断是否所有点均已判断完,如果完毕，iρ即为iA的样本密度，否则判断下一点，重复第二步。4)将样本密度按从大到小的顺序排列,取密度昀大者作为第一个聚类中心Z1，选择密度次大的数据点'Z，若'Z与第一凝聚点1Z之间距离大于R2，即|1Z'Z|R2，则把'Z作为第二个凝聚点Z2，否则继续判定下一密度昀大者，若下一密度昀大者的点与前面若干个凝聚点之间距离均大于R2，则将之作为又一新的凝聚点，如此反复迭代直到达到要求聚类的数目k。5)把得到的k个聚类中心Z1，Z2，Z3，…，Zk作为K-MEANS算法的初始聚类中心。以一组测试数据为例，模拟为97零售户的地理座标信息，其分布如下图：：图1零售户的地理坐标信息模拟Fig.1Simulationofretailers’geographicalcoordinates按照上述改进后聚类算法的思路，将97个零售户分成八个类，即八个配送区域。309图2八个类的分布图（情况二）Fig.2Distributionofeightclustersin2ndsituation3．3．1．3以车载量为限制条件对聚类结果调整聚类完成后，还应根据车载量这个约束条件对聚类结果进行判断调整。具体实现方法为：Step1：计算每一个类内的零售户的订单量总和；Step2：判断每一类内零售户订单量总和是否超过车载量如果未超过，说明符合限制条件。如果超过车载量，选择该类中距离质心昀远的点，将其拟归入距离其他类质心距离昀近的类，归入某一类前，还必须判断如归入后该类的卷烟零售户的订单量是否小于车载量。如果小于，即将该数据归入该类，否则，选择欧氏距离再次之的类作为拟归入的类，同样判断该类卷烟零售户订货量是否小于车载量，如果小于则归，否则选择距离再次之的。Step3：当所有的类零售户订单量总和都小于车载量时，暂告一段落。调整完毕以后，每一类的卷烟零售户地理位置相对集中，且订单量总量小于车载重量。3．3．1．4以工作量为限制条件对聚类结果调整提出泛工作量的概念，对配送线路的工作量进行测量，并以工作量为约束条件对聚类以后的结果进行调整。关于配送人员工作量的计算一直是物流配送中心管理工作中一个难点。难点之一在于影响配送人员工作量的因素较多；难点之二在于各影响因素的量纲不统一，无法计算和判断。为了能更好地计算配送人员的工作量，笔者通过与配送中心管理人员、驾驶员、送货员进行广泛接触，了解配送人员的实际工作情况，并通过实地跟车送货，提出了一个衡量配送人员工作量（包括驾驶员和送货员）的一个概念——“泛工作量”。该指标综合考虑了送货里程、零售户户数、送货卷烟量，以及零售户的结算方式、路况等因素，并且通过一定的权值，将各个影响因素均统一转化成秒、分或小时这些时间单位的数值，从而将工作量的大小以工作时间的长短来表示，能比较直观和准确地衡量不同送货线路负荷大小。具体可以用下式来表示：iL=1aiC+2aiP+3aiR+4aiH+D……………(1)310式(1)中：iC为配送线路的长度、iP该条配送线路上零售户数、iR为该条配送线路上卷烟配送量、iH为配送线路上现金结算的零售户、D为配送人员每天配送卷烟必须花费的固定时间，主要包括车况检查、停车入库