城市物流配送中的路径优化算法外文翻译资料

城市物流配送中的路径优化算法

Yuming Chen

Modern Educational Technology Center

摘要 - 随着计算机和网络技术的进一步发展和应用，现代物流和配送正在进入信息技术，自动化，网络化，智能化发展阶段。 本文针对电子商务环境，第三方物流的需求，对物流运输车辆路径优化问题进行了研究。 在参考线前辈汽车优化解决方案的过程中，本文采用遗传算法的启发式方法来实现，并在遗传算法框架下加入强大的局部搜索能力贪心算法，利用贪心邻域搜索算法建立一个原理。 各种新的遗传交叉算子是一种贪婪的交叉算子，从而提高了遗传算法的局部搜索能力，实现了快速收敛效果。

关键词 - 物流配送; 遗传算法; 贪心算法;

1. 引言

随着经济全球化和信息技术的飞速发展，电子商务作为商业贸易的先进方式，在全球范围内迅速传播，并对传统商业领域的思想和行为产生了巨大的影响和影响。 在电子商务环境中，完整的业务活动是由信息流，业务流，资金流和物流四个有机组成。 信息流，业务流，资金流都可以在互联网上实现，这是一个“虚拟”的经济过程，但它最终还是需要依靠高度发达的物流配送系统，所以在某种意义上，物流和 电子分销业务的重要组成部分是信息流和现金流的基础和载体，也是电子商务成功的关键因素。

配送作为物流系统分布的重要组成部分，在整个物流系统的效率起着举足轻重的作用。在我国这个阶段，物流配送的发展还比较落后，基本上仍停留在“只送一个值得”的水平，造成配送效率低，配送效率低，成本高，服务质量差，已成为制约因素。和健康发展的电子商务瓶颈[1]。高成本，低效率的物流配送使得电子商务在线完成即时节省时间，成本变得毫无意义。因此，如何实现快速准确的交付是企业在一个必须解决的重要问题上运作。有鉴于此，研究应用科学方法对物流配送进行合理组织，建立高效，经济的物流配送体系，支持和保障电子商务的快速发展已成为当务之急。

整个物流配送系统的物流路线和车辆调度优化是关键领域，也是电子商务活动中不可或缺的要素。 这个问题首先得到了纠正Dantzing和Ramser：1959年，由于这个问题涉及多学科理论，应用前景，我很快就兴起了运筹学，应用数学，图论和网络分析，物流与运输工程，管理 理工科，计算机科学学科，工程技术人员非常重视。 此后一直是运筹学领域和前沿组合优化研究的重点，该课题专家对该问题进行了大量的理论研究和实验分析，取得了很大进展。

道路规划物流配送领域组合优化问题是众所周知的NP（Nondeterministic Polynomial Problem，即非确定性多项式问题）问题。 许多专家学者对其计算复杂性进行了研究，这是确定求解算法方向的基础[3]。 近二十年来，国内外物流配送路径规划问题都是一个非常活跃的研究领域。 国内外对于解决问题的方法可分为精确算法和启发式两大类。

1. 配送概述

物流配送物流结束时，正在挖掘第三方物流系统的源头，突破性，增加物流成本，优化完整的物流系统，改善服务，降低成本等功能，在物流系统中占有一席之地 重要的位置。 按照国家质量技术监督局颁布的中华人民共和国国家标准“物流条款”将解释为分布：在区域框架内的经济合理性，根据用户要求，选择项目，加工 ，包装，分区，集团分销和其他业务，并在指定地点按时交付物流活动。

根据主要物流可分为五类：

大型制造商主导的物流和配送是指产品直接向零售商，制造商的时间，发送给零售商的请求数量，如分配方法[6]。 这需要这样的大规模生产者，具有更广泛的销售和营销网络分布。 中国知名企业如海尔，联想，清洁，长虹，康佳，TCL，美的，格力，科龙等企业都有计划在其营销网络的基础上，建立自己的物流配送体系，包括海尔，联想， 清洁等已率先与第三方物流公司进行在线销售和分销业务。

大型连锁企业从集团化物流配送，由于其统一的采购和采购，统一的库存和配送，统一的管理和运作以及巨大的规模经济和快速发展。 在分销链中，世界500强排名第四的沃尔玛被评为零售分销模式。 沃尔玛拥有近20个大型配送中心，其中有2000多辆长途运输车[13]，卡车和运输车辆超过11000辆并拥有私人通信卫星并改善了货物的采购跟踪，库存，配送 和其他管理系统。

大型批发和物流业务为主导，即从制造商的大型批发商，将批发商品批发分配到小型超市，便利店，百货商店和其他中小型零售商的土地面积。

