摘 要

二十世纪下半叶以来，全球化的趋势明显加快。随着科学技术的发展，特别是信息技术和通迅技术的发展，现代物流业进入了一个快速发展的新阶段。与发达国家相比，我国物流企业的发展还处于初始阶段，大多数企业尚未发展自身的企业物流，第三方物流市场竞争激烈，而资源整合难度大，部分中小型物流企业存在资源利用率、物流效率低等问题，导致企业竞争力日渐下降的同时对环境造成较大负担。

本课题研究目的是对我国中小型物流企业的物流配送路径进行优化，以扬州正帆货运代理有限公司在江苏省中北部的物流配送线路优化为例，通过分析该企业物流业务情况，建立物流线路优化模型，对现有路径优化算法进行择优比较，并选择遗传算法求解，满足企业经济利益的同时提高企业市场竞争力，最后对配送模式中可能存在的其他不足之处给出改善建议。

关键词 线路优化；车辆路径问题；遗传算法

Abstract

Since the second half of the 20th century, with the acceleration of globalization, science and technology, especially the development of information technology and communication technology, has driven the modern logistics industry into a new period of vigorous development. At present, the development of logistics enterprises in China is still in its infancy as most enterprises are lack of its own logistics. As a result, third party logistics market competition is fierce, and resources integration is difficult to realize. Problems like low resource utilization and low efficiency of logistics are existing in some small or medium-sized logistics enterprises, which leads to increasingly decline in enterprise competitiveness and create greater burden on the environment.

The purpose of this research is the logistics distribution route optimization of our country small or medium-sized logistics enterprises. The author takes Yangzhou Zhengfan co., LTD in north-central Jiangsu province as an example and analyzes the operating condition of this logistics business enterprise to establish the route optimization model. By comparing the existing path optimization algorithm, genetic algorithm (GA) is selected to satisfy the business enterprise economic benefits and enhance the competitiveness of the enterprise in the market at the same time. Finally, suggestions are presented to the distribution pattern of the other deficiencies improvement.

Keywords: Route optimization; Vehicle routing problem; Genetic algorithm

目 录

第1章 绪论 1

1.1研究背景 1

1.2研究文献综述 2

1.2.1路径优化模型的提出与主流优化算法的研究 2

1.2.2现代智能算法在解决路径优化问题上的应用 2

1.3研究内容及方法 3

1.3.1研究内容 3

1.3.2研究方法 3

1.4研究的技术路线 5

第2章 扬州正帆货运代理有限公司物流配送现状分析 6

2.1 扬州正帆货运代理有限公司物流配送现状 6

2.2 扬州正帆货运代理有限公司物流配送过程中存在的问题 6

2.3 解决现存问题的策略与方法 7

第3章 物流配送车辆路线优化模型的构建 8

3.1问题描述与模型的选择 8

3.2物流配送需求分析 8

3.3模型的选择与配送成本分析 9

3.4模型的假设与约束 9

3.3.1模型建立的假设前提 9

3.3.2基础参数设置 9

3.3.3模型构建与约束 10

第4章 物流配送车辆路径优化模型求解 12

4.1算法的选择 12

4.2算法的实现 12

4.2.1 VRP问题的算法描述 12

4.2.2算法的运行 13

4.3实验结果核对与分析 14

4.3.1 实验结果核对 15

4.3.2 结果分析 15

5.结论与展望 16

5.1 工作总结 16

5.2 不足与展望 16

参考文献 18

附录A 19

MATLAB主程序 19

致 谢 23

第1章 绪论

1.1研究背景

随着科学技术的进步和社会经济的发展，经济全球化进程不断加快，我国的进出口经济也在不断增长。进出口贸易对国民经济的促进作用也得到了国家前所未有的重视。因此，货运代理行业的发展一直受到外贸快速发展的推动。

