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

《烟草配送线路优化问题的探讨》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、烟草配送线路优化问题的探讨王芳江苏省泰州市烟草专卖局（公司）摘要：配送是物流运输活动的一个重要环节,配送线路规划得成功与否将直接关系到现代物流中心运行的成本和效率。本文对该VRP问题及算法进行了比较深入地研究探讨。对配送区域的形成、区域内优化线路的形成这两个线路优化过程中的关键性问题进行了细致地分析研究，并用一组测试数据验证了算法的可行性。整个方案具有较强的实用性、科学性和实践性。关键词：烟草配送；配送线路VRP问题；线路优化1配送线路优化问题研究的意义烟草行业是国民经济重要而又特殊的行业，实行的是“统一领导、垂直管理、专卖专营”的管理体制。烟草行业在国民经济中占有举足轻重的地位。但随着

2、中国加入WTO，WHO推出了一系列的控烟措施，再加上经济全球化的影响使中国烟草行业面临着前所未有的挑战。中国烟草行业迫切需要提高自己的核心竞争力来应对越来越严峻的形势。现阶段烟草行业的核心竞争力主要由两个方面构成：其一是产品技术，也就是生产国式卷烟所需的各项技术；其二就是物流技术，在生产设备、原辅材料趋于同质的今天，如何做到比竞争对手更及时、更有效地满足市场需要已成为企业竞争的重要内容。二者相比，物流技术更具战略价值。配送是物流一个重要环节，从烟草企业的层面上看，烟草配送是关系到企业经济效益实现，关系到卷烟零售户的满意度提高，进而关系到企业核心竞争能力提升和生存、发展的大问题。配送线路规

3、划的成功与否，将直接影响配送成本高低、工作效率快慢和服务质量优劣，关系到大物流建设的整体优势能否体现。2配送线路优化问题分析物流配送线路优化问题，其实就是以线路最优化为目标的车辆调度问题，即VRP问题，问题的实质是对于一个确定的卷烟零售户集合，在确定的需求下，如何安排车辆、安排行驶路线和安排时间，使得总的行使里程数最小。配送车辆调度问题（VRP），最早是由Dantzig和Ramser于1959年首次提出的，自此很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。线路优化问题一

4、直是学术界的NP难题，一般来说给定约束条件，具体问题的解空间有限，虽然从理论上是可以找出问题的最优解的，但是此类问题的求解非常复杂，特别是随着配送规模的增加，计算量呈指数增长，求解过程复杂。线路优化问题的常用算法，究其实质，基本上可将求解方法分成精确算法和启发式算法两大类。精确算法的计算量一般随问题规模的增大呈指数增长，因此在实际中其应用范围很有限。由于VRP问题是NP困难问题，高效的精确算法存在的可能性不大（除非P=NP），因此寻找近似算法是必须和现实的，为此，专家们主要把精力花在构造高质量的启发式算法上，目前，绝大部分这方面的研究成果也是对启发式算法的设计或改进。尤以两阶段算法是目前

5、成果最丰富、应用最多的一类方法，作者简介：王芳，女，江苏南通人，经济师，在职研究生，硕士，现为泰州市烟草专卖局（公司）经济信息中心主任,邮箱：wfnewyear@163.com，通讯地址：江苏省泰州市迎春西路71号，邮政编码：225300，305在两阶段法求解过程中，常常采用交互式优化技术，把人的主观能动作用结合到问题的求解过程中，如先路径后分组算法(Route-First/Cluster-SecondMethod)，先分组后路径算法Cluster-First/Route-SecondMethod)3烟草配送线路优化的研究如何对配送线路进行科学地优化和整合，对配送车辆进行合理的调度、对线

6、路之间的工作量进行科学的均衡，对配送车辆装载率进一步合理的提高，是烟草配送线路优化希望达到的目标。3．1问题提出与描述(1)已知条件N={0,1,2,?,n}①所有卷烟零售户的集合N为已知，，其中，0为配送中心，其他为卷烟零售户所在地；②从配送中心出发的配送车辆，经过卷烟零售户所在地之后再返回配送中心，这时，配送车辆所经过的零售户的顺序称为路线；③在配送中心的配送车辆的种类、数量以及每辆车最大装载能力W为已知；PGR④卷烟零售户i数为n，地理位置i为已知，且每一个客户的卷烟需求量i已知（i=1,2,,,n）；T⑤每辆车每日最长送货时间为k；diji=1,2,?,n−1⑥配送中心到各零售户

7、点的距离及零售户之间的距离为（；j=1,2,?,ni