专业物流企业发展以社区为基础的物流（第三方物流公司），其中主要指中国邮政和快递公司等已经准物流业务，原有的大型制造商，批发零售企业等。 交通部门远离母亲单独或通过差异化出来的不同储运部门企业共同组建联合物流公司兼并，并从公路运输，仓储公司专门从第三方物流服务企业转型社会[8]。

以运输为主题，以货代为主的物流，是指从事航运，港口，铁路和公路等运输业的企业依靠港口，货运站，集装箱堆场，公路枢纽机场及其当地行为背后的互联网接入快速将货物运送至 用户，而不是等待特殊的用户提取。

1. 物流路径规划中的遗传算法

遗传算法（Genetic Algorithm，GA）是一种模拟达尔文遗传选择在自然环境和生物遗传和进化过程中形成的自适应概率搜索算法的全局优化。遗传算法是一种基于社区的操作，用于将所有个体分组为目标。选择（Selection），交叉（Crossover）和变异性（Mutation）是遗传算法的三大操作算子，它构成了所谓的遗传算子（Genetic Operation），使遗传算法的其他传统方法不具备。遗传算法涉及五个主要因素：参数编码，初始种群创建，评估函数（即适应度函数）设计，遗传算法在设计和控制参数设置中运行[4]。遗传算法经过多年的发展，已经可以应用于多种领域：功能优化，组合优化，自动控制，机器学习，图像处理，人工生命，遗传编程和机器人技术等。

遗传算法实际上是迭代生成测试搜索算法的特征。 它首先生成一个可行的解决方案组，然后测试这些解决方案的质量（计算其评估函数值）。 然后，重新利用遗传算子生成一个新的群体，然后对这一新的群体进行重新检验。 重复此过程，直到算法终止[11]。 算法的基本结构我们可以看出，遗传算法解决问题的方法本身无知所做的是通过算法生成来评估每个个体，并通过遗传操作产生新一代群体，从而获得良好的适应值 个人的健康状况比个人的健康更有机会重现。 因此，演变继续代代相传，直到算法满足给定终止的条件。

1. 利用车辆路径优化问题解决TSP的四维遗传算法

在上一节中，介绍了基本遗传算法。 虽然遗传算法比其他传统搜索方法更强大，但它更擅长全局搜索但却没有足够的本地搜索能力。 该研究发现，遗传算法可以快速加速到最优解的90％左右，但要获得真正的最优解，则需要花费很长时间。

遗传算法是一个渐进的收敛过程。 保留在遗传算法机制中使用最佳个体的选项，可以搜索全局最优解。 然而，在实际应用中，遗传算法可能会收敛到一个可行的解决方案，但最可行的解决方案可能不是整体优势，甚至不是局部最优解[7]。

因此，遗传算法框架，适当引入其他局部搜索方法，提高遗传算法在实践中的局部搜索能力是非常必要的。

在遗传算法运算中，在可行解空间交叉运算，运动范围广，步伐比较大; 由于“选择”压力导致的突变，通常难以使局部搜索的有效性（特别是遗传算法倾向于在后期阶段收敛）。 因此，在遗传算法的框架下，通过添加其他强启发式局部搜索算法的局部搜索能力可以提高遗传算法的局部搜索能力，进一步提高质量，优化搜索效率，以弥补一些单一的优化方法的不足。

贪婪方法，也称为局部改进算法（10cal改进），是一种基于邻域搜索方法的搜索技术。 这种方法很强，局部搜索能力是寻找局部最优解的常用方法[2]。 对于模型搜索，“贪婪”搜索意味着解决方案空间中的解决方案开始搜索当前解决方案邻域，如果邻近解决方案优于当前解决方案，则使用此解决方案替换当前解决方案，并且 然后继续搜索Up以满足搜索停止条件。当搜索无法进一步改善目标函数时，得到局部最优解。 本地搜索优化方法是单一方向，新一代解决方案仅取决于搜索过程中收集的信息[12]。 一旦目标函数值无法进一步改善，搜索将被暂停，并且很容易陷入本地最小。

遗传算法用于局部搜索能力不足的局部搜索贪婪算法与强组合构建单车辆路径优化的混合遗传算法。 该算法的特点是通过遗传操作添加贪婪交叉算子，以增强局部搜索算法的容量。

A.Encoding

为了提高效率，TSP路由优化问题采用自然数编码方法，即编码序列的数量。 是给客户端访问点会给出一个自然数，然后将自然数作为路由路径规划的有序排列。 例如，N是一个分布点，每个点在自然数之间给出一个（1，N），运输路线可以表示为有序的染色体串xX1，i1,2，L，N 如果染色体