改革开放的伟大战略实施以来，我国货运代理行业的业务持续增长，与之相关的国家政策法规和基础设施建设在“引进来，走出去”的国策驱动下都有了明显改进。相较前些年，行业服务能力有了显著提升，现代物流发展的基础也逐步形成。但从宏观角度出发不难发现，与行业发展成熟的国家相比，我国货代物流业发展历史短，服务范围狭窄，难以形成规模化的网络化服务，抗风险能力弱，集约化程度低，有效融资环境匮乏等问题。作为后金融危机时代的产物，各类企业之间的竞争日趋激烈。由于业务量的减少和利润的损失，许多中小企业正在挣扎求生，我国货代行业的产业结构也随着行业资源和市场份额的重新洗牌而不断调整。在此大背景之下，中小型货代企业正在积极地寻求适合自身发展的道路，以期在复杂的市场环境中分到一定份额。

现阶段相比于细节化、具体化的物流营运模式调整，国内外学者对于货代企业的研究更趋向于现代物流的宏观大方向。而事实上，企业规模对发展方略的选择有决定性影响。大中型货代企业会为实现物流现代化加大投入以求获得更高的利润，然而，由于中小货代企业的局限性，现代物流的发展还没有提上日程。因此，研究中小型货代企业如何提高经营利润、改善经营方式对整个货运代理业的稳定发展是必要的。

另一方面来讲,货运企业属于物流企业。现如今，能源日益短缺、环境压力增加,整个社会的节能环保意识逐渐加强。对于物流企业而言，减少能源消耗、提高物流配送的效率不仅可以带来巨大的社会和经济效益,也必将成为子孙后代实现社会可持续发展的福祉。物流和配送企业作为能源消耗和污染物排放的主体之一，节能减排效果的好坏将直接影响到当地节能减排的总体效果，科学管控物流流程和提高运行车辆的燃油效率，减少排放，将对实现节能减排、绿色发展的目标起到关键作用。

而对于中小型物流运输企业而言，实现高效绿色物流的关键不在于过早地向前沿理论和大规模物流企业看齐，而在于转变经营模式、优化配送方案。在这之中，首要考虑的是整体供应链环节的优化，这对于大部分难以转型的中小型企业而言是一个长远的规划。其次是可以短期内实现的目标，即尽可能缩短货物在途时间。在营运水平的情况下，缩短在途时间最直接有效的方式在于优化配送路径和车辆调度方案。为此，本文将重点研究车辆路径优化问题(VRP问题)，通过合理安排车辆配送路径和配送订单，制定合理的物流配送方案，以满足运营商和消费者的需求。

VRP是一个典型的组合优化问题,也是一个无多项式解法的问题(NP-hard problem)。现有的大部分研究方向主要在于优化目标车辆里程，总运输成本最低，工作时间最短，使用最少的车辆等等。近年来，随着能源的逐渐短缺和环境的退化，人们的节能环保意识日益增强，越来越多的学者开始研究最小能耗车辆的路径优化问题。本文将从一个企业的角度来研究VRP问题和经典的遗传算法，在实现节能减排物流配送新理念的过程中，根据节能运输的理论和实际需求，结合中国物流行业的特点和现状，为促进物流配送行业的节能减排，加快我国物流业的经济建设提供参考和建议。

1.2研究文献综述

1.2.1路径优化模型的提出与主流优化算法的研究

新时期的物流业有着诸多标志性的特点。学者Alexander T.Richter等^[16]这样概括道：物流业是一个拥有着庞大且发展迅速的路线网络，并对费用十分敏感的行业。一家生产企业如果需要从不同的供应商将商品运至工厂加工，决策者往往会选择市场上运输费用较小的物流公司托运。对于物流公司而言，面对数量较多的客户需求，在路网中选择最优的配送路径可以使运输成本最低化，从而提高自身的市场竞争力。这便折射出现代物流学中的一个问题，即共同配送模式下的路径优化。此外，费用发生极小的改变，也与物流线路规划高度相关，因此优化模型中需要包含准确的费用函数。