指示路线1534如下：配送仓库客户客户l客户3 1 5 1 4 a配送仓库客户。 在这条染色体的结构内是有序的，如果路径到l，2的中点交换位置，则目标函数值会发生变化[9]。

B.健身功能

在遗传算法中以个体适应度的大小来判断个体是否继承到下一代群体的概率，个体的适应度越大，个体继承到下一代的概率就越大; 另一方面，个体适应程度越小，个体就会继承下一代较小的概率[5]。 对于分配对应于个体程序的优缺点的路径与否，是通过计算适应度函数来确定该值，适应度函数值越高，表明个体越优越。 在本文中，适应度函数通过以下公式计算：

F =1000 / （ D01 L Dn 0 ）

C.形成初始人口的方法

在一类自然数的非重复之间随机生成1~L的L，其中L个非重复的自然数被排列成个体。个人对应于问题的可行解决方案。将种群大小设置为N，然后通过随机生成的个体初始种群来形成N.

D.选举行动

成对的遗传算法的交叉和变异遗传操作，如恒定属性，产生了新的个体。虽然由于群体的进化会产生越来越多的最佳个体，但由于选择，交叉和变异的遗传操纵随机性，它们也可能破坏当前群体中的最佳适应度，会降低群体的平均值适应度和遗传算法的运行效率，收敛有负面影响。为了消除这种影响[3,10]，你可以用来保存最适合生存的个人选择，以适应最优秀的策略来运作，也就是说，当前这个群体能够适应不参与交叉和变异的几个人中最高的一个。操作，但似乎很自然地通过交叉和变异遗传操作代表小组使用这个，在最低数量的个体后产生适应性，以确保遗传算法的快速收敛。

E.Crossover --Greedy Crossover

在遗传算法中可以选择各种交叉算子，如基本交叉算子（BX），部分映射交叉（PMX），阶次交叉（OX）和周期交叉（CX）等，以增强算法 本地搜索功能，本文利用贪心邻域搜索原理解决TSP问题，提出了一种新的交叉算子贪婪交叉算子。 这种算子为了最小化相邻基因之间的距离选择邻域为基因，实现快速收敛的效果[2]。

在单车路径优化求解过程中，本文采用遗传算法框架，通过加入强大的局部搜索能力贪心算法，提高了遗传算法的局部搜索能力，实现了快速收敛的结果。

1. 结论

随着计算机和网络技术的进一步发展和应用，现代物流和配送正在进入信息技术，自动化，网络化和智能化发展阶段。 本文研究了对第三方物流公司的需求，对路径优化的物流运输车辆进行了研究。 在绘图的基础上，先前的研究提出了一种城市物流配送路径优化算法，即遗传算法和贪婪算法的交叉运算，两者相辅相成，实现了快速收敛效果。 有一些创新。

参考文献

[1] Syam Siddhartha，S：后勤组件定位问题的模型和方法。计算机与运筹学（29），1173-1193（2002）

[2] Sun，H.j.，Gao，Z.y：物流配送中心的竞争定位模型。交通运输工程学报（4），54-57（2002）

[3] Spohrer，G.A.，Kmak，T.R：用于评估替代工厂位置情景的定性分析。 INDUST。工程。 （8），52-56（1984）

[4] Bin，H：Hopfield人工神经网络在物流配送中心选址优化中的应用。模块化机床与自动化制造技术（3），24-29（2003）

[5]米尔格兰姆，S：小世界的问题。今日心理学，60-67（1967）

[6] Xu，Q.-q.，Miao，L.-x：基于产业链演化的物流网络资源配置策略。工业工程与管理（5），43-47（2006）

[7] Watts，D.J.，Strogatz，S.H：“小世界”网络的集体动态。 Nature 393（6684），440-442（1998）Barabasi，A.L.，Albert，R：在随机网络中出现缩放。 Science 286（5439），509-512（1999）

[8] Fan，W.X.，Xiang，L.，Rong，C.G：复杂网络理论及其应用。清华大学出版社（2006年）

[9] Guorong，C.，Ping，Y：一种基于增长的物流网络建模方法。 华南理工大学学报（自然科学版）5（36），24-29（2008）

[10] Yingluo，W：系统工程，第3版。 中国机械出版社（2005）

[11] K.H。 赖和T.C.E. Cheng，“运输物流中的供应链绩效：服务提供商的评估”，国际物流期刊：研究与应用，Vol.6，No.3，pp.151-164,2003。

[12] Jagdev，H.S.和Thoben，K.-D，Anatomy of enterprise cooperation，Production Planning and Control，12（5），437-451,2001。