学者崔少飞^[3]在研究物流线路优化时提出将运筹学中的0-1规划应用到启发式算法中，建立了某主机厂汽车货运的规划模型。学者张倩等^[12]在研究电商冷链物流路径优化问题也建立了关包含客户需求、成本、配车等要素在内的0-1规划模型，由此可见整数规划是构建优化模型的思路之一。此外，对于配送路线较少、产品时效性要求不高的路径优化问题，李秀邦^[2]和贾冰新^[8]以节约里程法为基础，综合车辆调度情况，把问题转化为VRP或VRPTW问题，利用现有的数学模型求解该问题具有一定的参考价值。

路径优化模型的算法也是本文研究的关键问题之一。现有的主流优化算法分为五类:仿真算法、人机交互算法、精确过程算法、启发式算法和智能算法(现代启发式算法)。^[1]其中，启发式算法和智能算法因可操作性和实用性强而得到广泛认可。智能算法与启发式算法的原理相同，但所采用的模型建立方法更加新颖、科技含量更高。智能算法往往会与计算机技术、人工智能技术相结合，计算的精度得到专家们的认可，在解决复杂问题时也会受到大多数专家的青睐。智能算法包括进化算法、模拟退火算法、人工神经网络等算法，为解决不同实际情况下的路径优化问题提供了选择的空间。

1.2.2现代智能算法在解决路径优化问题上的应用

现代智能算法在解决VRP问题时有着广泛的应用，下文将列举几例常用的智能算法。

第一个例子是蚁群优化(ACO)。蚁群算法，又称蚁群算法，是一种常用的概率算法，用于寻找最优路径。国内外学者对ACO在物流领域的应用都有研究前例可循。学者邓必年^[6] 针对物流配送路径优化中区间重构收敛性差的问题，采用蚁群算法进行优化。在使用基于ACO的路径模型解决电子物流问题时， Eric Hsueh-Chan Lu^[14]提出，除实际物流需求约束外，取货交货的约束条件也应考虑在内，从而对算法进行部分优化，也得到了相对可行的结果。

模拟退火算法是一种基于实体退火原理的概率算法，以较优解代替当前解，在解决局部的旅行商问题（TSP）和车辆路线问题（VRP）时能得到较为精确的结果。但是由于退火算法对新解的验收标准是随机的，因此存在一定程度上接受恶化解的情况。

遗传算法（GA）是一种基于全局搜索、自然选择和最优繁殖的智能算法。与模拟退火算法相比，遗传算法具有更好的全局性能，但求解速度慢、进化速度不理想等弊端限制了其对实际问题求解的效率。

由于结构单一，模拟退火算法和遗传算法各自在解决高维度问题时显露疲软。但值得一提的是，李秀邦^[2]在研究农产品物流配送问题时提出将模拟退火算法和传统遗传算法相结合的模拟退火遗传算法，以退火原理优化遗传算法，十分具有借鉴意义。

此外，对于进化算法的优化完善，近年来也有诸多研究。例如V.N.S.A.Kumar^[15] 采用人工免疫系统(AIS)算法和粒子群（PSO）算法求解双向多循环物流模型。AIS算法和PSO算法都是进化算法，都是从随机解出发，通过迭代求最优解。然而，PSO算法可以根据当前搜索的最优值来寻找全局最优值，这比遗传算法的规则要简单。该算法实现简单，精度高，在解决实际问题中显示出优越性。

1.3研究内容及方法

1.3.1研究内容

本文以扬州正帆货运代理有限公司（下文简称“ZF公司”）为例，对ZF公司进行全面剖析，总结出ZF公司现有物流配送模式的劣势，建立了苏中北部物流配送业务车辆路径优化模型。最后利用遗传算法对模型进行求解，并对未来ZF公司的经营战略提出合理建议。

论文全文共五个章节：

第一章为绪论。本部分首先介绍了本文的研究背景、国内外研究现状，然后阐述了本文的研究目的和意义，最后提出了本文的主要研究内容和研究方法。

第二章整理了ZF公司的基本情况以及现阶段物流配送业务中存在的问题。

第三章介绍了物流配送优化模型的构建过程，包括需求分析，模型前提假设，目标函数，条件约束以及对最终建立的VRP模型参数进行详细阐释。