[13]乙。 Rao，Z.Navoth

剩余内容已隐藏，支付完成后下载完整资料

A Routing Optimization algorithm in City Logistics Distribution

Yuming Chen

Modern Educational Technology Center Zhejiang Gongshang University Hangzhou,China

cym@mail.zgsu.edu.cn

Abstract-With the computer and network technology to further the development and application of modern logistics and distribution are entering an information technology, automation, networking, intelligent stage of development. In this paper, e-commerce environment, the need for third party logistics, the logistics of the delivery vehicle path optimization problems were studied. In the reference line of predecessors cars optimization solution process, this paper adopts a genetic algorithm heuristic approach to achieve, and in the framework of genetic algorithm by adding a strong local search ability greedy algorithm using the greedy neighborhood search algorithm to establish the principle of a kinds of new genetic crossover operator a greedy crossover operator, thus improving the local search ability of genetic algorithm to achieve a rapid convergence effect.

Keywords-logistics and distribution; genetic algorithm; greedy algorithm;

1. INTRODUCTION

With economic globalization and the rapid development of information technology, e-commerce as a commercial trade in an advanced way to trade in the global spread rapidly, and the traditional commercial areas of the ideas and behavior produced a huge impact and influence. In e-commerce environment, a complete business activities are conducted by the information flow, business flow, capital flow and logistics flow of four organic composition. Information flow, business flow, capital flow can be implemented on the Internet, this is a matter of 'virtual' economic process, but it is still ultimately need to rely on highly developed logistics and distribution system, so in a certain sense, logistics and distribution of electronic an important part of business is the information flow and cash flow basis and carrier, were also a key factor in the success of e-commerce.

Distribution as a logistics system, an important part of

the efficiency of the whole logistics system plays a pivotal role. In our country at this stage, the development of logistics and distribution is still relatively backward, basically still stuck in the 'only send worthy' level, resulting in inefficient distribution, distribution, high costs and poor quality of service, which has become a constraint and healthy development of e-commerce bottleneck [1]. High-cost, low efficiency of logistics and distribution makes the completion of e-commerce online instant savings of time, cost has become meaningless. So how to achieve fast and accurate delivery is the enterprise operating in an important issue that must be addressed. In view of this, study the application of scientific methods for the rational organization of logistics and distribution, the establishment of an efficient,

cost-effective logistics and distribution system to support and guarantee the rapid development of e-commerce has become a top priority.

Logistics routing and vehicle scheduling optimization of the entire logistics and distribution system are in key areas, but also an indispensable element in e-commerce activities. This problem was first corrected Dantzing and Ramser: in 1959, because of this problem involves the theory of multi-disciplinary, application prospect, and I quickly rise to operations research, applied mathematics, graph theory and network analysis, Logistics and transportation engineering, management science and engineering, computer science disciplines, engineering and technical personnel of great importance. Since then has been a field of operations research and combinatorial optimization of cutting-edge and research focus, the subject experts on the issue a lot of theoretical research and experimental analysis, has made great progress.

Path planning logistics and distribution field of

combinatorial optimization problem is well-known NP (Nondeterministic Polynomial Problem, that is, non-deterministic polynomial problems) problems. Many experts and scholars to its computational complexity has been studied, which is to determine the basis for the direction of solving algorithm [3]. Past two decades, both at home and abroad, logistics and distribution path planning problems are a very active research field. At home and abroad for the solution to the problem can be divided into exact algorithms and heuristics two broad categories.

1. DISTRIBUTION OVERVIEW

At the end of the logistics and distribution logistics, is digging a source of third-party logistics system, a breakthrough, with increased logistics cost, optimizing the complete logistics system, improve service, reduce costs and other functions, in the logistics system occupies an important position. In accordance with the State Quality and Technical Supervision issued by The Peoples Republic of China national standard 'logistics terms' will be interpreted as a distribution: In the economic rationality within the framework of the region, according to user requirements, selection of items, processing, packaging, partition, group distribution and other operations, and on time delivery of logistics activities in designated locations.

According to the main logistics can be divided into five categories:

A large manufacturer-led logistics and distribution refer to the product directly to retailers, manufacturers of the time, the number of requests sent to retailers, such as a distribution method [6]. This requires such large-scale producers, has a

978-1-4244-6349-7/10/$26.00 sect;c 2010 IEEE

V7-67

wider distribution of sales and marketing network. Chinas well-known enterprises such as Haier, Lenovo, cleaning, Ch

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[277130]，资料为PDF文档或Word文档，PDF文档可免费转换为Word