第四章介绍了对ZF公司物流配送VRP模型的求解及在MATLAB平台上的仿真实验。

第五章是对本论文选题的工作进行总结，并对本文研究过程中存在的问题和不足进行总结。

1.3.2研究方法

本篇文章通过对ZF公司江苏中北部物流配送模式的研究，首先分析了其物流配送业务中存在的问题；然后通过对ZF公司物流需求节点的数量、位置，运输载具的调度情况等营运现状进行了研究，进而对物流配送路径和车辆调度进行了优化设计；最后，在物流配送路径优化过程中，建立了VRP模型，并根据遗传算法计算模型的最优值，最终达到了本文的预定目标。在本研究过程中，采用了以下研究方法：

首先，本文运用了模拟建模的研究方法，将ZF公司的物流配送业务难题转化为数学模型，并根据实际情况建立约束条件以供求解。

其次，本文采用仿真验证的研究方法，利用MATLAB仿真工具对算法进行仿真，并实际验证了遗传算法的效果。

最后，在研究方法与实践相结合的基础上，构建并完善了ZF公司的物流配送模式，以实际的物流配送条件对实验结果的合理性做出分析，并且提出了具体的物流配送路径优化方案。

1.4研究的技术路线

本文的技术路线图如图1.1所示。

结论与展望

遗传算法求解VRP模型

绪 论

扬州正帆货运代理有限公司物流配送现状分析

物流配送车辆路线优化模型的构建

图 1.1 技术路线图

第2章 扬州正帆货运代理有限公司物流配送现状分析

2.1 扬州正帆货运代理有限公司物流配送现状

扬州正帆货运代理有限公司（本文简称“ZF公司”）注册于2009年，注册资本200万人民币，经营范围为进出口货物的陆路运输代理及相关运输咨询服务，属于我国中小型物流配送企业。经营发展十年以来，该企业以江苏省为主要业务区域，拓展了多条城际配送业务线路，但资源配置不合理、配送效率低等问题成为遏制其自身发展的主要原因。

目前，该公司在江苏中北部的主要的物流业务为将上海海关进口的货物（以儿童玩具为主）配送至中北部6所城市的十余个销售点。现有的配送路线为由上海统一运送至南通，再由南通分散配送至扬州、盐城、徐州、盐城、淮安等城市的配送点。现有的配送模式为由南通单独配送货物至各需求点。

截至2018年，ZF公司员工多达数百人，然而高学历人才的占比依然较低，多分布在公司中高层职位，在物流公司人员需求最大的终端或基层网点中，还是多以低学历、大中专学历人员为主，整体的快递配送人员知识水平较低，配送的服务和质量有待进一步提高。在此情况下，简单高效的优化方案更利于ZF公司的执行。

2.2 扬州正帆货运代理有限公司物流配送过程中存在的问题

配送模式不合理。

在现有配送模式下，各配送点派来运货的车辆存在起程空载的问题。此外，由于各销售点的需求量或多于或少于配送车辆的满载量，导致车辆里程利用率没有达到最合理情况，降低了经济和环境效益。配送模式的不合理亦导致了运输线路规划的不完善，部分路段出现多辆车重复运输的问题，增加了不必要的配送成本。

配送信息化质量低。

目前，ZF公司从顾客下单到签收的整个物品配送过程中，所用到的信息处理技术的较为落后，买卖双方和物流公司之间缺乏一个完善的信息技术平台，对配送的物品，缺乏实时进行追踪的技术，配送商品的丢失和损坏有着较大风险。其次，ZF公司的设施也不够完善和先进，设备的自动化水平低，操作复杂，运输方式单一，不能满足大批量的商品运输，可能造成货物积压，使之商品的质量不能得到保证，为电子商务的综合服务质量带来一定的影响，需大量的人力物力，增加了配送的成本。

配送成本高。

近几年，随着我国经济的发展，国内的物价普遍上涨，包括与物流相关的材料成本、油价、仓储费用、人工费用等普遍上涨，对于一些物流配送规模小、需求分散的业务来说，配送成本自然就会上升。

配送周期长。